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