Random walk Catalan sum

Question

Starting at $0$ on the number line, you go right $1$ unit with probability $p$ and left $1$ unit with probability $1-p$. What's the probability of ever getting to $n>0$, and how many steps are expected?

Let $q_k$ be the probability of ever getting to $k\ge 0$. $q_k=q_1^k$ since you ever get to $1$ with probability $q_1$, and the first time you get to $1$ the probability becomes $q_{k-1}$. $$q_1=pq_0+(1-p)q_2=p+(1-p)q_1^2$$ so $$q_1\in\left\{1,\dfrac{p}{1-p}\right\}$$ If $p\ge\tfrac{1}{2}$, then $\tfrac{p}{1-p}\ge 1$, so $q_1=1$, so $q_n=1$. If $p<\tfrac{1}{2}$, I don't know which root to pick.

Let $x_k$ be the expected number of steps to get to $k\ge 0$. By similar reasoning, $x_k=kx_1$. $$x_1=1+px_0+(1-p)x_2=1+(1-p)2x_1$$ so $x_1=\tfrac{1}{2p-1}$. If $p\le\tfrac{1}{2}$, then $$1=(2p-1)x_1\le 0$$ so the expected number of steps is infinite. If $p>\tfrac{1}{2}$, $x_n=\tfrac{n}{2p-1}$.

We can also sum the probability of getting to $1$ in exactly $2k+1$ steps using Catalan numbers to get $q_1$, and sum the probability times $2k+1$ to get $x_1$. The last step must be right and the remaining $2k$ steps can be rearranged in $C_k=\tfrac{1}{k+1}\tbinom{2k}{k}$ ways, so $$q_1=\sum_{k=0}^\infty\dfrac{1}{k+1}\dbinom{2k}{k}p^{k+1}(1-p)^k$$ and $$x_1=\sum_{k=0}^\infty\dfrac{2k+1}{k+1}\dbinom{2k}{k}p^{k+1}(1-p)^k=\sum_{k=0}^\infty\dbinom{2k+1}{k}p^{k+1}(1-p)^k$$ which I have no ideas to compute.

How do you compute the sums? Can you show that $q_1<1$ if $p<\tfrac{1}{2}$ without computing the sum? Are there other ways to answer the original question?

Answer 1

We consider the case $p<\frac{1}{2}$.

We obtain \begin{align*} \color{blue}{q_1(p)}&=\sum_{k=0}^\infty\frac{1}{k+1}\binom{2k}{2k}p^{k+1}(1-p)^k\\ &=p\sum_{k=0}^\infty\frac{1}{k+1}\binom{2k}{k}\left(p(1-p)\right)^k\\ &=p\cdot\frac{1-\sqrt{1-4p(1-p)}}{2p(1-p)}\tag{1}\\ &=p\cdot\frac{1-(1-2p)}{2(1-p)}\\ &\,\,\color{blue}{=\frac{p}{1-p}} \end{align*}

In (1) we use the generating function of the Catalan numbers.

We obtain \begin{align*} \color{blue}{x_1(p)}&=\sum_{k=0}^\infty\binom{2k+1}{k}p^{k+1}(1-p)^k\\ &=p\sum_{k=0}^\infty\binom{2k+1}{k}\left(p(1-p)\right)^k\\ &=p\cdot\frac{1}{\sqrt{1-4p(1-p)}}\left(\frac{1-\sqrt{1-4p(1-p)}}{2p(1-p)}\right)\tag{2}\\ &=p\cdot\frac{1}{1-2p}\cdot\frac{1-(1-2p)}{2p(1-p)}\\ &\,\,\color{blue}{=\frac{p}{(1-2p)(1-p)}} \end{align*}

In (2) we use the generating function of the shifted central binomial coefficients. See (2.5.15) in H. Wilf's Generatingfunctionology.