Series

Expectation — the series

12 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. Waiting for all 6 kinds. One bar per new kind: the expected number of draws needed to see a kind not yet seen, rising as fewer of them are left, and adding to 14.70 draws in total.

    How long until every one turns up

    Draw at random from six equally likely kinds until all six have appeared. The wait is not six draws, and it is not sixty; it is fourteen point seven, and the number is a harmonic sum wearing a hat.

    part 1 · probability
  2. Waiting for all 6 when they are not equally likely. One bar per kind giving the expected wait for that kind on its own, with the rarest much the tallest, and the expected wait for the whole collection printed above them.

    The one that hardly ever comes up

    Make the kinds unequally likely and the tidy decomposition into stages fails, because a stage's rate now depends on which kinds turned up rather than on how many. What replaces it is an alternating sum over every subset — and the rarest kind turns out to be nearly the whole answer.

    part 2 · probability
  3. How long 4 equally likely patterns take to appear. A bar for each of 4 patterns of 3 coin tosses giving the expected number of tosses before it first appears, with the lengths at which each pattern overlaps itself listed.

    Two patterns, one chance, different waits

    HTH and HTT are equally likely in any given window of three tosses. Waiting for HTH takes ten tosses on average and waiting for HTT takes eight, and the difference is not about probability at all — it is about what a failed attempt leaves behind.

    part 3 · probability
  4. How much the first player can guarantee, as the coin's bias moves. A plot of the first player's best guaranteed winning chance in Penney's game against the probability of heads, a third on a fair coin and rising past one half only when the coin is heavily biased.

    A coin that lets the first player win

    On a fair coin the second player in Penney's game always has a better pattern than the first, and the first can hold them to no worse than two to one. Bend the coin and every overlap is paid for in the letters it uses: the replies change, the first player's share swings between a third and a half, and past a heads chance of 1/∛2 the first player simply names HHH and wins.

    part 4 · probability
  5. Three patterns that beat one another in a circle: HHHT, TTHH, HTTH. Three coin-toss patterns at the corners of a triangle with arrows showing which beats which in two-way races, and each pattern's chance of winning when all three race.

    Three patterns in a circle

    Race three coin patterns at once and the gamblers' accounting still gives each one's chance of arriving first — one fairness equation per pattern. What it does not give is any way to read the three-way result off the two-way ones. HHHT, TTHH and HTTH beat one another in a circle, and HHH loses both its head-to-head races and still finishes ahead of one of the patterns that beat it.

    part 5 · probability
  6. Records in a thousand draws, and the lengthening waits between them. A sequence of 1000 uniform draws on a logarithmic position axis, with records at positions 1, 6, 11, 27, 36, 145, 539, 927.

    A wait that ends and has no average

    Draw a number, then keep drawing until one beats it. Half the time the very next draw does. The wait is certain to end, it is usually short, and its average is infinite — and the chance of still waiting after n draws is exactly 1/(n + 1), whatever the numbers are drawn from, because symmetry is the only thing the calculation uses.

    part 6 · probability
  7. Running totals of random steps, stopped as they pass 4. Four staircases of uniform steps stopped on passing 4, taking 11, 8, 8, 10 steps; the exact mean is 8.666604.

    Two-thirds of a step past the line

    Add random numbers between nought and one until the total passes one, and it takes e of them on average. Ask the same about passing any t and the answer is an exact finite sum that settles, within a few units, onto the line 2t + 2/3. The slope is one over the average step. The two-thirds is the interesting part: it is what the one step that crosses the line charges for being chosen by its length, and it is set entirely by how much the steps vary.

    part 7 · probability
  8. The longest run of heads at three sizes, never the same shape. n=65536: 12:0.018 13:0.117 14:0.233 15:0.239 16:0.172 17:0.104 18:0.057 19:0.030 20:0.015; n=82273: 13:0.075 14:0.204 15:0.249 16:0.197 17:0.124 18:0.070 19:0.037 20:0.019; n=104408: 13:0.040 14:0.162 15:0.248 16:0.221 17:0.148 18:0.086 19:0.046 20:0.024 21:0.012.

    The longest run has no limit

    Toss a fair coin n times and the longest run of heads is about log₂ n. The average settles: it is log₂ n − 0.667 to within a few millionths by a million tosses. The distribution does not. Because the run is a whole number and log₂ n is not, the chance of each value swings round the same cycle once every doubling of n, for ever, and computing it exactly to a million tosses shows the swing as large at the end as at the start.

    part 8 · probability
  9. Four fractions staked on one run of tosses. p=0.6, 1000 tosses, 604 heads; final log10 wealth: Kelly 9.449, half Kelly 6.881, twice Kelly 0.409, everything ruined at toss 10.

    The best average is the worst bet

    A coin lands heads six times in ten and pays even money. Stake everything on every toss and the expected wealth grows by a fifth a toss — and the bettor is ruined at the first tail, which is certain to come. Stake a fifth of wealth each time instead and the average grows far more slowly, while the typical bettor grows faster than with any other fraction. The expectation is maximised by the strategy almost nobody should use.

    part 9 · probability
  10. Knowing the coin, learning it, and guessing it once. p=0.6, 2000 tosses; final log10 wealth: hindsight 19.30, knew p 19.25, learned 17.73, plug-in from 20 tosses (15 heads, f=0.50) -25.88.

    What not knowing the coin costs

    Kelly's rule stakes the edge, and the edge is the one thing a bettor never has. Estimate it from twenty tosses and stake the estimate, and a lucky start can turn a favourable coin into certain ruin. Learn it toss by toss instead, with Laplace's rule, and the cost of ignorance shrinks to a factor of about the square root of the number of tosses — because a bettor who learns is exactly a bettor who split the money among every fixed fraction at once.

    part 10 · probability
  11. What is left in the other box. Banach matchbox remainder distribution for N=50: means p=0.5: 7.0385, p=0.55: 9.9165, p=0.6: 16.1560; at p=0.5 P(0)=0.07959, P(1)=0.07959.

    The matches left in the other pocket

    A smoker keeps a box of fifty matches in each pocket and picks a pocket at random. When one box is found empty, the other holds about seven, and none and one are exactly equally likely. Favour one pocket by a tenth and the answer is sixteen; give each box five thousand matches and a fair choice leaves seventy-nine while a bias of one in a hundred leaves nearly two hundred — because a fair remainder grows like a square root and any bias makes it grow in proportion, with the change-over at a bias of one over the square root of the box.

    part 11 · probability
  12. Where a randomly broken stick can land. De Finetti's triangle of all ways to break a stick into three pieces, with 500 random breaks: the 118 in the shaded middle quarter, where every piece is shorter than half the stick, are the breaks whose pieces form a triangle.

    A stick broken in three

    Break a stick at two random points and the three pieces form a triangle one time in four — a fact that can be read off a picture without integrating anything, because the pieces are a point spread evenly over a triangle and the good breaks fill its middle quarter. With more pieces the same picture gives 1 − n/2ⁿ⁻¹, which is also the chance that n random points on a circle avoid every semicircle. But 'break at random' is ambiguous: cut once and then cut the longer piece, and the answer is 2 ln 2 − 1.

    part 12 · probability

All series