Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 1 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.