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

Question

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$.

Answer 1

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.

Answer 2

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, using $\frac{1-\sqrt{1-4x^2}}{2x}=\sum\limits_{k=0}^\infty\frac1{k+1}\binom{2k}{k}x^{2k+1}$, the Cauchy Product Formula and $(1)$ imply $$ 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} $$

Answer 3

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$.

Answer 4

I guess I can solve this problem in a less combinatorial way.

For easier understanding, I will just give a sketch of the proof.

Some abbreviations:

• SRW = Simple Random Walk
• [L/R]HS = [left/right] hand side
• i.i.d. = independent and identically distributed
• # = number

---

First I need to introduce Reflection Principle for SRW.

Consider SRW: $S_n=X_1 + \cdots + X_n$ and $S_0=0$. $\{X_i\}_{i=1}^{n}$ are i.i.d. random variables.

Denote $M_n$ is the farthest position we can reach in $n$ steps (more formally, $M_n=\max_{i\in[0,n]} S_i$). Then

$$ \#(M_n\geqslant x, S_n=y) = \#(S_n=2x-y), \quad \text{if}~~x\geqslant y \tag{Reflection Principle} $$

This is intuitive:

1. $x$ is visited before or at $n$ (exists $t\leqslant n$, such that $S_t=x$);
2. For each path in LHS, you can "reflect" or "flip" all the behaviors after $t$ to get a path in RHS, and vice versa.

---

Then we can easily solve this problem.

Since it is possible only when $n$ and $k$ have the same oddity, and $n\geqslant k$, we can denote $n=k+2l$.

$$ \begin{split} & \#(\text{first visit $k$ at $n$th step}) \\ =& \#(M_{n-1}\leqslant k-1, S_{n-1}=k-1) \\ =& \#(S_{n-1}=k-1) - \#(M_{n-1}\geqslant k, S_{n-1}=k-1) \\ =& \#(S_{n-1}=k-1) - \#(S_{n-1}=k+1) \\ =& \binom{n-1}{k+l-1} - \binom{n-1}{k+l} \\ \end{split} $$

---

We can use 2 simple cases to test this result:

1. $\#=1$ when $n=k$ or $l=0$: $$\binom{k-1}{k-1} - \binom{k-1}{k} = 1 - 0 = 1$$
2. $\#=k$ when $n=k+2$ or $l=1$: $$\binom{k+1}{k} - \binom{k+1}{k+1} = (k+1) - 1 = k$$