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.


2 Responses to 3B Exercise 9: Symmetric convolutions

  1. Douglas Zare says:

    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.

  2. mwildon says:

    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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: