Take a random walk on Pascal's triangle, without revisits: Does the final number have infinite expectation?

Question

Let's take a random walk on Pascal's triangle, starting at the top. Each number is in a regular hexagon. At each step, we can move to any adjacent hexagon with equal probability, but we cannot revisit a hexagon. The walk ends when we cannot move.

Here is an example in which the final number is $15$.

Does the final number have infinite expectation?

(Paradoxically, a random variable whose possible values are all finite, can have infinite expectation.)

My thoughts

I suspect the answer is yes, because as we move down Pascal's triangle, the numbers quickly become very large. But I don't know how this could be proved.

After some step, if we find ourselves in "open territory" (no previously visited hexagons nearby), then there is a sequence of five moves that would end the walk. This is illustrated by this image provided by @Stef in the comments:

(The first red line segment after the blue line segment could have been in any other direction, so we don't count that one.)

The probability of such a sequence would be $\left(\frac{1}{5}\right)\left(\frac{1}{5}\right)\left(\frac{1}{5}\right)\left(\frac{1}{5}\right)\left(\frac{1}{4}\right)=\frac{1}{2500}$. Using the expectation of a geometric distribution, the expected number of steps in a walk would be roughly $2500$. I believe, but am not sure, that the expected row number at the end would be on the order of $\sqrt{2500}=50$. (This rough analysis ignores several factors, for example the effect of the boundaries of the triangle.)

But sometimes our walk would go much deeper than the expected depth. The numbers in the triangle increase very quickly. Generally speaking, if the numbers increase faster than the probabilities of reaching them decrease, then the expectation of the final number could be infinite.

Context

This is one of several questions about Pascal's triangle that I've asked recently, for example:

• Does the interior of Pascal's triangle contain three consecutive integers?
• I tried to kill the central binomial coefficients, but they came back
• Conjecture: In Pascal's triangle with $n$ rows, the proportion of numbers less than the centre number approaches $e^{-1/\pi}$ as $n\to\infty$..

Sometimes I am more interested in the methods used to answer the questions, than the answers themselves (but I am still curious what the answer is!). Many of my questions initially seemed almost unapproachable to me, but then turned out to have a rational explanation.

Answer 1

The probability that the first $n-1$ steps are all downward is at least $\left(\frac25\right)^{n-1}$: If all previous steps were downward, one option above is blocked and both options below are open, so the probability for the next step to also be downward is at least $\frac25$.

If all previous steps were downward, then as shown in the question there’s some small constant probability $p$ that we will box ourselves in and end on one of the numbers directly below. (Two of the numbers at the top right of the red path shown in the image may not exist if we’re at the boundary, but that just increases the probability of ending up boxed in at the end point, since in that case we can go there directly with probability $\frac13$ instead of taking three steps with probability $\frac15\cdot\frac15\cdot\frac14$ to get there.)

Both the first $n-1$ downward steps and the $n$-th downward boxing-in step can go left or right, so we can go left or right with equal independent probability $\frac12$ in each step. Then with probability at least $p\left(\frac25\right)^{n-1}2^{-n}\binom nk=c\left(\frac15\right)^n\binom nk$ (with $c=\frac52p$) we end up at $\binom nk$, so the contribution of the $n$-th row to the expectation is at least

\begin{eqnarray} c\left(\frac15\right)^n\sum_{k=0}^n\binom nk^2 &=& c\left(\frac15\right)^n\binom{2n}n \\ &\ge& c\left(\frac15\right)^n\frac{4^n}{2n+1} \\ &=& c\left(\frac45\right)^n\frac1{2n+1}\;. \end{eqnarray}

(see Wikipedia and Inductive proof that ${2n\choose n}=\sum{n\choose i}^2.$).

That’s already very close to what we need – we just have to mop up a bit more probability to increase the factor from $\frac45$ to $1$. To do that, let’s consider two cases depending on whether we’re on the boundary.

If we’re on the boundary, we can improve the bound $\frac25$ on the probability to go downward to $\frac23$, since two of the other adjacent numbers aren’t available.

If we’re not on the boundary, we can reach either number directly below by first moving sideways and then down. The probability for taking one of these two routes is $2\cdot\frac15\cdot\frac14=\frac1{10}$, since on the downward step two other options have already been used. (All the other probabilities are influenced by such sideways steps, since they take away options, but these are options we don’t want to take, so that merely increases the probabilities for the options we do want to take, so all the bounds remain valid.)

This is exactly what we need to get a lower bound of $\frac25+\frac1{10}=\frac12$ for the probability to go downward and thus a lower bound of $\frac c{2n+1}$ for the contribution from each row. It follows that the expected value of the coefficient we end up on is at least

$$ \sum_n\frac c{2n+1}=\infty\;. $$