Results 1 to 10 of 10

Math Help - When number theory and probabilities clash

  1. #1
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927

    When number theory and probabilities clash

    Hey everybody,
    I'm trying to prove the following :

    Say you are given a set of n random numbers 0 \leq X_i \leq 255 with n > 1. Prove that P \left ( \sum_{i = 1}^n X_i \equiv a \pmod{256} \right ) = \frac{1}{256}. That is, prove that the sum of all the random numbers modulo 256 has an equal chance of being any number between 0 and 255.
    I've been trying various methods, but I cannot find a general way to prove this. I guess it requires playing with inequalities and common sense, but I already am having difficulties proving it when n = 2 (I've been separating it in two cases, the first one being X_1 + X_2 < 256, then I add both to find the desired probability). Does anyone have a general proof for this ?

    Thanks all
    Last edited by Bacterius; February 24th 2010 at 02:16 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    The statement is wrong: the probability should be \frac{1}{256}, i.e. every residue of X_1+\cdots+X_n modulo 256 is equally likely.

    There is a strong symmetry between the variables, and this is the key.

    Consider the simplest case to better understand it: if X_1, X_2,\ldots are random with equal probability to equal 0 or 1, and independent of each other, then X_1+X_2+\cdots+X_n\pmod{2} is 0 if X_n has same parity as X_1+\cdots+X_{n-1} and 1 else. However, by the case with n-1 variables, the parity of X_1+\cdots+X_{n-1} is 0 or 1 with same probability. Using independence, we conclude that the parities match with probability 1/2.

    The general case is the same. You can procede by induction: you have (equalities are modulo N) P(X_1+\cdots+X_n+X_{n+1}=x)=P(X_{n+1}=x-(X_1+\cdots+X_n)) =\sum_{y=0}^{N-1} P(X_{n+1}=x-y, X_1+\cdots+X_n=y) =\sum_{y=0}^{N-1} P(X_{n+1}=x-y)P(X_1+\cdots+X_n=y) (using independence) and the conclusion is immediate since each probability is \frac{1}{N} by assumption or induction hypothesis.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Yes my bad, it is indeed 256, just added this before posting and realized it was wrong a couple of seconds ago
    I'll edit. Thanks for your reply, I will attempt to prove it by induction and see how it flows.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    I don't understand
    and the conclusion is immediate since each probability is 1/N by assumption or induction hypothesis.
    I understand that P(X_{n + 1} = x - y) = \frac{1}{256} since only one value of y satisfies it, but I don't get the next probability. That's what I'm trying to prove, isn't it ? That P(X_1+\cdots+X_n=y) = \frac{1}{N} ? And if both probabilities are \frac{1}{N}, then the overall probability should be \frac{1}{N^2} which is incorrect ? This is really puzzling me. Can you give me a little more help on this one Laurent ?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    And I just thought of something, wouldn't it be possible to show that two random numbers a and b between 0 and 255 add up equally to any number between 0 and 255, then apply the same argument over the sum of all random numbers in an iterative way ? (like take the first two numbers, say their sum is equally distributed over 0.. 255, and take the next number, rince and repeat ?)

    If this is possible then I only have to show the case when n = 2, and if I really get stuck I can always prove it by exhaustive search (ugh I wish this won't happen, would look bad in my textbook)
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    Quote Originally Posted by Bacterius View Post
    I don't understand

    I understand that P(X_{n + 1} = x - y) = \frac{1}{256} since only one value of y satisfies it, but I don't get the next probability. That's what I'm trying to prove, isn't it ? That P(X_1+\cdots+X_n=y) = \frac{1}{N} ?
    No. This is a proof by induction, although I didn't write every detail. We assume that P(X_1+\cdots+X_n=y)=\frac{1}{N} for every y (this is obvious if n=1), and deduce that P(X_1+\cdots+X_n+X_{n+1}=x)=\frac{1}{N} for every x.

    Then you get \sum_{y=0}^{N-1}\frac{1}{N^2}=\frac{N}{N^2}=\frac{1}{N}.

    About your last post: adding the random variables one by one is exactly was is done in the above induction.

    You can write the induction step in a different way, like P(X_1+\cdots+X_{n+1}=x)=P(X+Y=x), where X=X_1+\cdots+X_n and Y=X_{n+1} are independent and uniformly distributed on \{1,\ldots,N\} by the induction hypothesis, so you are reduced to the case n=2. Maybe you like it better this way; the computation is exactly the same as the one I did (sum over the value y of Y), a very little bit longer but it may be clearer.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    Oh, I understand now, that was smart ! Thanks Laurent !
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    ...or without induction, every step at once:

    P(X_1+\cdots+X_n=x)= \sum_{0\leq x_1,\ldots,x_{n-1}<N}P(X_1=x_1,\ldots,X_{n-1}=x_{n-1},X_n=x-(x_1+\cdots+x_{n-1})) =\sum_{0\leq x_1,\ldots,x_{n-1}<N}\frac{1}{N^n}=\frac{N^{n-1}}{N^n}=\frac{1}{N}.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by Laurent View Post
    ...or without induction, every step at once:

    P(X_1+\cdots+X_n=x)= \sum_{0\leq x_1,\ldots,x_{n-1}<N}P(X_1=x_1,\ldots,X_{n-1}=x_{n-1},X_n=x-(x_1+\cdots+x_{n-1})) =\sum_{0\leq x_1,\ldots,x_{n-1}<N}\frac{1}{N^n}=\frac{N^{n-1}}{N^n}=\frac{1}{N}.

    DISCLAIMER: the writer of this post is NOT a probability/measure theory lover and, in fact, pretty much sucks at it.

    I don't see this clearly: take n=2\,,\,\,a=5\,,\,7\!\!\!\pmod{256} . Now, there are only 6 options to get a sum that equals 5\!\!\!\pmod{256} according to the conditions: 0-5\,,\,5-0\,,\,1-4\,,\,4-1\,,\,2-3\,,\,3-2, but there're 8 options for 7\!\!\!\pmod{256}: 7-0\,,\,0-7\,,\,1-6\,,\,6-1\,,\,2-5\,,\,5-2\,,\,3-4\,,\,4-3 , so this means the probability to obtain 5 is less than the prob. to obtain 7...or ain't so?

    Tonio
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    Quote Originally Posted by tonio View Post
    I don't see this clearly: take n=2\,,\,\,a=5\,,\,7\!\!\!\pmod{256} . Now, there are only 6 options to get a sum that equals 5\!\!\!\pmod{256} according to the conditions: 0-5\,,\,5-0\,,\,1-4\,,\,4-1\,,\,2-3\,,\,3-2, but there're 8 options for 7\!\!\!\pmod{256}: 7-0\,,\,0-7\,,\,1-6\,,\,6-1\,,\,2-5\,,\,5-2\,,\,3-4\,,\,4-3 , so this means the probability to obtain 5 is less than the prob. to obtain 7...or ain't so?
    What about 6+255=6+(-1)? Like in my previous post, the equality is to be understood modulo 256. In fact, everything would be simpler to write if we considered that X_i is uniformly chosen in \mathbb{Z}/256\mathbb{Z}, and this is what I implicitly do here.

    Thus 5 can be obtained as 0+5, 1+4, 2+3, 3+2, 4+1, 5+0, 6+255,... and it is immediate to see that there are 256 possibilities, and there is nothing specific to 5 here, so it would be the same for any sum. I guess suddenly the problems seems simpler than at first sight...
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Textbooks on Galois Theory and Algebraic Number Theory
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: July 8th 2011, 07:09 PM
  2. Approximate joint probabilities using marginal probabilities
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: June 23rd 2011, 05:04 AM
  3. Replies: 2
    Last Post: May 29th 2011, 10:23 PM
  4. Replies: 2
    Last Post: December 18th 2008, 06:28 PM
  5. Number theory, prime number
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 17th 2006, 09:11 PM

Search Tags


/mathhelpforum @mathhelpforum