Re: sums of discrete uniform random variables

On Mon, 24 Dec 2007 04:03:56 -0500, quasi <quasi@xxxxxxxx> wrote:

On Mon, 24 Dec 2007 02:52:57 -0600, Robert Israel
<israel@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx> wrote:

quasi <quasi@xxxxxxxx> writes:

On Mon, 24 Dec 2007 02:54:50 -0500, quasi <quasi@xxxxxxxx> wrote:

On Mon, 24 Dec 2007 02:38:04 -0500, quasi <quasi@xxxxxxxx> wrote:

On Sun, 23 Dec 2007 23:35:04 -0800 (PST), Butch Malahide
<fred.galvin@xxxxxxxxx> wrote:

On Dec 24, 1:08 am, quasi <qu...@xxxxxxxx> wrote:
Let X_1, X_2, X_3, ... be independent, identically distributed random
variables, each uniformly distributed on the set {0,..., n-1}. In
other words, each X_i is uniformly distributed mod n.

Prove or disprove:

(X_1 + ... + X_k) mod m is uniformly distributed mod m iff m|n.

Do you really need all those assumptions? Wouldn't it be enough to
assume that one of the variables, say X_1, is uniformly distributed
mod m, and the rest are integer-valued variables with arbitrary
distributions?

Sure -- that's better, provided it's true, and it does seem like it
should be true.

Actually, the generalization you suggested makes it easier to see
what's going on.

Suppose X and Y are independent, integer-valued random variables and
such that (X mod m) is uniformly distributed mod m. Then ((X + Y) mod
m) must also be uniformly distributed mod m. The proof is obvious,
just by observing that for all a,b in {0, ..., m-1},

P(((X + Y) mod m) = a) | (Y mod m) = b) = 1/m

regardless of the value of b.

It follows that, for all a in {0, ..., m-1},

P(((X + Y) mod m) = a) = 1/m

proving that ((X + Y) mod m) is uniformly distributed, mod m.

I'll have to think about the converse.

Applying Butch Malahide's suggested generalization, and then
simplifying even further, here's a revised problem:

Suppose X,Y are independent random variables (but not necessarily
identically distributed) with values in {0, ..., m-1}.

Prove or disprove: If ((X + Y) mod m) is uniformly distributed mod m,
then either X or Y (or both) are uniformly distributed, mod m.

Remarks: It's true for m=2. The proof is easy.

It's also true for m=3. The proof is routine.

False in general. Try it for m = 4 with X taking values 0 and 2 with equal
probabilities, Y taking 0 and 1.

Yes, I see.

Perhaps it's true whenever m is prime?

Yes, if m is prime, it's true.

Proposition: If X,Y are independent integer valued random variables
such that, for some prime p, ((X + Y) mod p) is uniformly distributed
mod p, then either (X mod p) or (Y mod p) is uniformly distributed,
mod p.

proof:

Assume (X mod p) is not uniformly distributed, mod p.

For k = 0, ..., p-1, let

a[k] = P((X mod p) = k)

b[k] = P((Y mod p) = k)

For convenience, extend a,b cyclically.

Thus, if k in Z, where k < 0 or k > p -1, let

a[k] = a[(k mod p)]

b[k] = b[(k mod p)]

By hypothesis, for each fixed i = 0, ..., p-1

sum(a[i-j]*b[j],j=0..p-1) = 1/p

This can be written in matrix form as

A*b = (1/p)*u

where

A is the p x p matrix whose i,j'th entry is a[i-j]

b = <b[0],...,b[p-1]>, regarded as a column vector

u = <1,...,1>, a column vector with all entries equal to 1

Claim A is nonsingular.

Let A_1, ..., A_p denote the columns of A.

For convenience, let A_0 be an alias for A_p and
let A_(p+1) be an alias for A_1.

Note that each column is a cyclic shift by 1 of the previous column/

Let T be the p x p permutation matrix which maps each column to the
next one. Then for k = 1, ...,p we have T*A_k = A_(k+1)

It follows that A_k = T^(k-1)*A_1

Thus T^p = 1, so either T = 1 or T has order p.

Since, by assumption, X is not uniformly distributed, the entries of
A_1 are not constant. Hence, since T*A_1 = A_2 and since A_2 is the
same as A_1 except shifted cyclically by 1, it follows that A_2 is not
equal to A_1, so T is not the identity. Therefore T has order p, and
hence, the minimal polynomial for T is x^p - 1.

Thus, the matrices I, T, ..., T^(p-1) must be linearly independent
over Q, and hence also over R, since the entries of T are rational.

Since A_1 is nonzero, it follows that the vectors A_1, ..., A_k are
linearly independent over R. Therefore A is nonsingular, as claimed.

Noting that the sum of each row of A is exactly 1, it follows that

A*u = u

which implies

A*((1/p)*u) = (1/p)*u

But we know that

A*b = (1/p)*u

hence, since A is nonsingular, we deduce b = (1/p)*u.

It follows that (Y mod p) is uniformly distributed, mod p, as
required.

This completes the proof.

Remark: The above proposition yields an immediate negative answer to
G. A. Edgar's dice question.

quasi
.

Relevant Pages

  • Re: sums of discrete uniform random variables
    ... It follows that, for all a in {0, ..., m-1}, ... Suppose X,Y are independent random variables (but not necessarily ... Prove or disprove: If mod m) is uniformly distributed mod m, ...
    (sci.math)
  • Re: sums of discrete uniform random variables
    ... It follows that, for all a in {0, ..., m-1}, ... Suppose X,Y are independent random variables (but not necessarily ... Prove or disprove: If mod m) is uniformly distributed mod m, ...
    (sci.math)
  • Re: sums of discrete uniform random variables
    ... It follows that, for all a in {0, ..., m-1}, ... Suppose X,Y are independent random variables (but not necessarily ... Prove or disprove: If mod m) is uniformly distributed mod m, ...
    (sci.math)
Loading