# Probability that random walk will reach state $k$ for the first time on step $n$

We have a random walk which starts in state $$0$$. At each step, a coin is tossed with probability of heads: $$P(H)=p$$. If we get a heads, we go to the next higher integer state and on tails, we go to the next lower integer state (so state $$n$$ would go to $$n+1$$ on heads and $$n-1$$ on tails).

Now, I want to know the probability that we will reach state $$k$$ for the first time after exactly $$n$$ tosses of the coin. Turning out to be surprisingly hard for me.

Here is my attempt:

I define $$a_n^{k}$$ as the probability described above and $$c_n^k$$ as the probability that the random walk will be in state $$k$$ at toss $$n$$ (regardless of if it was there in a previous toss).

It's clear that we need $$\left(\frac{n-k}{2}\right)$$ tails and $$\left(\frac{n+k}{2}\right)$$ heads. So if $$n-k$$ is not even, the sequences for those $$n$$'s become $$0$$.

To get $$a_n^k$$, we need to identify all sequences where the cumulative number of heads stays less than $$k$$ + the cumulative number of tails for all tosses leading upto $$n$$. This is not so easy to solve.

On the other hand, I got an expression for $$c_n^k$$ and hoped I could use it to get $$a_n^k$$. I reasoned that the probability the walk reaches $$k$$ for the first time on toss $$n$$ is the probability it is in state $$k$$ on toss $$n$$ subtracted by the probabilities that it was in state $$k$$ in any previous toss. So,

$$a_n^k = c_n^k - \sum_{i=1}^{n-1} c_i^k$$

But this can't be right since this expression will become negative for many values of $$n$$.

• Still working on the solution to the question, but I do know why the reasoning at the end is wrong; the probabilities are not independent, so you can not simply subtract them from each other. – SmileyCraft Dec 16 '18 at 19:07
• Appreciate it. Yeah, I suspected as much. That's almost always the reason when you add/subtract probabilities and get something not between 0 and 1. Thought I'd mention it anyway in case it inspired someone to formulate a correct approach based on the idea. – Rohit Pandey Dec 16 '18 at 19:09
• If you reverse time and flip the y axis, you are counting paths which reach k after n steps without ever returning to 0. This is Bertrand’s ballot problem. – Mike Earnest Dec 16 '18 at 20:24
• Don't completely follow. If I reverse time, I start off at $k$, correct? So, doesn't it become paths that reach 0? – Rohit Pandey Dec 16 '18 at 20:33
• @RohitPandey Sorry, when I said "flip the y-axis,", I meant that you interchange $0$ with $k$. – Mike Earnest Dec 17 '18 at 12:49

After some investigation, it seems to be the case that there are $$f(k,\ell)=\frac{k+1}{k+1+\ell}{k+2\ell\choose\ell}$$ paths to state $$k\geq0$$ in $$k+2\ell$$ steps that never pass the $$k$$'th state. This is equivalent to the amount of ways to move to state $$k+1$$ for the first time after $$k+1+2\ell$$ steps. By substitution and simple probability, we get a $$\frac{k}{k+\ell}{k-1+2\ell\choose\ell}p^{k+\ell}q^{\ell}$$ probability of reaching state $$k$$ for the first time after $$k+2\ell$$ steps.

We can prove our formula for $$f$$ by induction. For $$\ell=0$$ the answer is obviously $$1$$, which coincides with the given formula. For $$k=-1$$ the answer is obviously $$0$$, which also coincides with the given formula. For $$\ell>0$$ and $$k\geq0$$ we have two options for the first move: right or left. If we go left, there are $$f(k+1,\ell-1)$$ options, and if we go right there are $$f(k-1,\ell)$$ options. Hence, in total we have \begin{align} f(k+1,\ell-1)+f(k-1,\ell) &=\frac{k+2}{k+2+\ell-1}{k+1+2(\ell-1)\choose\ell-1}+\frac{k}{k+\ell}{k-1+2\ell\choose\ell} \\&=\frac{(k+2)(k+2\ell-1)!}{(k+\ell+1)(\ell-1)!(k+\ell)!}+\frac{k(k+2\ell-1)!}{(k+\ell)\ell!(k+\ell-1)!} \\&=\frac{(k+2)(k+2\ell-1)!}{(\ell-1)!(k+\ell+1)!}+\frac{k(k+2\ell-1)!}{\ell!(k+\ell)!} \\&=\frac{\ell(k+2)(k+2\ell-1)!}{\ell!(k+\ell+1)!}+\frac{(k+\ell+1)k(k+2\ell-1)!}{\ell!(k+\ell+1)!} \\&=\frac{(\ell(k+2)+(k+\ell+1)k)(k+2\ell-1)!}{\ell!(k+\ell+1)!} \\&=\frac{(2\ell k+2\ell+k^2+k)(k+2\ell-1)!}{\ell!(k+\ell+1)!} \\&=\frac{(2\ell+k)(k+1)(k+2\ell-1)!}{\ell!(k+\ell+1)!} \\&=\frac{(k+1)(k+2\ell)!}{\ell!(k+\ell+1)!} \\&=f(k,\ell) \end{align} options. By principle of induction, this proves the correctness of the formula for $$f$$.

Now admittedly, even though this solves the problem, it is not a nice solution. I found the formula by simply experimenting for half an hour, and the proof is very algebraic and not very nice to look at. If someone comes up with a combinatorical proof, that would be much better! I am certainly going to think about it now.

• I see, thanks. Can you briefly explain how you came up with this formula via experimentation? What was your approach to first discover it? – Rohit Pandey Dec 16 '18 at 21:11
• I took a fixed $\ell$ and I expected the formula would be a polynomial of degree $\ell-1$, so simply finding $\ell$ terms determines the polynomial. The first few polynomials were $1$; $k+1$; $(k+1)(k+4)/2$; $(k+1)(k+5)(k+6)/6$; $(k+1)(k+6)(k+7)(k+8)/24$. At this point I found the pattern and I got the formula. – SmileyCraft Dec 16 '18 at 21:14
• Sorry, one last thing I haven't understood - why didn't you just call the probability $f(k,l) p^{k+l}q^l$? Instead, you wrote it as $f(k-1,l) p^{k+l} q^l$. – Rohit Pandey Dec 16 '18 at 21:52
• To go to state $k$ for the first time after $k+2\ell$ steps means to go to state $k-1$ after $k-1+2\ell$ steps without going past state $k-1$ and then going right. – SmileyCraft Dec 16 '18 at 22:09
• Ahh, without going past being they key. Got it, thanks again! Impressive solution. – Rohit Pandey Dec 16 '18 at 22:12

This answer is an extension to the one by @SmileyCraft. As he says in his answer, it would be nice to have a combinatorial proof. I might have found one. The problem seems similar in spirit to the one where you have a square grid, start at the bottom left corner and need to get to the top-right corner and find the number of paths where you don't cross the main diagonal of the grid (ok to touch it). In that instance, the number of such paths is the catalan numbers.

$$C_n = \frac{2n \choose n}{n+1} = {2n \choose n} - {2n \choose n-1}$$

Now, taking a cue from this, the formula @SmileyCraft has above can also be written as:

$$f(k,l) = \frac{k+1}{k+1+l} {k+2l \choose l} = {k+2l \choose l} - {k+2l \choose l-1} \tag{1}$$

Now, the problem here for the random walk not crossing $$k$$ can be converted to a grid problem. We basically have (per @SmileyCraft's convention) $$l$$ tails and $$l+k$$ heads and need to arrange them in such a way as to never cross the $$k$$. This is completely equivalent to saying we'll go right if we get a tails and up if we get a heads on a grid which has $$l+k$$ rows and $$l$$ columns.

Another way to see this is to plot on the x-axis the toss number and on the y-axis the score of the random walk. Now, imagine any path going from $$(0,0)$$ to $$(k+2l,k)$$. Now, simply rotate the whole picture by 45 degrees and you'll get the grid.

So the formula for $$f(k,l)$$ above is simply the number of ways to go from the bottom left to top right of a grid with $$l$$ rows and $$l+k$$ columns in such a way that the path never crosses the line $$y=x+k$$.

But how do we show that is equivalent to equation (1) above? I cheated and used the same reasoning as the answer by @Marcus M here. It goes like this:

We know the total paths in our grid are $$k+2l \choose l$$. The good paths are ones that never cross the line $$y=x+k$$. Then,

# good paths = # paths - # bad paths

Now, any bad path does cross the line $$y=x+k$$. So, it must touch the line $$y=x+k+1$$ (the diagonal just above it).

Divide any such path into two portions. The portion from the origin to when it touches the $$y=x+k+1$$ line and the portion after that. The first portion can be reflected about the $$y=x+k+1$$. And this leads to a bijection to a path from $$(-(k+1),(k+1))$$ to $$(l,k+l)$$. So, the bad paths can be mapped to paths from the bottom left to top-right of another grid whose height is $$(k+l)-(k+1)=l-1$$. But we didn't change the total path length, so the total length of the bad paths is still $$k+2l$$. Hence, the number of bad paths is $$k+2l \choose l-1$$.

Putting all of this together, we get equation (1) above. The picture below shows this for $$k=3$$ and $$t=2$$. • I believe you are confusing your lefts and rights somewhere, but I get the proof and it is very satisfying :) – SmileyCraft Dec 18 '18 at 16:55
• Yes, I did have left and right mixed up in one place. Fixed that - thanks! – Rohit Pandey Dec 18 '18 at 20:47

A Generating Function

Let the number of ways for getting to position $$s$$ for the first time on step $$n$$ be $$a_{s,n}$$. The number of unilateral walks of length $$2k$$ is $$\frac1{k+1}\binom{2k}{k}$$, with generating function $$\frac{1-\sqrt{1-4x}}{2x}$$. To first get to position $$s$$ on step $$n$$, we can count the number of ways to first get to position $$s-1$$ in $$n-2k-1$$ steps times the number of unilateral walks of length $$2k$$ and sum for all $$k$$. That is, $$a_{s,n}=\sum_{k=0}^\infty\frac1{k+1}\binom{2k}{k}\,a_{s-1,n-2k-1}\tag1$$ If we set the generating function $$f_s(x)=\sum_{n=0}^\infty a_{s,n}x^n\tag2$$ then $$(1)$$ implies $$f_s(x)=f_{s-1}(x)\left(\frac{1-\sqrt{1-4x^2}}{2x}\right)\tag3$$ and since $$f_0(x)=1$$, induction yields $$\bbox[5px,border:2px solid #C0A000]{f_s(x)=\left(\frac{1-\sqrt{1-4x^2}}{2x}\right)^{\large s}}\tag4$$ Therefore, if the probability of a '$$+1$$' step is $$p$$ and of a '$$-1$$' step is $$1-p$$, then the probability of $$\frac{n+s}2$$ '$$+1$$' steps and $$\frac{n-s}2$$ '$$-1$$' steps is $$a_{s,n}p^{\frac{n+s}2}(1-p)^{\frac{n-s}2}=\left(\frac{p}{1-p}\right)^{s/2}a_{s,n}(p(1-p))^{n/2}$$. Summing over $$n$$ gives the probability of getting to position $$s$$ at all to be \begin{align} \left(\frac{p}{1-p}\right)^{s/2}f_s\!\left(\sqrt{p(1-p)}\right) &=\left(\frac{1-|1-2p|}{2(1-p)}\right)^{\large s}\\[3pt] &=\left\{\begin{array}{}\left(\frac{p}{1-p}\right)^s&\text{if }p\lt\frac12\\1&\text{if }p\ge\frac12\end{array}\right.\tag5 \end{align}

A Closed Form

To derive a closed form for $$a_{s,n}$$, we first consider the series $$\sum_{n=0}^\infty b_{s,n}x^n=\left(\frac{1-\sqrt{1-4x}}{2x}\right)^{\large s}\tag6$$ where, comparing $$(4)$$ and $$(6)$$, we get \begin{align} a_{s,s+2n}&=b_{s,n}\\ a_{s,s+2n+1}&=0 \end{align}\tag7 Using the fact that $$\left(\frac{1-\sqrt{1-4x}}{2x}\right)^2=\frac1x\frac{1-\sqrt{1-4x}}{2x}-\frac1x\tag8$$ we get the relation $$b_{s,n}=b_{s-1,n+1}-b_{s-2,n+1}\tag9$$ We know that \begin{align} b_{0,n}&=[n=0]\\[3pt] b_{1,n}&=\frac1{n+1}\binom{2n}{n}=\binom{2n}{n}-\binom{2n}{n-1} \end{align}\tag{10} which implies that \begin{align} b_{2,n}&=\frac1{n+2}\binom{2n+2}{n+1}=\binom{2n+1}{n}-\binom{2n+1}{n-1}\tag{11}\\[6pt] b_{3,n}&=\frac1{n+3}\binom{2n+4}{n+2}-\frac1{n+2}\binom{2n+2}{n+1} =\binom{2n+2}{n}-\binom{2n+2}{n-1}\tag{12} \end{align} A pattern is appearing; that is, \begin{align} b_{s,n} &=\binom{2n+s-1}{n}-\binom{2n+s-1}{n-1}\\[3pt] &=\frac{s}{2n+s}\binom{2n+s}{n}\tag{13} \end{align} which satisfies $$(9)$$ using Pascal's Formula. Therefore, applying $$(7)$$ yields $$\bbox[5px,border:2px solid #C0A000]{a_{s,n}=\left\{\begin{array}{} \frac sn\binom{n}{(n-s)/2}=\binom{n-1}{(n-s)/2}-\binom{n-1}{(n-s-2)/2}&\text{if }2\mid n-s\\ 0&\text{if }2\nmid n-s \end{array}\right.}\tag{14}$$

• In equation (2), should the index be on $n$ instead of $k$? – Rohit Pandey Jan 20 at 18:54
• Very beautiful proof. To get an actual expression for $a_{s,n}$, we can use (5.70) here (in conjunction with equation (4)): math.stackexchange.com/questions/3064256/…. This identity isn't super easy to prove, but it gets one there. – Rohit Pandey Jan 20 at 19:39
• @RohitPandey: Indeed. I am working on more for the answer. As soon as I post that, the correction will be there. – robjohn Jan 20 at 23:27
• @RohitPandey: I have added a derivation of the closed form as well. – robjohn Jan 21 at 19:07
• Thanks a lot, reading through. In the meantime, I'm writing a paper on how races of wealthy gamblers can be used to estimate $\pi$. I think this provides a method that converges to $\pi$ reasonably fast and has a nice interpretation as well. I'll be done with the first draft very soon. Would love to have you as a co-author since your answers have helped a lot with the effort. Let me know if you're fine with it. If not, is it OK to cite your answers in it? – Rohit Pandey Jan 21 at 19:56