PMF for simple random walk

Question

The general formula for PMF of a binomial r.v. is:

$$p_X(k) = \begin{cases}{n \choose k}~ p^k~ (1-p)^{n-k} & k=0,1,2,...,n \\ 0 & \text{otherwise}\end{cases}$$

Now for the problem:

A simple random walk $X[n]$ is defined in terms of a Bernoulli r.v. Z:

$$P_Z(z) = \begin{cases}p & z=1 \\ 1-p & z=-1 \end{cases}$$

$$X[n] = \sum \limits_{i=1}^{n} Z[i]~~~~~~~n=1,2,\cdots$$

Find the PMF at index n $p_n(k)$ for the random walk $X[n]$

---

So I Start with:

$$X[n] = \sum \limits_{i=1}^{n} Z[i]~~~~~~~n=1,2,\cdots$$

Let:

$$N_1[n] \Leftarrow \text{number of times Z was 1 from index 0 to index n}$$

$$N_0[n] \Leftarrow \text{number of times Z was -1 from index 0 to index n}$$

$$n = N_1[n] + N_0[n] \Leftarrow \text{current index}\tag{1}$$

Now, the summation from above can be rewritten as:

$$X[n] = N_1[n] - N_0[n]\tag{2}$$

Adding (1) and (2) together:

$$n + X[n] = 2 N_1[n]$$

$$N_1[n] = \frac{1}{2}(n + X[n])$$

At this point the textbook notes that $N_1[n]$ is a Binomial random variable, because $N_1[n]$ represents the number of time $Z=1$ for n trials, and that this Binomial random variable has the parameters $(n,p)$.

Now for the part, I don't get...

How did they jump to the conclusion that at index n the PMF of the random walk X[n] is:

$$p_n(k) = {n \choose (n+k)/2} ~~ p^{(n+k)/2}~~q^{(n-k)/2}~~~~~q=1-p$$

Answer 1

Observe that $X[n]=k\iff N_1[n]=\frac12(n+k)$ so that:

$$p_{n}\left(k\right)=P\left(X\left[n\right]=k\right)=P\left(N_{1}\left[n\right]=\frac{1}{2}\left(n+k\right)\right)=\binom{n}{\frac{1}{2}\left(n+k\right)}p^{\frac{1}{2}\left(n+k\right)}q^{n-\frac{1}{2}\left(n+k\right)}$$

Answer 2

$$N_0[n] = \frac{1}{2}(n+X[n])$$

$$X[n]=2N_0[n]-n\tag{1}$$

substitute (1) into (2):

$$P(X[n] =k)\tag{2}$$

$$=P(2N_0[n]-n=k)$$

$$=P\Big(N_0[n]=\frac{1}{2}(k+n)\Big)\tag{3}$$

Now plug (3) into binomial PMF formula.