Random walk in one dimension with different probabilities As the title suggests, I'm concerned with a typical random walk problem, where the probability to go right is $p$ and the probability to go left is $q=1-p$. I was trying to find the probability of reaching a position $ml$ (where l is the length of each step) and prove that the sum of all the probabilities across m is 1. The first part was fairly trivial, but I can't figure out how to do the second part in a reasonable way. 
The variables I used are 
$m = N_r - N_l$ (number of steps left and right)
and 
N = total number of steps
For the first part I got P = $\frac{N!}{\frac{N+m}{2}!\frac{N-m}{2}!} p^{\frac {N + m}2}(1-p)^{\frac {N - m}2}$
I'm not sure how to reasonably integrate this to show that the total probability is 1. I used Stirling's approximation and got $\ln \sqrt{2\pi n}(\frac n e)^n - \ln \sqrt{2\pi(n+m)/2}(\frac{n+m}{2e})^{\frac{n+m}{2}}-\ln \sqrt{2\pi(n-m)/2}(\frac{n-m}{2e})^{\frac{n-m}{2}} + \ln(p^{\frac{n+m}{2}})+\ln((1-p)^{\frac{n-m}{2}}$ 
Which I can't reasonably integrate. Come to think of it I've realized there is no justification in taking the natural log of P when I'm trying to find the sum of P, but I'm not sure how to proceed as even without the natural log, the resulting function is too convoluted to integrate. 
 A: Let $P_n(m)$ be the probability of reaching $m^{th}$ position at time $n$.
The proper way to attack this sort problem is not to compute any sum explicitly.
Instead, one should try to prove following sum over $m$ is independent of $n$. 
$$\mathcal{S}_n \stackrel{def}{=}\sum_{m=-\infty}^\infty P_n(m)$$
The main reason is with minimal modification, the argument given below can make to work even when $p$ depends of $n$ or when the jumps in each time steps are not limited to the nearest neighbor. As long as the range of jumps at each time step 
is finite, for any fixed $n$, there are only finitely many $m$ when $P_n(m) \ne 0$. So above sums $\mathcal{S}_n$ are always well defined and you can manipulate
it like ordinary finite sum.
Back to the problem at hand, it is not hard to see our $P_n(m)$ satisfies a recurrence relation of the form
$$P_n(m) = p P_{n-1}(m-1) + (1-p) P_{n-1}(m+1)\quad\text{ for }n > 1$$
Summing over $m$ give us
$$\mathcal{S}_n = p \mathcal{S}_{n-1} + (1-p) \mathcal{S}_{n-1} =
(p + (1-p))\mathcal{S}_{n-1} = \mathcal{S}_{n-1}\quad\text{ for }n > 1$$
Since $\displaystyle\;P_0(m) = \begin{cases} 1,& m = 0\\ 0,& m \ne 0\end{cases},\;$ 
we have $\mathcal{S}_0 = 1$ and hence $\mathcal{S}_n = 1$ for all $n \ge 0$.
A: You can model a random walk using the binomial theorem.  Model a single step as $px + \frac{1-p}{x}$, and $n$ steps as $\left(px + \frac{1-p}{x}\right)^n$.  The coefficient of $x^i$ is the probability that, after $n$ steps, the person is at position $i$ (assuming $l=1$).  From the binomial theorem,
$$\begin{align}
\left(px + \frac{1-p}{x}\right)^n & = \sum_{i=0}^{n} \binom{n}{i}((px)^i((1-p)x^{-1}))^{n-i})\\
& = \sum_{i=0}^{n} \binom{n}{i}p^ix^i(1-p)^{n-i}x^{i-n}\\
& =\sum_{i=0}^{n} \binom{n}{i}p^i(1-p)^{n-i}x^{2i-n}\\
\end{align}$$
So the probability that you wind up at position $2i-n$ is $\binom{n}{i}p^i(1-p)^{n-i}$.  The probability of all other positions is $0$.
As @lulu pointed out, the initial form (with $x=1$) gives you a trivial proof that the sum of all probabilities is $1$.
