3B Exercise 9: Symmetric convolutions

Let $p$ be an odd prime. A probability distribution $P$ on $\mathbf{Z}/p\mathbf{Z}$ is symmetric and unimodal if and only if $P_{-x} = P_x$ for all $x$ such that $0 \le x \le (p-1)/2$ and

$P_{0} \ge P_1 \ge P_2 \ge \ldots \ge P_{(p-1)/2}.$

Exercise 9 asks us to show that if $P$ and $Q$ are two symmetric unimodal distributions then their convolution $R= P \star Q$ is again symmetric and unimodal. The symmetry is easy: for any $x \in \mathbf{Z}/p\mathbf{Z}$ we have

$R_x = \sum_{y \in \mathbf{Z}/p\mathbf{Z}} P_{x+y} Q_{-y} = \sum_{y \in \mathbf{Z}/p\mathbf{Z}} P_{-x-y} Q_y = R_{-x}.$

First proof of unimodality

Let $r = (p-1)/2$. It suffices to show that if $0 \le x \le r$ then $R_x \ge R_{x+1}$. In fact we shall prove that $R_x - R_{x+1}$ is a sum of terms of the form $(P_j - P_k)(Q_i - Q_{i+1})$ where $0 \le j < k \le r$ and $0 \le i \le r$. Each such term is positive.

It is clear that one contribution to $R_x - R_{x+1}$ comes from

$P_x (Q_0 - Q_1)$.

If we increase the indices of the $Q$ terms, we get $P_{x-1}(Q_1 - Q_2)$, $P_{x-2}(Q_2 - Q_3)$ and so on, until we reach $P_0 (Q_x - Q_{x+1})$. At this point the indices of the $P$ terms begin to increase, until we reach $P_{r-x-1}(Q_{r-1} - Q_r)$. The next term is $P_{r-x}(Q_r - Q_r)$, which vanishes, and then we continue until $-P_r(Q_{r-x} - Q_{r-x+1}$. (Note the change of sign.) Then finally the indices of the $p$ terms decrease until we reach $-P_{x+1}(Q_0 - Q_1)$. In this process we see each $Q_i - Q_{i+1}$ twice. A rather fiddly calculation shows that if $x \le r-x$ then the coefficient of $Q_i - Q_{i+1}$ is

$\begin{cases} P_{x-i} + P_{x+i+1} & : \ 0 \le i \le x-1 \\ P_{i-x} - P_{x+i+1} & :\ x \le i \le r-x-1 \\ P_{i-x} - P_{2r-x-i} & : \ r-x \le i \le r-1 \end{cases}$

which is as required. The case $x > r-x$ should be similar, but I haven’t worked out the formula.

A better proof

A very slick proof of unimodality for random variables taking values in $\mathbf{R}$ was given by Purkayastha in 1998. The argument can be adapted to our case.

Let $Y$ be a random variable distributed so that $\mathbf{P}(Y = y) = P_y$. Then

$R_x = (P \star Q)_x = \sum_y P_y Q_{x-y} = \sum_y P_y Q_{y-x} = \mathbf{E}(Q_{Y-x}).$

A standard result states that if $Z$ is any random variable taking non-negative real values then $\mathbf{E}(Z) = \int_{u=0}^\infty \mathbf{P}(Z > u) \; \mathrm{d}u$. Applying this result to the random variable $Q_{Y-x}$ we see that

$R_x = \int_{u=0}^\infty \mathbf{P}(Q_{Y-x}) \ge u) \; \mathrm{d}u$.

For each $u$ there exists an $m(u) \in \mathbf{N}_0$ such that

$\mathbf{P}(Q_{Y-x} \ge u) = \mathbf{P}(|Y-x| \le m(u))$

It therefore suffices to prove that for each fixed $u$, the function

$f(x) = \mathbf{P}(|Y-x| \le m(u)) = \mathbf{P}(x-m(u) \le Y \le x+m(u))$

is a decreasing function of $x$, for $0 \le x < r$. (Note that $x-m(u)$ and $x+m(u)$ are computed in $\mathbf{Z}/p\mathbf{Z}$.) Now finally we have

$f(x) - f(x+1) = \mathbf{P}(Y = x - m(u)) - \mathbf{P}(Y = x + m(u) + 1)$

which is always positive provided $0 \le x < r$.

Other remarks

Note that the probability distribution of the position of a particle after $n < p$ steps of the symmetric random walk in which the steps $\pm 1$ have equal probability is certainly not unimodal, because if $n$ is even then the particle must be at an even position, and similarly if $n$ is odd. (Exercise 10 gives a monotonicity result for these positions.)

The result on convolutions can however be applied to the random walk where the steps $0, \pm 1$ all have equal probability $1/3$. It would be interesting to know how quickly this walk approaches the uniform distribution compared to the walk with steps $\pm 1$. On the one hand, one might expect the convergence to be slower, since at each time there is a good chance we will stand still. On the other hand, one would not expect parity to lead to any significant extra departure from randomness.

If we renumber $\mathbb{Z}/p\mathbb{Z}$ so that $n$ is relabeled $n/2$, then what is originally a $\{-1,+1\}$ walk becomes a $\{0,1\}$ walk followed by a rotation. (Similarly, a $\{-1,0,1\}$ walk is a $\{0,1,2\}$ walk followed by a rotation.) For $p$ much larger than $n$ (or in fact, much larger than $\sqrt{n}$), doing $n$ steps of the $\{0,1\}$ walk gives something that looks like an integer approximation to a normal distribution with variance $n/4$. Doing $m$ steps of the $\{-1,0,1\}$ walk gives an integer approximation to a normal distribution with variance $2m/3$. If we do $8k$ steps of the $\{0,1\}$ walk, it should be hard to tell that it was not $3k$ steps of the $\{0,1,2\}$ walk followed by a rotation. So, as $p$ tends to infinity, I would guess that the $\{-1,0,1\}$ random walk should approach the uniform distribution about $8/3$ as rapidly as the $\{-1,1\}$ random walk.
It takes about $p^2$ steps for the $\{-1,1\}$ random walk on $\mathbb{Z}/p\mathbb{Z}$ to get close to uniform, so taking $p$ much larger than $n$ is not obviously justified. Of course your argument could still give the correct rate of approach to the uniform distribution. When I have time I will run some simulations.