Consider the following problem.
A particle takes discrete steps $\sigma_1, \sigma_2, \sigma_3, \ldots, \sigma_n$ which take on values $+1$ or $-1$. However, $P(\sigma_i = +1) = p$ if $i$ is odd and $1-p$ if $i$ is even. Equivalently, $P(\sigma_i=-1)$ will be $1-p$ if $i$ is odd and $p$ if $i$ is even.
I am looking for the PMF of $M_n = \sigma_1 + \sigma_2 + \ldots + \sigma_n$. For large $n$ the solution using the central limit theorem is quite straightforward says that $M\sim N(0,n)$, a normal with zero mean and variance $n$.
However, I am stuck at trying to find a solution for arbitrary n. So far, what I have tried is: write $M_n = M_o+ M_e$. For these M's I can compute their PMF, which is equivalent to the usual random walk. So let $n_o = n - Floor(n/2)$ and $n_e = Floor(n/2)$. Then, if $q=1-p$,
\begin{equation} P_{n_o}(M_o = m_o) = \binom{n_o}{\frac{n_o+m_o}{2}} p^{\frac{n_o+m_o}{2}} q^{\frac{n_o-m_o}{2}} \end{equation}
\begin{equation} P_{n_e}(M_e = m_e) = \binom{n_e}{\frac{n_e+m_e}{2}} q^{\frac{n_e+m_e}{2}} p^{\frac{n_e-m_e}{2}} \end{equation}
But now I would have to convolve these two PMFs, something which I have no idea how to do. I am not even sure this is a good approach (it sure is a messy one). Anyone has any idea to share?
I can't think of any clever solution. A non-clever approach is to consider the probability generating function $E z^{M_n}=\prod_{k=1}^n Ez^{\sigma_n}$. Since $E z^{\sigma_1}=pz+(1-p)z^{-1}$ and $Ez^{\sigma_2}=(1-p)+pz^{-1}$, the product becomes $$E z^{M_n} = \{pz+(1-p)z^{-1}\}^{n\mod2} \left\{p(1-p)(z^2+z^{-2})+p^2+(1-p)^2\right\}^{\lfloor n/2\rfloor} $$ The second term can be simplified to $(p(1-p))^{\lfloor n/2\rfloor}(z^2+z^{-2}+c)^{\lfloor n/2\rfloor}$ with $c=\frac{p^2+(1-p)^2}{p(1-p)}$, and the multinomial formula gives the coefficients of $z^m$ as sums of multinomial coefficients.
This is not really different from convolving $M_o$ and $M_e$, just expressed differently.