SOME RANDOM PROCESSES RELATED TO AFFINE RANDOM WALKS

Martin Hildebrand

Department of Mathematics, The University of Michigan, Ann Arbor, MI 48109-1003

Keywords: affine group; random walks; random number generators; Diaconis- Shahshahani upper bound lemma

ABSTRACT

This paper considers random processes of the form X_{n+1} = a_{n}X_{n} +b_{n} (mod p) where (a_{n}, b_{n}) are independent random variables, p is an odd integer, and P (a_{n} = (p + 1)/2) is a positive constant. This paper searchs for the time it takes the sequence X_{0} = 0, X_{1}, X_{2}, ... to get close to uniformly distributed on Z/pZ. This paper shows that the order of this time will depend on the probabilities for a_{n}. In particular if a_{n} may take on values 1, 2, or (p + 1)/2 and must take on at least 2 of these values and if b_{n} is independent of a_{n}, then this time depends on whether P (a_{n} = 2) = P (a_{n} = (p + 1)/2). This paper also considers some results when a_{n} and b_{n} are dependent.

INTRODUCTION

A pseudo-random number generator sometimes used on computers utilizes a recurrence equation of the form

X_{n+1} = aX_{n} + b (mod p)

where a and b are constants. Although the sequence X_{0} = 0, X_{1}, X_{2}, ... is deterministic, this sequence shares some properties of random sequences. See Knuth (1981) for more details.

Further work has examined random processes of the form

X_{n+1} = a_{n}X_{n} + b_{n} (mod p)

where the a_{n}’s and b_{n}’s are independent random variables with the a_{n}’s identically distributed and the b_{n}’s identically distributed. Cases where a_{n} has a fixed probability on Z^{+} and b_{n} has a fixed probability on Z have been explored in a number of previous works. See Chung Diaconis, and Graham (1987) and Hildebrand (1990, 1993a, 1993b). Questions where a_{n} has a distribution which depends on p (e.g. P (a_{n} = (p + 1)/2) = P (a_{n} = 1) = P (a_{n} = 2) = 1/3 for odd values of p) appear in Diaconis (1988). The question of interest is how long does it take for X_{n} to get close to uniformly distributed on Z/pZ. Using random walks on the affine group, Xu (1990) provides an upper bound to this time for certain values of p but wonders if the bound can be improved. This paper finds some lower bounds for this time and provides an upper bound which uses different techniques and a broader range of values of p than Xu.

Using the notation of the next section, this paper shows the following 3 theorems where a_{n} and b_{n} are assumed to be independent. Theorem 1: If P (a_{n} = (p + 1)/2) = P (a_{n} = 2) = 1/2 and P (b_{n} = −1) = P (b_{n} = 1) = 1/2 and ϵ > 0 is given, then for some constant c > 0, if n ≥ c(log p)^{2} then ∥P_{n} − U∥ < ϵ for sufficiently large odd values of p. Theorem 2: Suppose P (a_{n} = (p + 1)/2) = a, P (a_{n} = 1) = b, P (a_{n} = 2) = c, at least 2 of a, b, and c are non-zero, a + b + c = 1, P (b_{n} = 1) = d, P (b_{n} = 0) = e, P (b_{n} = −1) = f, at least 2 of d, e, and f are non-zero, and d + e + f = 1. Let

g = \{ \begin{matrix}2 & if a = c \\ 1 & if a ≠ c \end{matrix} .

Let ϵ > 0 be given. Then for sufficiently large odd p, ∥P_{n} − U∥ < ϵ if n > c_{1}(log p log log p)^{g} for some value c_{1} > 0 (which may depend on a, b, c, d, e, and f but not p) but ∥P_{n} −U∥ < ϵ for almost all odd p if n > c_{2}(log p)^{g} for some value c_{2} > 0 (which also may depend on a, b, c, d, e, and f but not p). By almost all odd p, we mean that the proportion of odd p between 1 and p_{0} satisfying this condition approaches 1 as p_{0} → ∞. Theorem 3: With the notation of Theorem 2, there exists a value c_{3} > 0 such that, given ϵ > 0, ∥P_{n} − U∥ > 1 − ϵ if n < c_{3}(log p)^{g} and p is odd.

Theorems 2 and 3 answer, up to a factor of (log log p)^{2}, a question posed on p. 35 of Diaconis (1988). This question has a = b = c = 1/3 and d = e = f = 1/3 and asks how long it takes for X_{n} to get close to uniformly distributed on Z/pZ.

This paper also shows the following results where a_{n} and b_{n} may be dependent. Theorem 4: Let p be odd. Suppose (a_{n}, b_{n}) is defined so that P (a_{n} = 2) = P (a_{n} = (p + 1)/2) = (1/2)(1 − P (a_{n} = 1)) ≠ 0 and that b_{n} has a fixed distribution on Z and has finitely many possible values. Suppose the (a_{n}, b_{n})’s are i.i.d. Let ϵ > 0 be given. There exists a value c > 0 (not depending on p but depending on the values for the probabilities on (a_{n}, b_{n})) such that if n < c(log p)^{2}, then ∥P_{n} − U∥ > 1 − ϵ for sufficiently large p. Theorem 5: Suppose that p is odd and that (a_{n}, b_{n}) is chosen uniformly from (2, 1), (2, −1), (((p + 1)/2), ((p + 1)/2)), and (((p + 1)/2), −((p + 1)/2)). Then there exists a value c > 0 such that if n > c(log p)^{3}, ∥P_{n} − U∥ → 0 as p → ∞.

NOTATION AND BACKGROUND

Let P be a probability on Z/pZ. Define the variation distance of P from the uniform distribution U by

∥P − U∥ := \frac{1}{2} ∑_{s∈Z/pZ} |P (s) − \frac{1}{p}|.

One can readily show that

∥P − U∥ = max_{A⊆Z/pZ} |P (A) − U(A)|.

This variation distance is the one defined in Diaconis (1988).

Suppose X_{0} = 0 and

X_{n+1} = a_{n}X_{n} + b_{n} (mod p)

where the (a_{n}, b_{n})’s are i.i.d. We shall define P_{n} to be the probability distribution of X_{n} (where X_{n} is viewed as a random variable on Z/pZ). By abuse of notation, we shall also call ∥P_{n} − U∥ the distance of X_{n} from uniform.

Let X and Y be independent random variables on Z/pZ with probability distributions P and Q. Let P ∗ Q be the probability distribution of X + Y. The following proposition will be useful: Proposition 1:

∥P ∗ Q − U∥ ≤ ∥P − U∥

The proof is left as an exercise.

PROOF OF THEOREM 1

In this section, we shall prove Theorem 1. Throughout this section, we shall assume p is odd. The proof builds on the following lemmas. Lemma 1: Suppose Y_{0} = 0 and

Y_{n+1} = 2Y_{n} + b_{n} (mod p)

where b_{n} is as in Theorem 1. If n > c_{1} log_{2} p where c_{1} > 1, then ∥Q_{n} − U∥ → 0 as p → ∞ if Q_{n} is the probability distribution of Y_{n}.

Proof: If n ≥ 1, then Y_{n} (viewed in Z) is uniform on the odd integers from −2^{n} + 1 to 2^{n} − 1. Since 2^{n} > p^{c_{1}} and c_{1} > 1, the result follows by a straightforward consideration of these odd integers mod p.

The next lemma is a property of random walks. Lemma 2: Suppose P (W_{n} = 1) = P (W_{n} = −1) = 1/2. Let V_{n} = ∑_{i=1}^{n} W_{i} (with V_{0} = 0), let M_{n} = max_{i=0,...,n} V_{i}, and let m_{n} = min_{i=0,...,n} V_{0}. Given c_{1} > 0, there exists a value c such that if n > c(log p)^{2} then P (M_{n} − m_{n} ≤ c_{1} log_{2} p) < ϵ/2.

The proof of this lemma may be derived quickly from the Central Limit Theorem. Next observe that

X_{1} = b_{1}
X_{2} = a_{2}b_{1} + b_{2}
X_{3} = a_{3}a_{2}b_{1} + a_{3}b_{2} + b_{3}
...

Consider the sequence a_{n+1}, a_{n+1}a_{n}, ..., a_{n+1}a_{n}...a_{2}. Observe that this sequence can also be written as 2^{V_{1}}, 2^{V_{2}}, ..., 2^{V_{n}} where V_{1}, ..., V_{n} are as in Lemma 2. If j > 0, 2^{−j} denotes ((p + 1)/2)^{j} in the integers mod p since 2 is a unit in Z/pZ and has multiplicative inverse (p + 1)/2.

Suppose a_{1}, ..., a_{n+1} are given such that M_{n} − m_{n} > c_{1} log_{2} p where the values M_{n} and m_{n} refer to the values V_{1}, ..., V_{n} in the previous paragraph. Let Z_{n+1} = a_{n+1}...a_{2}b_{1} + a_{n+1}...a_{3}b_{2} + ... + b_{n+1} be a random variable for these particular choices of a_{1}, ..., a_{n+1} but with b_{1}, ...b_{n+1} still being i.i.d. random variables with the same distribution as in Theorem 1. Let R_{n} be the distance of Z_{n} from uniform. Note that since p is odd, R_{n+1} is also the distance of 2^{−m_{n}}Z_{n+1} from the uniform. Note that

2^{−m_{n}}Z_{n+1} = ∑_{i=0}^{M_{n}−m_{n}} 2^{i}b̃_{i} + ∑_{i=M_{n}−m_{n}+1}^{n} 2^{r(i)}b̃_{i}

where the values r(i) are determined by a_{1}, ..., a_{n+1} and b̃_{i} are i.i.d. random variables with the same distribution of b_{n}. (The b̃_{i}’s are obtained from the b_{i}’s by relabeling the subscripts.) Since r(i) is determined and the b̃_{i}’s are i.i.d., Proposition 1 says that the distance of 2^{−m_{n}}Z_{n+1} from uniform is less than the distance of

∑_{i=0}^{M_{n}−m_{n}} 2^{i}b̃_{i}

from uniform; the latter distance goes to to 0 as p → ∞. Since P (M_{n}−m_{n} ≤ c_{1} log_{2} p) < ϵ/2, we may thus conclude that ∥P_{n} − U∥ < ϵ for large enough odd values of p.

PROOF OF THEOREM 2

The technique illustrated by the proof of Theorem 1 is readily generalizable to other distributions for a_{n} and b_{n}. Theorem 2 proves a generalization, but the replacement for Lemma 1 is more complicated. Throughout this section, we assume p is odd. Lemma 3: Suppose Y_{0} = 0 and Y_{n+1} = 2Y_{n} + b_{n} (mod p). Let Q_{n} be the probability distribution of Y_{n}. For some value c̃_{1} > 0 if n > c̃_{1} log p log log p, then ∥Q_{n} − U∥ → 0 as p → ∞. For some value c̃_{2} > 0 if n > c̃_{2}(log p) then ∥Q_{n} − U∥ → 0 for almost all odd p. (Note c̃_{1} and c̃_{2} may depend on d, e, and f.)

This lemma is a straightforward generalization of Theorems 1 and 3 of Chung, Diaconis, and Graham (1987) and is left to the reader.

Lemma 2 is replaced by the following lemma. Lemma 4: Suppose P (W_{n} = −1) = a, P (W_{n} = 0) = b, and P (W_{n} = 1) = c with a, b, and c as in Theorem 2. Let V_{n}, M_{n}, and m_{n} be obtained from W_{1}, ..., W_{n} as in Lemma 2. Then given c̃_{1} > 0 and c̃_{2} > 0, there exist values c_{1} > 0 and c_{2} > 0 (which may depend on a, b, and c) such that P (M_{n} − m_{n} ≤ c̃_{1} log p log log p) < ϵ/2 if n > c_{1}(log p log log p)^{g} while P (M_{n} − m_{n} ≤ c̃_{2} log p) < ϵ/2 if n > c_{2}(log p)^{g} where g is as defined in Theorem 2.

This lemma can be shown from the Central Limit Theorem.

The remainder of the proof of Theorem 2 is virtually identical to the last portion of the proof of Theorem 1 provided that one takes into account the two cases in Lemma 3.

PROOF OF LOWER BOUNDS

The proof of Theorem 3 is straightforward in the case g = 1. Since there are no more than 9^{c_{3} log p} = p^{c_{3} log 9} possible values that X_{n} can have if n = ⌊c_{3} log p⌋, then the set of also possible values of X_{n} will have probability under p^{c_{3} log 9−1} under U. If c_{3} < 1/ log 9, this implies that ∥P_{n} − U∥ → 1 as p → ∞.

Next consider the case where g = 2. Define M_{n} and m_{n} as in the proof of Theorem 1. Let ϵ > 0 be given. By elementary considerations from the Central Limit Theorem and a reflection principle, we can show that there exists a value c_{3} > 0 such that if n = ⌊c_{3}(log p)^{2}⌋, then P (M_{n} − m_{n} > ⌊(1/4) log_{2} p⌋) < ϵ/2. If M_{n} − m_{n} ≤ ⌊(1/4) log_{2} p⌋, consider

2^{⌊(1/4) log_{2} p⌋}X_{n+1} = (2^{⌊(1/4) log_{2} p⌋}a_{n}...a_{2})b_{1} + (2^{⌊(1/4) log_{2} p⌋}a_{n}...a_{3})b_{2} + ... + 2^{⌊(1/4) log_{2} p⌋}b_{n}.

Observe that since ((p + 1)/2)2 ≡ 1 (mod p), then

2^{⌊(1/4) log_{2} p⌋}a_{n}...a_{2}, 2^{⌊(1/4) log_{2} p⌋}a_{n}...a_{3}, ..., 2^{⌊(1/4) log_{2} p⌋} ⊆ [1, 2^{2⌊(1/4) log_{2} p⌋}] (mod p).

There are ⌊c_{3}(log p)^{2}⌋ terms on the right. Mod p, each term is in the range

[−2^{2⌊(1/4) log_{2} p⌋}, 2^{2⌊(1/4) log_{2} p⌋}] ⊆ [−\sqrt{p}, \sqrt{p}] .

Thus

2^{⌊(1/4) log_{2} p⌋}X_{n+1} ⊆ [−\sqrt{p}c_{3}(log p)^{2}, \sqrt{p}c_{3}(log p)^{2}] (mod p).

Thus, for this choice of n,

\begin{aligned}∥P_{n} − U∥ & > (1 − (ϵ/2)) − \frac{1 + 2\sqrt{p}c_{3}(log p)^{2}}{p} \\ & > 1 − ϵ \end{aligned}

for sufficiently large p.

Theorem 4 is a straightforward generalization of the previous theorem.

In some cases where b_{n} does not have a fixed distribution on Z, similar claims may still be made: Corollary: Let p be odd. If P ((a_{n}, b_{n}) = (2, 1)) = P ((a_{n}, b_{n}) = ((p + 1)/2, −(p + 1)/2)) = 1/2, then, given ϵ > 0, there exists a values c > 0 such that if n < c(log p)^{2}, then ∥P_{n} −U∥ > 1 − ϵ for sufficiently large p.

Proof: X_{n} and 2X_{n} are the same distance from uniform. Since 2(−(p + 1)/2) ≡ −1 (mod p), we have

2X_{n} = a_{n−1}...a_{2}b̃_{1} + a_{n−1}...a_{3}b̃_{2} + ... + b̃_{n−1} (mod p)

with P ((a_{n}, b̃_{n}) = (2, 2)) = P ((a_{n}, b̃_{n}) = ((p + 1)/2, −1)) = 0.5. The previous theorem provides the lower bound for how long it takes for X_{n} to get close to uniform on Z/pZ.

PROOF OF THEOREM 5

The proof utilizes the upper bound lemma of Diaconis and Shahshahani. Let P be a probability on Z/pZ and let

P̂(k) = ∑_{j=0}^{p−1} P (j)q^{jk}

where q := q(p) := e^{2πi/p}. The expression P̂(k) is called the Fourier transform of P in Z/pZ. The upper bound lemma uses techniques from Fourier analysis to conclude Lemma 5:

∥P − U∥^{2} ≤ \frac{1}{4} ∑_{k=1}^{p−1} |P̂(k)|^{2}.

A generalization of this lemma is described and proved in Diaconis (1988).

The proof of the theorem shall use a recurrence relation among the Fourier transforms; a similar relation is used in Hildebrand (1990, 1993a, 1993b). The recurrence relation among the Fourier transforms will follow from the following lemma. Lemma 6:

P (X_{n+1} = k) = \frac{1}{4}P (X_{n} = ((p + 1)/2)k − ((p + 1)/2))

+ \frac{1}{4}P (X_{n} = ((p + 1)/2)k + ((p + 1)/2))

+ \frac{1}{4}P (X_{n} = 2k − 1) + \frac{1}{4}P (X_{n} = 2k + 1)

The proof is straightforward and follows from the recurrence relation relating X_{n+1} to X_{n}.

The following lemma is similar to a recurrence in Hildebrand (1990,1993a): Lemma 7:

\begin{aligned}P̂_{n+1}(k) & = \frac{1}{4}P̂_{n}(2k)q^{k} + \frac{1}{4}P̂_{n}(2k)q^{−k} \\ & + \frac{1}{4}P̂_{n}(((p + 1)/2)k)q^{((p+1)/2)k} + \frac{1}{4}P̂_{n}(((p + 1)/2)k)q^{−((p+1)/2)k} \end{aligned}

Proof: First observe that

P̂_{n+1}(k) = ∑_{j=0}^{p−1} P (X_{n+1} = j)q^{jk}

= ∑_{j=0}^{p−1} \frac{1}{4}P (X_{n} = ((p + 1)/2)j − ((p + 1)/2))q^{jk}

+ ∑_{j=0}^{p−1} \frac{1}{4}P (X_{n} = ((p + 1)/2)j + ((p + 1)/2))q^{jk}

+ ∑_{j=0}^{p−1} \frac{1}{4}P (X_{n} = 2j − 1)q^{jk} + ∑_{j=0}^{p−1} \frac{1}{4}P (X_{n} = 2j + 1)q^{jk}

Observe that the mapping from j to ((p + 1)/2)j − ((p + 1)/2) is a bijection on Z/pZ since p is odd and since this mapping is the inverse of the bijection on Z/pZ which sends j to 2j + 1. Thus

∑_{j=0}^{p−1} P (X_{n} = 2j + 1)q^{jk} = ∑_{j=0}^{p−1} P (X_{n} = j)q^{(((p+1)/2)j−((p+1)/2))k}

= ∑_{j=0}^{p−1} P (X_{n} = j)q^{j(((p+1)/2)k)}q^{−((p+1)/2)k}

= P̂_{n}(((p + 1)/2)k)q^{−((p+1)/2)k}.

The other terms in the lemma follow similarly.

The recurrence in Lemma 7 provides the key to the proof of Theorem 5. By Lemma 7, we conclude that

|P̂_{n+1}(k)| ≤ \frac{1}{2}| cos 2πk/p| |P̂_{n}(2k)| + \frac{1}{2}|P̂_{n}(((p + 1)/2)k)|.

Let M_{n} = max_{k≠0} |P̂_{n}(k)|. Observe that M_{0} = 1 and that M_{n+1} < M_{n} if n ≥ 0. Also observe that if k ∈ S := ((1/8)p, (3/8)p) ∪ ((5/8)p, (7/8)p) (mod p) then |P̂_{n+a}(k)| ≤ 0.8M_{n} for a = 1, 2, 3, ... Thus we may claim that

|P̂_{n+1}(k)| ≤ \frac{1}{2}f(k)|P̂_{n}(2k)| + \frac{1}{2}|P̂_{n}(((p + 1)/2)k)|  (∗)

where f(k) = 0.8 if k ∈ S and f(k) = 1 of k ∉ S.

Note that if k ≠ 0 and k ∉ S, then 2^{b}k ∈ S (mod p) for some value b ≤ (log_{2} p). Since p is odd, we may view (p + 1)/2 as 2^{−1} in the multiplicative group of the units of Z/pZ. Let d = ⌊c_{1}(log p)^{2}⌋. By |P̂_{n+d}(k)| by expanding (∗) recursively d levels. Define W_{i} and V_{i} as in Lemma 2. By the Central Limit Theorem, V_{n} > log_{2} p with probability at least c_{2} > 0. Thus at least the fraction c_{2} of the terms will have a multiple of 0.8 coming from the f(k) term in (*). Thus for all n and k ≠ 0,

|P̂_{n+d}(k)| ≤ (0.8c_{2} + 1(1 − c_{2}))M_{n}.

Observe that that c_{3} := .8c_{2} + (1 − c_{2}) < 1 and that M_{n+d} ≤ c_{3}M_{n}. Thus for some value c_{4} > 0, M_{d⌊c_{4} log p⌋} ≤ c_{3}^{⌊c_{4} log p⌋} ≤ 1/p^{2} for large enough p. By the upper bound lemma, if n = d⌊c_{4} log p⌋, then ∥P_{n} − U∥^{2} < (1/4)((p − 1)/p^{2}) → 0 as p → 0.

PROBLEMS FOR FURTHER STUDY

Theorems 2 and 3 do not provide sharp bounds on the time it takes for X_{n} to get close to uniform; the bounds differ by a factor of a constant times (log log p)^{g}. This time may vary by such a factor; such variation appears in results proved in Chung, Diaconis, and Graham (1987) and Hildebrand (1993b). If g = 2, it is unclear whether such variation will hold, and this uncertainty provides a subject for further study.

Upper bounds for cases where a_{n} and b_{n} are dependent need improvement. Both generalizations of the method used in proving Theorem 5 and improvements of the upper bound in Theorem 5 form natural further problems worth studying.

The techniques in this paper can be extended to cases where a_{n} is either a, 1, or the multiplicative inverse of a if p and a are relatively prime. What happens if a_{n} takes on a broader range of values? For instance, what happens if a_{n} takes on the values 1, 2, 3, and the multiplicative inverses of 2 and 3 with certain probabilities?

ACKNOWLEDGEMENTS

The author thanks Persi Diaconis for suggesting some of the problems and acknowledges that some of this work is based on ideas in chapter 5 of Hildebrand (1990). The author also thanks Mark Conger for a couple of comments on an earlier version of the paper.

BIBLIOGRAPHY

Chung, F., Diaconis, P., and Graham, R.L. (1987) “A random walk problem arising in random number generation.” Ann. Prob. 15, 1148-1165.

Diaconis, P. (1988) Group Representations in Probability and Statistics. Hayward, Calif.: Institute of Mathematical Statistics.

Hildebrand, M. (1990) “Rates of Convergence of Some Random Processes on Finite Groups.” Ph.D. thesis, Harvard University Department of Mathematics.

Hildebrand, M. (1993a) “Random Processes of the Form X_{n+1} = a_{n}X_{n} + b_{n} (mod p).” Ann. Prob. 21.

Hildebrand, M. (1993b) “Random Processes of the Form X_{n+1} = a_{n}X_{n} + b_{n} (mod p) Where b_{n} Takes on a Single Value,” preprint.

Knuth, D. (1981) The Art of Computer Programming. Vol. II, 2nd ed. Menlo Park, Calif.: Addison-Wesley.

Xu, D. (1990) “On random walks on affine group,” Commun. Statist. - Theor. Meth. 19, 2925-2942. Corrigendum, Commun. Statist. - Theor. Meth. 20, 2737.