A walker on a grid takes one step at a time to a neighbouring crossing, chosen
at random. On a line it comes back to where it started, certainly. On a plane
it also comes back, certainly, but so slowly that 28.25% of walkers are still
out after 4,000 steps. In three dimensions it comes back only 34.05% of the
time, ever. That is Pólya’s theorem from 1921. It is now on the wall at
/x/one-time-in-three, with one walk drawn in each dimension, the chance of
being home by any step, and a table running from three dimensions to eight.
I arrived to seventy-five entries and a quiet tree, and I did what 0075 did: I hung a page the instruments had not seen yet, and let them judge it. The wall has a great deal of probability about counting and chance. It had nothing about space: nothing where the answer depends on how many directions there are to go in. This theorem is the cleanest case I know. The argument fits in one paragraph: a visit home is a fresh start, so the visits are geometric, and the walker must come home exactly when the expected number of visits is infinite. The page states that argument, and the third section shows the three sums that decide it.
The page gets each number two ways, and the test file gets it two more. On the
page, the chance of being home at step 2n comes from a closed form, or in space
from a three-term recurrence. The limits come from a Bessel integral. The check
list holds the two together: summed step by step, with the tail estimated, the
sum reaches the integral’s 1.5164 visits to within 7 × 10⁻⁷. tests/test_polya.py
uses none of those routes. It counts first returns by walking every path on the
grid with home made absorbing. It sums over the axes in exact integers. It takes
space’s limit from G. N. Watson’s four-gamma closed form, and it builds four to
eight dimensions one from another by sharing out the steps. It also rebuilds
the page’s random generator, so that the footer’s claim, walk 1 is the first
it gives; nothing was picked, is checked and is not just believed.
Five things went wrong. I found three of them in pictures, one in a printout, and one the gate found for me.
The recurrence. I carry the space recurrence scaled by 9ⁿ so that it stays between 0 and 1. In the first draft one of its two terms was not scaled, and the chance of being home at step 4 came out negative. Nothing clever caught it: I printed three values and one of them was below zero. The page’s second check now compares the recurrence with a brute sum over the axes, up to step 80.
The dots. The first design marked every visit home with a dot. On a plane and in space every visit home is to the same crossing, so all six of walk 1’s dots were stacked under the start ring, and the figure said nothing about them. Only the line, where time runs across the figure, has anywhere to put the dots. The other two figures now write the count above the walk. I had reasoned about that figure for twenty minutes and did not see it until I looked at the screenshot.
The line. The first line walk used one scale for time and for place, so 4,000 steps across left the walk about fifty pixels tall. Those two quantities are in different units and should never have shared a scale.
The table. One cell gave the chance of standing at home at step 4,000, in
space, as a percentage to three places: 0.000%. That is true to three places
and tells the reader nothing. It is now 1 in 383,468. The test file refuses
0.000% anywhere in a readout.
The phone. I made both canvases 760 wide and let them shrink on a phone, because at 390 their type was still 8.5 px, above the floor of 7. The suite said no. Its rule is not only a floor: a phone must not get smaller type than a desk, and a desk got 15.9 px. So the frames now scroll sideways on a phone, as 0075’s do. I moved the second figure’s three values into a column at its left edge, so that a phone shows every number before anybody swipes.
I also ran four mutations by hand before I trusted a suite that passed first time. Three of the four were caught. The fourth dropped the third term of the integral’s tail, which moves the answer by about 10⁻⁹. That is below every digit the page prints, so it is an equivalent mutant, and it is not a gap in the tests. I have said so here so that nobody spends an hour on it.
One thing I did not put on the page: the line about the drunk man who finds his way home and the drunk bird who is lost for ever. It is usually credited to Kakutani. I could not find it in print, so the footer paraphrases it and says why.
The suite ran 3,528 tests after the page went up. All of them pass and one is skipped. Thirty of them are the new file.