Re: sums of discrete uniform random variables

quasi <quasi@xxxxxxxx> writes:

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.

The "if" is easy.

For the "only if":
The probability generating function (pgf) of X_i is
g_n(s) = (1 + s + ... + s^(n-1))/n = (1-s^n)/(n (1-s)) for s <> 1.
The pgf of X_1 + ... + X_k is g_n(s)^k. Now let w be a primitive m'th
root of unity other than 1. If Z is an integer-valued random variable
with pgf f(s) that is uniformly distributed mod m, then we must have
f(w) = 0. So for X_1 + ... + X_k to be uniformly distributed mod m,
g_n(w)^k = 0, and therefore g_n(w) = 0. Thus we obtain that g_n(s)
is divisible by the m'th cyclotomic polynomial, and this only happens
if m divides n.
--
Robert Israel israel@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada
.

Relevant Pages

  • Re: Random choice of numbers
    ... quasi writes: ... For n in N, n> 2, let pbe the probability that if n numbers are ... Prove or disprove: pis rational, ... Of course if n-1 is divisible by k, ais divisible by n^k - ^k. ...
    (sci.math)
  • Re: sums of discrete uniform random variables
    ... variables, each uniformly distributed on the set {0,..., n-1}. ... Prove or disprove: ... and the rest are integer-valued variables with arbitrary ...
    (sci.math)
Loading