How Random Is Random? Fair Ways to Pick Teams • The Science 360

In 2010 Microsoft's browser ballot screen for Windows listed five web browsers in what was meant to be a random order. The code shuffled the list by sorting it with a comparison that returned a random answer. When Rob Weir ran that code 10,000 times, Internet Explorer came last 5,034 times. A fair shuffle would put it last about 2,000 times, one in five. Nobody had cheated; the method was simply biased.

The same quiet bias turns up whenever someone shuffles a class list with a few lines of code. This post works out, by exact counting, how three common shortcuts go wrong and what a fair shuffle does instead. The random group generator uses the fair method to split a class into groups or teams, entirely in your browser.

Quick answerA fair way to pick teams gives every possible split the same chance. Shuffle the full list with the Fisher-Yates method, using unbiased random numbers, then deal the names into groups in order. Sorting with a random comparison, swapping each name with any position, and taking a random number's remainder all favour some outcomes over others.

What does fair mean when you split a class into groups?

Fair has a precise meaning here: every way of splitting the class should be equally likely. That is stronger than "everyone gets a group". It means no student is more likely to sit with any particular classmate than with any other, and no group is more likely to get the first names on the list.

One handy consequence is a number you can check. Pick any student. In equal groups of size $s$ they have $s-1$ seats beside them, filled from the other $n-1$ students, each equally likely to be there. So the chance that a given friend joins them is a simple fraction.

Example 1: two friends in a class of 30

\begin{aligned} P(\text{same group}) &= \frac{s-1}{n-1} \\ \text{6 groups of 5:}\quad &\frac{4}{29} = 13.8\% \\ \text{2 teams of 15:}\quad &\frac{14}{29} = 48.3\% \end{aligned}

In pairs the chance falls to 1 in 29, or 3.4%. If two friends keep landing together much more often than this over many lessons, the method is not fair.

The number of different splits is enormous. For 30 students into 6 unlabelled groups of 5, count every order of the 30 names, then divide out the orders inside each group and the order of the groups themselves.

Example 2: how many ways to make 6 groups of 5

\begin{aligned} \frac{30!}{(5!)^6 \times 6!} &= 123{,}378{,}675{,}083{,}039{,}376 \\ &\approx 1.23 \times 10^{17} \end{aligned}

Drawing a fresh split every second, you would need nearly 4 billion years to see each one once.

A classroom with six tables of five students, each student with a folded name card in the group colour, under a whiteboard that reads 6 groups, 30 students — Figure 1. Thirty students dealt into six groups of five after a Fisher-Yates shuffle. Any two of them share a table with chance 4 in 29. Open this in the generator.

How does the Fisher-Yates shuffle work?

Ronald Fisher and Frank Yates described the method in 1938 in their book of statistical tables, as a pencil and paper procedure with a table of random digits. Richard Durstenfeld gave the version computers use in 1964, and Donald Knuth made it famous in The Art of Computer Programming.

The computer version is short. Start at the last name. Pick a random position from the first one up to and including the current one, and swap the two names. Then move one step towards the front and repeat, each time choosing only among the names not yet fixed in place. When you reach the front, the list is shuffled.

Why it is fair comes down to counting. For the last position there are $n$ choices, then $n-1$ , and so on down to 1. That gives $n!$ equally likely runs, and each run produces a different order. There are exactly $n!$ orders, so each one comes up exactly once.

Example 3: three names

3 \times 2 \times 1 = 6 \text{ runs} \quad\text{and}\quad 3! = 6 \text{ orders}

One run per order, so each order has a chance of exactly 1 in 6, 16.7%. With 30 names there are about $2.65 \times 10^{32}$ runs, still one per order.

Once the order is fair, dealing it into groups keeps it fair. Every split of the class is produced by the same number of orders, namely the ways to rearrange people within their groups and to rearrange equal-sized groups, so every split is equally likely too.

Why is swapping each name with any position biased?

The most common mistake looks almost identical to Fisher-Yates. Go through the list and swap each name with a position chosen from the whole list rather than only from the part not yet fixed. It feels more random. It is actually less fair.

Count again. Each of the $n$ steps has $n$ choices, so there are $n^n$ equally likely runs. Those runs have to share out among only $n!$ orders, and for three or more names $n^n$ does not divide evenly by $n!$ . Some orders must get more runs than others.

Example 4: counting every run for 3 and 4 names

\begin{aligned} n = 3:\quad 3^3 &= 27 \text{ runs for } 6 \text{ orders} \\ \text{three orders get } 5 &\text{ runs: } \tfrac{5}{27} = 18.5\% \\ \text{three orders get } 4 &\text{ runs: } \tfrac{4}{27} = 14.8\% \end{aligned}

Fair would be 16.7% each. With four names there are 256 runs for 24 orders, an average of 10.7 each, but the actual counts run from 8 to 15. The commonest order is nearly twice as likely as the rarest.

Those counts come from walking through every run, so they are exact, and nothing in the output warns you.

Why does sorting with a random comparison fail?

This is the browser ballot method. A sort asks over and over whether one item should come before another. Give it a coin flip instead of a real answer and the result depends on how that particular sort is written. Weir found that the same code gave a different bias in Internet Explorer and in Firefox, because the two browsers sorted differently.

You can work it out exactly for a simple case. Take insertion sort, which places each new name by comparing it with the names before it, moving it left until a comparison says stop. With a fair coin for each comparison, every sequence of flips has a known chance, so the chance of each final order can be added up.

Example 5: insertion sort with a coin flip

\begin{aligned} \text{3 names, unchanged:}\quad &\tfrac{1}{4} = 25\% \\ \text{4 names, unchanged:}\quad &\tfrac{1}{8} = 12.5\% \\ \text{4 names, rarest:}\quad &\tfrac{1}{64} = 1.6\% \end{aligned}

Fair would be 16.7% for each order of three names and 4.2% for four. With four names the list stays exactly as it was three times as often as it should. The name typed last ends up at the front only if every coin flip says move, which is why later names tend to stay near the end.

Spreadsheet users have a related habit: add a column of random numbers and sort by it. That one is fine, as long as the random numbers are fresh and ties are rare. It is a slow Fisher-Yates in disguise, because sorting by independent random keys gives every order the same chance.

What is modulo bias?

Computers make random whole numbers in a fixed range, such as 0 to 255 for one byte. To pick one of 30 names, the quick trick is to take the remainder after dividing by 30. The trouble is that 256 is not a multiple of 30.

Example 6: one random byte, 30 names

\begin{aligned} 256 &= 8 \times 30 + 16 \\ \text{names } 0 \text{ to } 15:\quad &\tfrac{9}{256} = 3.52\% \\ \text{names } 16 \text{ to } 29:\quad &\tfrac{8}{256} = 3.13\% \end{aligned}

The first 16 names on the list are each one eighth more likely to be picked than the last 14. Alphabetical lists make that a bias towards names early in the alphabet.

The fix is to throw away the values that cause the uneven leftover. Here that means discarding 240 to 255 and drawing again, which happens one time in 16. The generator does the same with 32-bit random numbers from the browser's crypto.getRandomValues function, where the leftover is tiny but is still rejected rather than ignored. That function is designed for cryptography, so its numbers cannot be predicted by anyone watching the screen.

Are names from a hat or counting off fair?

Names from a hat can be fair if the slips are the same size and properly mixed, which is harder than it sounds when they went in in register order.

Counting off 1, 2, 3, 4 around the room is not random at all. It is a fixed rule applied to the seating plan. Two friends sitting side by side are certain to be split up, and two students four seats apart are certain to be together. That can be exactly what a teacher wants, but the chance of a pair sharing a group is 0 or 1, never 4 in 29.

Captains picking teams is not random either, and the same students wait to be chosen last every week.

How do you keep two students apart without breaking fairness?

Sometimes two students should not work together. The tempting fix is to shuffle, and if they land together, move one of them to another group. That shifts probability towards the arrangements the move tends to create, so some allowed splits become more likely than others.

The clean method is to reshuffle the whole class until the rule holds, and keep the first shuffle that passes. This is called rejection sampling. Every arrangement that keeps the pair apart had the same chance in the original shuffle, and throwing away the rest does not change that, so the survivors stay equally likely.

It is also quick. With 5 groups of 6, any one pair lands together 5 times in 29, or 17.2%. For three pairs, a simulation of 200,000 shuffles found all three apart 56.9% of the time, so the generator needs 1.76 shuffles on average and rarely more than a handful.

Thirty students in five random groups of six, shuffled again until three pairs who should not work together are all at different tables — Figure 2. Five groups of six with three keep-apart pairs. The generator reshuffles until no pair shares a table, which keeps every allowed split equally likely. Open this in the generator.

What happens when the class does not divide evenly?

Thirty students in groups of 4 leaves two over: make 7 groups with two of them a student bigger, or 8 groups with two a student smaller. Neither is more random, so the generator lets you choose. Split by a number of groups and sizes differ by at most one.

Group size changes the chance of friends sitting together more than most people expect. Here is a class of 30 split eight ways; 6 × 5 means six groups of five.

Setting	Sizes	Friends together	Splits
Pairs	15 × 2	3.4%	6.19 × 10¹⁵
Groups of 3	10 × 3	6.9%	1.21 × 10¹⁸
Groups of 4, some bigger	2 × 5, 5 × 4	11.5%	9.64 × 10¹⁸
Groups of 4, some smaller	6 × 4, 2 × 3	9.7%	2.68 × 10¹⁹
6 groups	6 × 5	13.8%	1.23 × 10¹⁷
5 groups	5 × 6	17.2%	1.14 × 10¹⁶
3 groups	3 × 10	31.0%	9.25 × 10¹¹
2 teams	2 × 15	48.3%	7.76 × 10⁷

For unequal groups the "friends together" figure is the sum of $s(s-1)$ over the groups, divided by $n(n-1)$ . Splitting into two teams makes it close to a coin toss whether a given friend is on your side.

Thirty students split at random into fifteen pairs, two at each small table with name cards in fifteen different colours — Figure 3. Thirty students in fifteen random pairs. Each student's partner is any one of the other 29 with equal chance, 3.4% each. Open this in the generator.

Does it matter for a classroom?

For one lesson, a biased shuffle will not be noticed. Over a year it adds up: with a method that favours the original order, register neighbours are grouped together more often than chance. Students notice patterns like that. A class list is also personal information, so the generator shuffles in the browser, never sends the names anywhere and never puts them in its link.

Try it yourself

Open the random group generator with three keep-apart pairs, paste your own class list, and press Re-roll a few times to watch different splits appear. Switch between a number of groups and a group size, then copy the groups, print them or download a CSV for your spreadsheet. If you like seeing probability worked out from first principles, the 100-year flood analysis applies the same counting to rare events, sorting without a sort function shows how simple sorts move items around, and the ninth Dedekind number is a reminder of how fast counting problems grow.

Sources

Wikipedia, Fisher-Yates shuffle: history (Fisher and Yates 1938, Durstenfeld 1964, Knuth’s Algorithm P), the naive swap and its 27 outcomes for three items, modulo bias and the random comparator.
Rob Weir, Doing the Microsoft shuffle: algorithm fail in browser ballot (2010): a comparison returning 0.5 minus a random number, and Internet Explorer last in 5,034 of 10,000 runs.
MDN Web Docs, Crypto: getRandomValues() method: random numbers suitable for cryptographic purposes from a generator seeded with enough entropy.
Exact counts in this post (the 27 and 256 runs, the insertion sort chances, the modulo bias and the numbers of splits) were worked out by enumerating every case in the generator’s own code.

Frequently asked questions

What is the fairest way to split a class into random groups?

Shuffle the whole list with a proper method such as the Fisher-Yates shuffle, then deal the names into groups in order. Every way of splitting the class is then equally likely, and any two students share a group with the same chance.

What is the chance two friends end up in the same group?

For equal groups it is (group size minus 1) divided by (class size minus 1). In a class of 30 split into 6 groups of 5, that is 4 in 29, or 13.8%. For two teams of 15 it is 14 in 29, or 48.3%.

Why is sorting with a random comparison not a fair shuffle?

A sort assumes its comparisons are consistent. Random answers make the result depend on how the sort works, so some orders come up far more often. With insertion sort and four names, the original order appears 1 time in 8 instead of 1 in 24.

Does keeping two students apart make the groups less random?

Not if you reshuffle until the pair is apart. Throwing away the shuffles that break the rule leaves every allowed arrangement equally likely. Moving one student by hand afterwards does make some arrangements more likely than others.

Is counting off 1, 2, 3, 4 around the room random?

No. It depends entirely on where people sit. Two friends next to each other are guaranteed to be split up, and students sitting four seats apart are guaranteed to be together.