The Walker’s Night

It is midnight, and the power has failed. A person finds herself in the middle of a large room. She can’t see the walls or the doors, so all she can do is walk and hope. She takes one step at a time, choosing north, south, east or west at random (each with probability ¼). Whenever she runs into a wall she stays put, and on the next step makes a fresh random choice. Only a door lets her out.

The room has several doors. Which one will she leave by?

Take a moment and guess. Does the nearest door win? Does a wider one? What if the room were split in two by a narrow passage?

Every step is a random choice, yet the probabilities of leaving by each door are already settled by the shape of the room and the starting point. This piece is about the why.

The simplest room: a corridor

Consider a corridor consisting of cells numbered . The end cells and are doors, while the remaining cells form the room.

The corridor is one cell wide, so two of her four directions face walls: half the time she stays where she is, and otherwise she moves one cell left or right. The walk ends when she reaches either door.

Diagram of the corridor. Top: from cell k the walker moves to k+1 or k-1 with probability 1/4 each, and bounces off the walls with probability 1/2. Middle: the corridor of cells from door 0 to door N with the walker at cell k. Bottom: a graph of p(k) rising in a straight line from p(0) = 0 to p(N) = 1, so that p(k) = k/N.

Suppose she starts at cell , where . Define

First-step analysis. Conditioning on the first move, the walker either moves to , moves to , or stays at after hitting one of the two walls. Thus,

with boundary conditions and , since starting at a door means the walk has already ended.

Rearranging the equation,

Successive differences being equal makes the sequence an arithmetic progression with boundary values and . Solving the progression gives

Observation. The nearer door is more likely. Despite the randomness of individual steps, the probability of reaching the right door is a linear function of the starting position.

Widening the corridor

We now allow the walker to move in an actual room, made up of cells arranged on a square grid. Let be a finite, connected set of cells forming the room. The cells just outside — adjacent to it but not in it — are of two kinds: walls, which she cannot pass, and doors, which let her leave and end the walk. We denote the set of doors by .

The setup. Fix a group of doors , with . For a starting cell , define

At a door the walk is already over, so

For a room cell , we write

Each of the four directions leads to one or the other, so .

First-step analysis. From a room cell , she picks each of her four neighbours with probability . If the neighbour is accessible, she moves there, and the probability of eventually exiting through becomes . If it is a wall, she stays put and the probability remains . Then, by the law of total probability,

Multiplying by and moving the wall term across, we get

Dividing by 1, we obtain the averaging property:What if | 𝒪(x) | = 0?It never is. A cell walled in on all four sides would be sealed off from every door, which a connected room with a door does not allow. So at every room cell, and the division is always legal.

In words: every cell’s chance of leaving through is the average of its neighbours’ chances — four of them when no wall is in the way.

The same line can be read another way. Since does not depend on , adding it once for each of the accessible neighbours gives . Substituting that back,

that is,

Chance of leaving through the orange door, from each cell0.200.170.270.340.420.510.220.230.280.340.430.590.240.250.280.310.350.420.250.260.270.270.240.331door0door0doorSolid ring0.28 = ¼(0.27 + 0.28 + 0.23 + 0.34):the average of its 4 neighboursDashed ring0.34 = (0.34 + 0.27 + 0.42) ÷ 3:wall above, so only 3 accessible neighboursOrange door fixed at 1, other doors at 0.One local rule at every cell fixes all ofthese numbers.

Where does this lead? The sum , which we have just shown to vanish at every room cell, is called the graph Laplacian of at , written

A function whose graph Laplacian vanishes at every room cell is called discrete harmonic — equivalently, one whose value at every room cell is the average of its neighbours’ values. Our exit-probability function is one of them.What became of the walls?A blocked direction contributes , so drops out and the Laplacian never mentions walls. Bumping into them costs her time, not her destination.

Label each cell by its coordinates and write . At a cell with all four directions accessible, the equation reads

Pair the terms into two brackets, one along each axis:

Each bracket is a second difference2 — the grid version of a second derivative. So the equation is the lattice form of Laplace’s equation:Why is that a second derivative?The central difference scheme approximates the second derivative on a grid of spacing by with equality in the limit . Each bracket is that numerator.

The solutions of Laplace’s equation are called harmonic functions — the continuum counterpart of the discrete harmonic functions on our grid.

That single local rule is what the next section turns into global facts about the room.

Filling in the gaps

So far we have worked through some very interesting mathematics, but a good deal has been taken for granted. Before going further, we need to make sure the reasoning is solid.

Can the values escape the door values?

The maximum principle. If is discrete harmonic, then at every room cell ,3What is E?The set of all the doors.

A maximum inside forces its neighbours. is finite, so exists. If it is attained at a room cell , so that , then is the average of the values , , each of which is at most . An average of numbers at most equals only if every one of them equals . So

And it travels to a door. Take any door and a room cell adjacent to it. By connectedness there is a path of neighbouring room cells . The step above at gives , at gives , and so on to ; once more at gives . So the maximum sits at a door either way: carried there by the argument above if it is attained inside the room, or already at one if it is not. Hence

The minimum comes for free. The averaging condition is linear, so is discrete harmonic too, and applying the above to gives . 

Finiteness gives the maximum something to be attained at; connectedness is what carries it to a door.

Consequence. is discrete harmonic and each door value is or , so and . The principle therefore gives at every room cell.

Does she leave with probability 1?

Let be her position after steps, with . She stops at the first door she reaches, so the exit time is4

with if she never reaches one. We must show .What is T? is the step at which she first stands on a door — the moment the walk ends. The events and are therefore the same.

The function to look at. Write for the probability that she never leaves, and set at every door, which is correct since there.

It is discrete harmonic. First-step analysis applies to exactly as it did to : with probability each she picks a direction; if it leads to an accessible neighbour she moves there and the chance of never leaving becomes ; if it leads to a wall she stays and it is still . Hence

which rearranges, exactly as before, to say that is discrete harmonic.

is discrete harmonic and vanishes at every door, so by the maximum principle at every room cell; and , being a probability. Therefore . 

Consequence. Since with probability and she leaves by exactly one door, the chances of leaving by each door add up to :

They form a genuine probability distribution on the doors.

Is the answer unique?

Take the difference. Let and be discrete harmonic and agree at every door, and put . Averaging is linear, so is discrete harmonic, and at every door.

By the maximum principle and at every room cell. So , that is, . 

And a solution does exist: itself is discrete harmonic with those door values. So for the exit probabilities the answer exists and is unique.

Where we stand. Three questions settled, and with them the footing the rest of this needs.

Which door, then?

The equation can now be put to use on the questions we set out with. What follows is the solve, run on three experiments. Each changes one thing at a time and leaves everything else alone. The numbers are exact, not sampled.5How the numbers are foundEach room is solved from its linear system, which by uniqueness has one answer only. The probabilities in every room add to .

From here the nearer door winsADA0.61D0.39A is 3 steps away, D is 9.From here it does notADA0.60D0.40D is 12 steps away, A is 14.

Distance is not the answer. Intuition says the nearer door should win, and in the first panel it does. Move the walker and it may not. This is because a door’s position is as important as its distance; a corner is a place the walk seldom reaches, so D collects far less traffic than being nearer would suggest.

Two doors the same sizeABA0.50B0.50Both 6 steps away, both one cell.One door three times widerBABBA0.38B0.62Both 6 steps away; B is three cells.

Width counts, but not proportionally. Again we expect the wider door to win, and it does. The interesting part is how little the width buys: three times the door raises its share by only a quarter. Reaching that side of the room is the hard part; the extra cells only catch the near-misses.

A one-cell passageABA0.66B0.34Both doors 8 steps away.A three-cell passageABA0.55B0.45Both doors 8 steps away.

The room in between counts. The last pair differs only in the width of the gap; both doors stay eight steps away in each. Two extra cells of passage move more than a tenth of the probability across the room. What a passage restricts is not distance but traffic.

None of this is a theorem. But all three point the same way: no door’s distance or width settles the answer on its own — the shape of the whole room does.

One equation, many worlds

In electrical circuits.6What is S?The set of doors we are asking about — any non-empty part of . Replace every edge of the room by a one-ohm resistor, hold the doors of at one volt and the rest at zero, and let be the voltage at cell . Ohm’s law makes the current from to equal to , and Kirchhoff’s current law says the currents at an interior node sum to zero:

That is our equation, with our door values. By uniqueness : the voltage at a cell is the probability of leaving through a door of . Not an analogy — the same function.

The corridor is then resistors in series: voltage divides evenly along the chain, and falls out with no algebra.

In games of chance. The corridor is the gambler’s ruin problem — a player with chips betting on fair coin flips reaches before going broke with that same probability.

In the continuum. Shrink the grid spacing and, after rescaling, approaches . Fixing values on the boundary of a region and asking for the harmonic function inside is the classical Dirichlet problem — the same averaging property, the same maximum principle, and, on a bounded region, the same uniqueness. Solutions of it run all through physics: the steady temperature in a plate, the electrostatic potential where no charge sits. The walker’s room is that problem on a grid.

And in the walker herself. Her walk already solves the discrete problem. Shrink her steps and she becomes Brownian motion, which solves the continuous one: the value at a point is the expected boundary value at her first exit.

The roomwalls elsewhereprobability of leaving by a doorA metal platecold elsewheresteady-state temperatureA charge-free regionwalls groundedelectrostatic potentialdoorshot1 VDark is a value near 1, pale near 0.Three different questions, one equation — and it is the walker’s equation.

One question about a dark room has carried us through probability to the Laplacian, and from there to a circuit and a warm plate. The idea underneath keeps surfacing wherever anyone looks closely.