A Random Walk on $\mathbb{Z}$ starts at $0$. $X_i = 1$ with probability $p$ and $X_i = -1$ with probability $1-p$. I'm looking for the distribution that $\sum_{i=1}^n X_i = S_n = a$, but such that $\forall m < n, S_m < a$. In other words, I'm looking for the distribution of the $\textbf{FIRST}$ time the random walk hits $a$ after $n$ steps.
If we let $n_1$ be the steps to the right, and $n_2$ be the steps to the left, we want $n_1 - n_2 = a$ and $n_1 + n_2 = n$, BUT with the additional requirement that $S_m < a \space \forall m<n$. How do I incorporate this requirement to see the distribution and calculate $\mathbb{P}(S_n = a)$?
To find the probability that $P(T_a=n)$, let us count the number of walks of length $n-1$ which start at $0$ and end at $a-1$, and which never reach $a$. To do this, we will take all the paths which end at $a-1$, of which there are $$\binom{n-1}{({n-a})/2},$$ and subtract the bad paths which reach $a$ at some point.
There is a clever way to count the bad paths. Given a bad path, find the first time it reaches $a$, and reverse all of the steps afterwards. Before the reversal, the path went from the first time it hit $a$ down to $a-1$, so afterwards, it will go from that point to $a+1$. This process is reversible as well; given a path from $0$ to $a+1$, by looking at the first point where it hits $a$ and reversing afterwards, you get a path from $0$ to $a-1$. Therefore, the number of bad paths is just the number of paths from $0$ to $a+1$, which is $$ \binom{n-1}{(n-a)/2-1} $$ Therefore, the number of good paths is $$ \binom{n-1}{({n-a})/2} - \binom{n-1}{(n-a)/2-1} = \binom{n}{(n-a)/2}\cdot \frac{a}{n} $$ Finally, multiplying each of these good paths by the probability they occur, we get $$ P(T_a=n)=\frac{a}n\binom{n}{(n-a)/2}p^{(n+a)/2}q^{(n-a)/2} $$ valid when $n\ge a>0$ and $n-a$ is even.