Variation of a simple random walk

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$,

$$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}}$$

$$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}}$$

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?

-
If n is even, then your walk is the same as a symmetric random walk with n/2 steps, which has the probability $p^2+(1-p)^2$ of staying put. – user31373 Jul 17 '12 at 4:06
Would you mind elaborating on that please? For me it is still not clear. For instance, what would the PMF be for finding the particle at position m after n steps? Same as a n/2 walk? And with what probability, 1/2? Thank you in advance. – Gabriel Landi Jul 17 '12 at 13:27

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.

-