Random Walk: $P(X = (n + k)/2) = {n \choose \frac{n + k}{2}} \frac{1}{2^n}$

Question

My notes say the following:

Example (Random Walk)

A particle moves $n$ steps on a number line. The particle starts at $0$, and at each step it moves $1$ unit to the right or to the left, with equal probabilities. Assume all steps are independent. Let $Y$ be the particles position after $n$ steps. Find the PMF of $Y$.

Consider each step to be a Bernoulli trial, where right is considered a success and left is considered a failure.

The number of steps the particle takes, say $X$, to the right is a $Bin(n, 1/2)$ random variable, that is $x \sim Bin(n, 1/2)$.

If $X = j$, then the particle has taken $j$ steps to the right and $n - j$ steps to the left, giving a final position of $j - (n - j) = 2j - n$.

So we can express $Y$ as a one-to-one function of $X$, namely, $Y = 2X - n$.

The PMF of $Y$ can then be found from the PMF of $X$:

$P(Y = k) = P(2X - n = k) = P(X = (n + k)/2) = {n \choose \frac{n + k}{2}} \frac{1}{2^n}$

How does one conclude that $P(X = (n + k)/2) = {n \choose \frac{n + k}{2}} \frac{1}{2^n}$?

I would greatly appreciate it if people could please take the time to clarify this.

Answer 1

Note that the PMF of a binomial distribution is$$\Pr\{X=k\}=\binom{n}{k}p^k(1-p)^{n-k}$$where $p$ is the probability of success in a single experiment.

P.S.

It is worth noting that $n$ and $k$ in your question must be both even or both odd simultaneously.

Answer 2

Out of $n$ steps you want $\frac {n+k} 2$ steps to the right and the remaining steps to the left. All possibilities have probability $(\frac 1 2)^{n}$. Once you pick the stepsto the right the entire path is fixed. The number of ways of choosing $\frac {n+k} 2$ steps from $n$ steps is $\binom {n} {\frac {n+k} 2}$. Hence the probability is $\binom {n} {\frac {n+k} 2} (\frac 1 2)^{n}$