Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
Let $P_{k,j}$ be the probability that a simple symmetric random walk starting from the origin reaches the point $k \in \mathbb{N}$ precisely in $j$ steps without ever returning to the origin. Obviously, $P_{k,j}>0$ if and only if $j \geq k$. Let $ 0<c <1$ be a constant.
Is there a way to rewrite the following sum in a "nicer" way, without computing $P_{k,j}$ explicitly, by using the properties of simple symmetric random walk?
$$ \sum_{k=1}^{\infty} \sum_{j=k}^{\infty} P_{k,j} \, \, c^{j-1}$$
Let $P_{k,j}$ be the probability that you reach $k\ge 1$ in exactly $j$ steps without ever returning to the origin. As OP points out, $P_{k,j}=0$ for $j<k$, so the sum $$ S=\sum_{k=1}^{\infty}\sum_{j=k}^{\infty}P_{k,j}c^{j-1}=\sum_{k=1}^{\infty}\sum_{j=1}^{\infty}P_{k,j}c^{j-1}=\sum_{j=1}^{\infty}\left(\sum_{k=1}^{\infty}P_{k,j}\right)c^{j-1}. $$ That is, the sum over $k$ can be carried out first. The term inside the parentheses is just half the probability that the walk has never returned to the origin after $j$ steps. The probability that a random walk of length $j$ is non-recurrent is given by $1 - 2^{-j}R_{j}$, where $R_j$ is the number of walks of length $j$ that have returned to the origin. So $$ S=\frac{1}{2}\sum_{j=1}^{\infty}\left(1 - 2^{-j}R_j\right) c^{j-1} = \frac{1}{2(1-c)}-\frac{1}{4}\sum_{j=1}^{\infty}\left(\frac{c}{2}\right)^{j-1}R_j. $$ Now, the number of recurrent walks of length $j$ is equal to the sum over $T \le j$ of the number of walks that first return to the origin after $j$ steps, times $2^{j-T}$. We can restrict the sum to even $T=2n+2$: as is well known, the number of walks that first return to the origin after $2n+2$ steps is given by twice the $n$-th Catalan number. So $$ R_j=\sum_{n=0}^{\lfloor j/2\rfloor - 1} 2^{j-2n-2} (2C_n)=2^j\sum_{n=0}^{\lfloor j/2\rfloor - 1} \frac{2^{-2n-1}}{n+1}{{2n}\choose{n}}=2^j\left(1-2^{-2\lfloor{j/2}\rfloor}{{2\lfloor{j/2}\rfloor}\choose{\lfloor{j/2}\rfloor}}\right)\\=2^j-2^{\lceil{j/2}\rceil - \lfloor{j/2}\rfloor}{{2\lfloor{j/2}\rfloor}\choose{\lfloor{j/2}\rfloor}}. $$ So for even $j=2k$, we have $$ R_{2k}=2^{2k}-{{2k}\choose{k}}, $$ while for odd $j=2k+1$, we have $$ R_{2k+1}=2^{2k+1}-2{{2k}\choose{k}}=2 R_{2k}. $$ Then $$ \sum_{j=1}^{\infty}\left(\frac{c}{2}\right)^{j-1}R_j = \sum_{k=1}^{\infty}\left(\frac{c}{2}\right)^{2k-1}\left(R_{2k}+\frac{c}{2}R_{2k+1}\right)=(1+c)\sum_{k=1}^{\infty}\left(\frac{c}{2}\right)^{2k-1}\left(2^{2k}-{{2k}\choose{k}}\right)\\=(1+c)\sum_{k=1}^{\infty}2c^{2k-1}-(1+c)\sum_{k=1}^{\infty}\left(\frac{c}{2}\right)^{2k-1}{{2k}\choose{k}} \\ =\frac{2c(1+c)}{1-c^2}-\frac{2(1+c)}{c}\left(\frac{1}{\sqrt{1-c^2}}-1\right)=\frac{2c}{1-c}+\frac{2(1+c)}{c}-\frac{2}{c}\sqrt{\frac{1+c}{1-c}}. $$ Putting it all together, we have $$ S=\frac{1}{2(1-c)}-\frac{c}{2(1-c)}-\frac{1+c}{2c}+\frac{1}{2c}\sqrt{\frac{1+c}{1-c}}=\frac{1}{2c}\left(-1 + \sqrt{\frac{1+c}{1-c}}\right). $$
The solution already given can be simplified somewhat by using generating functions. The random walk is given by a sequence of steps, either in the positive direction (+ steps) or in the negative direction (- steps.) Let $\cal W$ be the set of walks which begin with a + step, return to the origin exactly once, and end there, let $W_j$ be the number of walks in $\cal W$ of length $j$, and let $W(x):=\sum_{j\ge 0} W_j x^j$ be the generating function (gf) of $\cal W$. Then each walk in $\cal W$ can be decomposed in a unique way into a + step (taking us to the point 1), a sequence of walks taken from $\cal W$ (which eventually leave us at 1), and a final - step returning to 0. Translating this into the language of gfs gives $$W(x)={x^2 \over 1-W(x)},$$ and solving this quadratic gives $$ W(x)={1-\sqrt{1-4x^2}\over 2}, $$ where the sign of the square root has been chosen to make $W_0=0$. Let $R(x)$ be the gf of the set of walks $\cal R$ beginning with a + step which have returned to the origin at some point, and $S(x)$ be the gf of the set $\cal S$ of walks beginning with a + step which have not. Then any walk in $\cal R$ can be decomposed uniquely into an initial walk which returns to the origin once and ends there, followed by an arbitrary sequence of steps. The gf of the initial walk is $W(x)$; since $(1-2x)^{-1}$ is the gf of an arbitrary sequence of steps, $R(x)=W(x)(1-2x)^{-1}$. Also, $\cal R$ and $\cal S$ partition the set of all walks beginning with +; this set has gf $x (1-2x)^{-1}$, so \begin{eqnarray*} S(x)&=&{x \over 1-2x}-R(x)\\ &=& {x- W(x)\over 1-2x}\\ &=&{2x-1+\sqrt{1-4x^2}\over 2(1-2x).} \ \ \ (*) \end{eqnarray*} Now, if $S_j$ is the number of walks in $\cal S$ of length $j$, then the sum we want to compute is $$ \sum_{j\ge 1} S_j 2^{-j} c^{j-1} = c^{-1} S({c\over 2}), $$ so plugging $c/2$ into $(*)$ and dividing by $c$ gives the answer: $$ {c-1+\sqrt{1-c^2}\over 2c(1-c)}={1\over 2c}\left(-1+\sqrt{1+c\over 1-c}\right). $$
This answer is correct if $P_{k,j}$ is taken to be the probability that the walk has never returned to the origin and is at $k$ after $j$ steps. If $P_{k,j}$ is the probability that the walk has never returned to the origin and arrives at $k$ for the first time after $j$ steps, the answer will be more complicated.
