random-walk-is-binomial

Fri Jul 03 2026

The Problem

A particle starts at 0 on the number line and takes $n$ steps. Each step is $+1$ or $-1$ with equal probability. After $n$ steps, what is the distribution of its position?

I worked it out by hand for the first few $n$. Some things jumped out of those $P_{X_1}, P_{X_2}, P_{X_3}$ tables:

• After 1 step it sits on $\pm 1$. After 2 steps, only even positions. After 3 steps, only odd positions. The reachable set flips parity with $n$.
• Each distribution is symmetric about 0, with the most mass near 0 and less toward the edges.
• It looked like a bell, or like the triangle you get from summing two dice, which peaks at 7.

What I could not do was jump to general $n$. Redoing the tree for every $n$ is hopeless. I needed the position's PMF as a formula, and I did not see how to get there.

Where I Got Stuck

Those tables were positions: $X_1$ the position after one step, $X_2$ after two, $X_3$ after three. I was treating each one as a random variable whose distribution I did not know, and grinding it out by hand with a tree. The instinct was to keep going the same way for general $n$: build $X_n$'s table too, so $Y = X_n$.

That is the trap. Each new step splits every position into two, so the tree doubles and after $n$ steps the bookkeeping explodes. Redoing it for every $n$ is hopeless, and it hands me no formula for $P(X_n = y)$. I was trying to compute the position's distribution in one piece, directly, instead of building it from simpler pieces I already understood.

The Reframe: Count Rights, Not the Running Sum

The way out is to build the position from simple pieces instead of computing it whole. Let $X_i$ be the $i$-th step, $+1$ for a right and $-1$ for a left (reusing $X_i$, now for the step itself rather than the running position). Each step is a trivial fair two-outcome trial, and the position is just their sum:

$Y = X_1 + X_2 + \dots + X_n, \qquad X_i \in \{-1, +1\}.$

This is the reframe. Adding up $n$ independent identical fair steps builds a Binomial, so $Y$ is a Binomial in disguise and I never have to grind out its distribution by hand: I know one step, and $Y$ is $n$ of them summed. Whether I write a step as right or left, $+1$ or $-1$, or a $0/1$ indicator, is just notation for the same coin. What is left is bookkeeping to pin down exactly which Binomial.

That bookkeeping is cleanest if you stop tracking the running sum and count the two kinds of step instead. Let $R$ be the number of right steps and $L$ the number of left steps. Two facts then pin down everything:

$n = R + L, \qquad Y = R - L.$

The first says every step is either a right or a left. The second is the position, since each right adds 1 and each left subtracts 1.

Now $R$ is easy to name. Over $n$ independent steps, each going right with probability $1/2$, $R$ is a count of successes in $n$ fair trials. So $R \sim \text{Bin}(n, 1/2)$ and

$P(R = r) = \binom{n}{r} \left(\tfrac{1}{2}\right)^{r} \left(\tfrac{1}{2}\right)^{n-r} = \binom{n}{r} \frac{1}{2^{n}}.$

Both probabilities are $1/2$, so $p^{r}(1-p)^{n-r}$ collapses to $1/2^{n}$ no matter what $r$ is. The entire shape of the distribution is carried by the count $\binom{n}{r}$ alone.

From R to the Position y

I still had the probability in terms of $R$, not the position $y$ I actually care about. The same two equations bridge them. Adding $n = R + L$ and $Y = R - L$ drops $L$ and gives $R = \frac{n + y}{2}$. Landing at position $y$ forces exactly $\frac{n+y}{2}$ of the steps to have been rights. Substitute:

$P(Y = y) = \binom{n}{\frac{n+y}{2}} \frac{1}{2^{n}}.$

That is the whole PMF. Two constraints fix its domain, and they explain the parity pattern I had noticed by hand:

• Parity. The count $\frac{n+y}{2}$ has to be a whole number, so $n + y$ must be even, so $y$ shares the parity of $n$. Even $n$ lands on even positions, odd $n$ on odd positions, and off-parity positions get probability 0.
• Range. The number of rights runs $0 \le \frac{n+y}{2} \le n$, which is just $-n \le y \le n$. You cannot get further from 0 than the number of steps you took.

The textbook runs the same derivation in its random walk example (Example 3.7.2 in the 2nd edition), writing the position as $Y = 2X - n$ with $X \sim \text{Bin}(n, 1/2)$ counting the right steps. That is the same $R - L$ in different letters, since $X = R$ and $n - X = L$.

Quick check against my hand tables: for $n = 3$, $P(Y = 1) = \binom{3}{2}\frac{1}{8} = \frac{3}{8}$, exactly the $3/8$ I had written for position 1 under $P_{X_3}$.

The Click: One Shape, Three Disguises

Once the PMF is $\binom{n}{(n+y)/2} / 2^{n}$, the bell stops being a surprise. The $1/2^{n}$ is a constant. The whole shape is the binomial coefficient $\binom{n}{k}$ swept across $k$, and I already knew that coefficient peaks in the middle and drops off toward the ends.

Why the coefficient peaks

Two arguments, and the second is the one worth keeping.

Symmetry rules out a monotonic slide. Choosing $k$ items to take is the same as choosing the $n - k$ to leave behind, so $\binom{n}{k} = \binom{n}{n-k}$. The values at $k$ and $n-k$ match, which forces a symmetric hump rather than a curve that just keeps falling.

The ratio test says where the hump turns over. Compare one coefficient to the next:

$\frac{\binom{n}{k+1}}{\binom{n}{k}} = \frac{n-k}{k+1}.$

While this ratio is above 1, the sequence is still climbing. Setting $\frac{n-k}{k+1} \ge 1$ rearranges to $n - k \ge k + 1$, that is $k \le \frac{n-1}{2}$. So the coefficients grow up to about the middle and shrink after it. For even $n$ there is a single peak at $k = n/2$. For odd $n$ the ratio equals exactly 1 at the center, so the two middle values tie.

The same shape everywhere

Map that back to the walk. The count of rights is $k = \frac{n+y}{2}$, and $\binom{n}{k}$ is largest at $k = n/2$. Setting $\frac{n+y}{2} = \frac{n}{2}$ gives $y = 0$. The most likely place to end up is where you started, with the probability decaying symmetrically toward $\pm n$. That is the same peak, relabeled from "number of rights $k$" to "position $y$".

It is also the same shape as summing two dice. There, middle sums like 7 have many more combinations ($1{+}6, 2{+}5, 3{+}4, \dots$) than edge sums like 2, which only comes from $1{+}1$, so mass piles up in the center.

Worth pinning down what that dice sum actually is. With $X$ and $Y$ the two dice, $X + Y$ is not a Binomial. A die is uniform on $\{1, \dots, 6\}$, not a Bernoulli, so the sum is a triangular distribution, the convolution of two uniforms, which is why its plot has straight sides rather than a smooth hump. It shares the Binomial's shape through the mechanism, not the formula: both are sums of independent identical pieces, and summing independent pieces piles mass in the middle, since more input pairs land on the central values. The walk lands on the Binomial exactly because its pieces are $\pm 1$ Bernoulli steps, while the dice sum lands on a triangle because its pieces are uniform. Same family, different members.

Binomial coefficients, dice sums, and the random walk are the same peaked, symmetric object wearing different labels. The random-walk PMF is a relabeled $\text{Bin}(n, 1/2)$, and nothing more. The reason it keeps smoothing toward a cleaner bell as $n$ grows has a name, the Central Limit Theorem: a sum of many independent identical pieces tends toward a bell whatever the pieces look like, and the walk is exactly such a sum.

Aside: y on Both Sides Is Fine

For a while the formula bothered me because $y$ shows up on the left and the right of $P(Y = y) = \dots$. That looked like an equation I should solve for $y$. It is not. $P(Y = y)$ is a function definition, read as "the probability that the random variable $Y$ takes the specific value $y$". Capital $Y$ is the random variable, lowercase $y$ is a particular number you plug in, and the PMF is often written $p_Y(y)$ to make that explicit. It is no stranger than $f(x) = x^2$ having $x$ on both sides. That capital-vs-lowercase split is exactly the machinery behind probability-distributions-and-random-variables.