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}$.

  • 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