Putting It Back, or Not

Last timeWhen Order Does Not Matter

Drawing with the item returned each time gives a power; drawing without gives a falling product. The two answers agree when the pile is large and diverge alarmingly when it is not.

Draw three items from a pile of ten. How many outcomes are there?

The question is not yet answerable, because one thing has not been said:

whether each item goes back before the next draw. The two answers are different

and both are produced by the multiplication rule.

FIG 1The two counts, side by side

: how many items are in the pile at the start
: how many draws are made
: the count when each item is returned. Every stage sees the same pile, so every stage offers n options
: the count when items are kept out. Each stage has one fewer option than the last, and the product has exactly k factors

Three from ten gives a thousand with replacement and seven hundred and twenty without, a gap of about twenty eight per cent. Both counts treat the order of the draws as meaningful; if it does not matter, the second is divided by the orderings to give the choose count of the previous lesson, and the first needs a different and much less common formula that this course does not use. The two numbers to keep straight are the base, which is the size of the pile, and the exponent or number of factors, which is the number of draws.

How far apart they get

The interesting behaviour is not either count on its own but the ratio between

them, because that ratio is exactly the chance that no item came up twice.

FIG 2Drawing k times from a pile of 365, both ways

	draws k	with replacement	without replacement	ratio: chance of no repe
a handful	5.000000	6480000000000.000000	6400000000000.000000	0.973000
a small group	10.000000	4.2e+25	4.16e+25	0.883000
a classroom	20.000000	1.77e+51	1.68e+51	0.589000
the crossover	23.000000	8.6e+58	8e+58	0.493000
a lecture hall	40.000000	6.3e+102	5e+102	0.109000
a large hall	60.000000	1.8e+154	7.2e+153	0.006000

The two counts are enormous and nearly equal at the top, and the only readable column is the last one. At five draws the chance of no repeat is ninety seven per cent, which matches intuition. At the marked row, twenty three draws from three hundred and sixty five, it has fallen below a half: in a room of twenty three people it is more likely than not that two share a birthday. At sixty the chance of no shared birthday is under one per cent. Nothing surprising is happening in the counting, which is why this result belongs here rather than in a chapter on paradoxes; what is surprising is how few draws it takes, and that is the subject of the seventh lesson.

The reason the gap arrives so early is that the number of chances for a repeat

is the number of pairs of draws, not the number of draws. Twenty three draws

make two hundred and fifty three pairs, and each pair has one chance in three

hundred and sixty five of matching. The pair count grows with the square of the

number of draws, which is why doubling the draws roughly quadruples the chance

of a collision.

The lesson stops here

2 more paragraphs to go

You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.

The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.

See the plan The contents

This is the reading half

Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.

The contents

Putting It Back, or Not

How far apart they get

2 more paragraphs to go

This is the reading half

Read alongside