Design and audit a fair random allocation

Try

Three fictional people, A, B and C, need equal chances of receiving one shared ticket. You have independent fair coin tosses, but no three-sided random device. Two tosses produce four equally likely codes: 00, 01, 10 and 11, where 0 and 1 label the two coin outcomes. Assigning the first three codes to A, B and C leaves one extra code. What should happen when it appears?

A tempting shortcut gives 11 to A as well as 00. Count the elementary outcomes: A then receives probability 1/2, while B and C each receive 1/4. Calling the procedure random does not make it fair. Here fairness means equal probabilities under the stated coin model, not that every short sequence of actual draws contains equal counts.

Predict

Consider rejecting 11 and tossing again. Predict whether each person has the same chance of eventually receiving the ticket. Now impose a maximum of three attempts. Predict whether equal chances can coexist with a possibility of selecting nobody. Make the stopping rule part of your prediction; a hidden fallback can change all the probabilities.

Two-bit code	Action
00	Select A and stop
01	Select B and stop
10	Select C and stop
11	Reject; try again only if an attempt remains

The procedure uses at most six coin tosses with a three-attempt cap. It might stop after two. A cap is a maximum workload, not a claim that every run takes the maximum.

Experiment

Choose an attempt cap in the explorer, predict the probability of no decision, and reveal the exact finite law. Run a seeded teaching replay and inspect every consumed code. Next select the deliberately constructed all-rejection path. That path is not a random sample; it exposes what the procedure actually does when the budget is exhausted.

Inspect a fair allocation and its stopping rule

Use independent fair bits in pairs: 00 selects A, 01 selects B, 10 selects C, and 11 rejects and retries. Predict each person's unconditional chance and the chance of no decision when retries are capped.

Maximum attempts12345Replay seedRun seeded allocationInspect all rejections

Reveal calculationsReset explorer

Commit to a prediction, then reveal the table and fixed-scale plot. Change one control and explain the difference.

All settings and traces are temporary. This explorer does not save an answer or award mastery; keep your assumptions and reasoning in the written practice.

Increase the cap and compare the no-decision probability without changing the accepted-code mapping. Explain why no winner is reported on an exhausted path. Repeating a seed repeats the same programmed path and supplies no independent evidence of fairness. The displayed probabilities come from the independent fair-bit model and its enumeration, not from the apparent balance of one short trace.

Understand

At each attempt, every person has probability 1/4 of being selected immediately, while rejection has probability 1/4. With a cap of three, A can win on attempt one, after one rejection, or after two rejections. These mutually exclusive cases have probabilities 1/4, (1/4)(1/4), and (1/4)²(1/4). Their sum is 16/64 + 4/64 + 1/64 = 21/64. The same argument applies to B and C. Three consecutive rejections have probability 1/64, so the four outcome probabilities sum to 3(21/64) + 1/64 = 1.

Conditional on a decision being made, A’s probability is (21/64)/(63/64) = 1/3, and similarly for B and C. Its unconditional chance is 21/64, not 1/3: the missing probability belongs to no decision. If exhaustion instead awarded the ticket to A, A’s chance would become 22/64 while the others remained at 21/64. Reporting exhaustion is therefore part of preserving the claimed symmetry.

For a cap n, no decision has probability (1/4)ⁿ. Each person has one third of the remaining probability, namely (1 − (1/4)ⁿ)/3. This follows either by adding the finite geometric series or by symmetry among the three accepted codes and subtracting the all-rejection probability. An uncapped procedure terminates with probability 1 because (1/4)ⁿ tends to zero, but it has no finite guaranteed attempt count. “Probability one” and “within a fixed budget” are different guarantees.

The expected number of attempts for cap three is 1 + 1/4 + 1/16 = 21/16. Every run reaches attempt one, one quarter reach attempt two, and one sixteenth reach attempt three. Adding those reach probabilities counts expected work without pretending that a fractional number of attempts occurs on a particular run.

Apply

Design a fair allocation among a number of people that does not divide the number of equally likely available codes. State the elementary random device, accepted codes, rejected codes, retry cap and exhaustion result. Prove that each person’s accepted-code probability is equal at every attempt, then explain why preceding rejections preserve equality. Include one successful trace and one exhausted trace.

Also distinguish equal chance from eligibility. A procedure can be perfectly symmetric among its listed people while excluding someone who should have been included. Conversely, a weighted allocation may deliberately give unequal chances for a stated reason. Describe the criterion you are evaluating rather than treating “fair” as a property established by a button. This teaching explorer is not a lottery service and does not certify an external source of random bits.

Continue

Bring your mapping, proof, cap and trace to the mixed practice. The key evidence is an argument about every possible path, together with an explicit account of the paths that do not decide. Finite computation helps inspect that argument; a few visually balanced runs cannot replace it.