Glossary / Random walk
A man leaves a bar and at every crossroads turns whichever way he likes. Mathematics guarantees that sooner or later he will be standing at his own door. But a bird flying just as randomly forward, sideways, up or down may never come back. The only difference is one dimension. George Pólya proved it in 1921, and the mathematician Shizuo Kakutani summed it up: "A drunk man will eventually find his way home, but a drunk bird may get lost forever."
“In plain words” is hidden on all puzzles.
Each walker starts at home, in the centre, and at every step moves to a neighbouring cell at random: left or right on a line, one of four directions on a plane, and also up or down in space. Whoever steps on home is back. Release 100 walkers into each world and give them 10,000 steps each.
On a line there is nowhere to go: the walker shuffles around home and sooner or later steps on it. On a plane there is more room and the return takes longer, but it is still certain, you just wait longer. In space there are so many directions that a walker who has wandered off mostly reaches new places rather than old ones. So a third come back quickly, and the rest most likely never do.
Pólya became interested during walks in the woods outside Zurich. He kept running into the same student and his fiancée, felt embarrassed that it looked like snooping, and wondered: how often do people who wander at random meet?
“Rigorous” is hidden on all puzzles.
A random walk on a line: start at zero, and each step is +1 or −1 with probability 1/2, independently of the earlier ones. The position after n steps is just the sum of those steps. For example, two steps give four equally likely outcomes:
On average the walker stays put: the mean position is 0. But the squared distance averages (4 + 0 + 0 + 4) / 4 = 2, exactly the number of steps. That is no coincidence, and everything else follows from it.
It seems twice as many steps should take you twice as far. No: the steps mostly cancel each other out. The typical distance from the start after n steps is about √n. After 100 steps that is roughly 10, after 10,000 steps only about 100. Below are 200 walkers on a line: time runs to the right, position goes up or down.
The typical distance here is the square root of the mean squared distance of all 200 walkers. The dashed lines are ±√n.
Olena and Bohdan toss a coin 1,000 times: heads is a point for Olena, tails for Bohdan. The score between them is exactly a random walk. It seems the lead should keep changing hands and each of them should be ahead for about half the game. In fact an even split is the least likely outcome, and most often one of them leads nearly all the time.
Histogram: the share of tosses during which Olena is ahead, over all games played. A toss on which the score becomes level or stops being level goes to whoever leads at its other end.
“Deeper” is hidden on all puzzles.
Sn = X₁ + X₂ + … + Xn, E[Sn²] = Σ E[Xi²] + Σi≠j E[XiXj] = n · 1 + 0 = n
Each squared step equals 1, so the first sum gives n. The cross products XiXj are +1 and −1 equally often, because the steps are independent, and they vanish on average. So the variance of the position is n, and the typical distance is √n. The plain average distance is a bit smaller: E|Sn| ≈ √(2n/π) ≈ 0.8 √n.
Take some steps in the simulation with 200 walkers, and their numbers will appear here.
P(ahead for 2k of 2n tosses) = C(2k, k) · C(2n − 2k, n − k) / 2²ⁿ
P(share of time ahead ≤ x) → (2/π) · arcsin √x
The first formula is exact for a game of 2n tosses. The largest probabilities belong to the extremes k = 0 and k = n, the smallest to the middle. The second formula is its limit for long games, hence the name. The probability that someone leads at least 90% of the time tends to 2 · (1 − (2/π) · arcsin √0.9) ≈ 0.410, and for exactly 1,000 tosses it is 0.413. A balanced split between 40 and 60% happens with probability only ≈ 0.129.
Play some games in the simulation above, and your shares will appear here.
Probability of ever getting home: line 1, plane 1, space ≈ 0.3405
Let p be the probability of ever coming back. After each return the walk starts afresh, so the average number of visits home, counting the start, is 1/(1 − p). On the other hand, it is the sum of the probabilities of being home at each step. After 2n steps that probability is about:
line 1/√(πn) · plane 1/(πn) · space 2 · (3/(4πn))3/2
The first two sums are infinite, so 1/(1 − p) is infinite and p = 1. The second grows only like a logarithm, which is why the plane brings walkers back so slowly: within 10,000 steps only about 74%. The third sum is finite, equal to 1.516…, so p = 1 − 1/1.516 ≈ 0.3405. Within 10,000 steps about 33.7% come back in space, nearly everyone who will ever return. In four or more dimensions walkers return even less often.
Release walkers in the first simulation, and your totals will appear here.
The middle value: line everyone up in order, and half are below it, half above.
A millionaire walks into a bar: the average income shoots up, the median barely moves.
The sum of all values divided by how many there are: what everyone would get if it were shared equally.
Almost everyone has more legs than average: the average is a little under two.
The average result you can expect if you repeat the same thing very many times.
A die's expected value is 3.5, yet no face shows 3.5.
A number from −1 to +1 showing how closely two quantities move together.
In summer both ice cream sales and drownings go up. Ice cream isn't to blame: the heat drives both.
A measure of spread: how far values typically stray from the mean. The standard deviation is its square root, in the same units.
Two towns with the same average temperature: one stays near +15 all year, the other swings from −20 to +50.
A bell-shaped distribution: most values sit near the mean, and the further away, the rarer.
Every ball on a Galton board falls at random, yet thousands of balls always build the same bell.
The more repetitions, the closer the share of an outcome gets to its true probability.
The share of heads creeps towards 50%, while the gap between heads and tails in coins usually grows.
The chance of an event given that something else is already known.
Almost all NBA players are tall, but almost all tall people are not NBA players.
Events are independent if knowing about one doesn't change the chances of the other.
After five heads in a row tails is no more likely: the coin remembers nothing.
How many times you multiply the base by itself to get a number: log₂ 8 = 3, because 2 · 2 · 2 = 8.
A sheet of paper folded in half 42 times would be thicker than the distance to the Moon.
A sample some people get into more easily than others, so it describes everyone badly.
In 1936 a magazine polled millions of Americans and still picked the wrong election winner.
How often chance alone would produce a gap at least as big as yours if there were really no difference.
When there is no effect at all, p below 0.05 turns up as often as p between 0.50 and 0.55.
A range around a measured number, built by a method that covers the true value in a chosen share of samples, such as 95%.
Of twenty honest 95% intervals, on average one misses the truth, and none of them knows whether it is the one.
The probability that a test notices a real effect of a given size. A power of 80% means the test misses one working effect in five.
A weak A/B test that does find an effect almost always exaggerates it: a real +10% shows up on the dashboard as +24%.
How far an average or a rate computed from a sample usually misses the truth: σ divided by the square root of the sample size.
Halving the error takes four times as much data.
Counting how many ways things can be ordered or chosen: permutations n!, combinations C(n, k).
A well-shuffled deck is almost certainly in an order nobody has ever seen.
The sum 1 + ½ + ⅓ + ¼ + …: it grows without limit, but incredibly slowly.
Identical books can be stacked so the top one overhangs the table edge as far as you like.
The rule for updating confidence when new evidence arrives: prior odds × strength of the evidence.
Two weak pieces of evidence together can be strong, while one striking piece means little if the claim was unlikely.
Growth where a quantity is multiplied by the same factor each time, so it doubles at equal intervals.
One grain on the first square of a chessboard, doubling on each next one: the last square holds as much rice as the world grows in over 300 years.
A stream of independent random events at a constant average rate: calls, Geiger clicks, raindrops.
In 1944 Londoners thought German flying bombs were aimed at certain districts; it was ordinary random clumping.