Re: sums of discrete uniform random variables

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.

quasi
.

Relevant Pages

  • 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: ... How can probability distinguish between any two distinct values in {0, ..., m-1}? ...
    (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)
  • 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