0
$\begingroup$

Let $\{x_i\}_{i \in [k]}$ be randomly chosen independently from the uniform distribution over $\mathbb{Z}_p$.

What is the probability that $\Sigma_{i\in [k]} x_i = 0$?

1 Answers 1

1

The answer is $\frac{1}{p}$.

Assume that the first $k-1$ numbers are chosen. There is a unique number in $\mathbb{Z_p}$ for $x_k$ that would make the sum zero (the additive inverse of the sum of the first $k-1$ numbers).

The answer follows from Bayes' theorem.

Alternatively we can count the number of $k$-tuples that sum up to zero and divide it by the total number of such k-tuples: $\frac{p^{k-1}}{p^k}=\frac{1}{k}$.

  • 4
    Mind if I ask what the point was of asking and immediately answering your own question?2012-10-08
  • 0
    @Gerry, the question question came up while reading a paper, I thought about it a little bit and find the answer. I posted the question and the answer. Note that it is fine to answer your own questions, there is no requirement to wait before answering. To encourage sharing knowledge in this way SE has added a new future that you can post your answer answer at the same time that you post your question. If you want to know more about it please check [this post](http://blog.stackoverflow.com/2011/07/its-ok-to-ask-and-answer-your-own-questions/) on blog.SO.2012-10-09
  • 0
    @Gerry, also see [What is this “answer your own question” jazz?](http://meta.stackexchange.com/questions/132886/what-is-this-answer-your-own-question-jazz). ps: By the way, note that I still have to wait 2 days before accepting my own answer, if someone comes up with a better answer I may accept that in place of my own.2012-10-09
  • 0
    Yes, I was (dimly) aware of this feature, thanks. It still strikes me as strange. I hope I came across as curious, not critical.2012-10-09
  • 0
    @Gerry, you are welcome. :) Btw, you may want to check also this more recent blog post: [Encyclopedia Stack Exchange](http://blog.stackoverflow.com/2012/05/encyclopedia-stack-exchange/).2012-10-09