Re: sums of discrete uniform random variables

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?

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
    ... Suppose X,Y are independent random variables (but not necessarily ... Prove or disprove: If mod m) is uniformly distributed mod m, ... Claim A is nonsingular. ... Since, by assumption, X is not uniformly distributed, the entries of ...
    (sci.math)
  • Re: sums of discrete uniform random variables
    ... variables, each uniformly distributed on the set {0,..., n-1}. ... Prove or disprove: ... Suppose X and Y are independent, integer-valued random variables and ... It follows that, for all a in {0, ..., m-1}, ...
    (sci.math)
  • Re: sums of discrete uniform random variables
    ... variables, each uniformly distributed on the set {0,..., n-1}. ... Prove or disprove: ... Suppose X and Y are independent, integer-valued random variables and ... It follows that, for all a in {0, ..., m-1}, ...
    (sci.math)