Probability of an average of naturals being also natural

67 Views Asked by At

Probably not much of a hard question, but still annoys me that I can't find an easy answer.

Let's imagine we have an audience of n people and each can give a score from 0 to m (equally probable) and that score is an integer number. What is the probability that the average score for these people will be also integer?

I did try some basic calculations but did not progress too much here so I got nothing to "show". And if anything, this question is more of an .. academic interest to me. Perhaps there is a solution known already?

1

There are 1 best solutions below

0
On BEST ANSWER

I don't know if an easy closed formula exists generally.

If you want to calculate the probabilites numerically, note that it doesn't matter what score each person gives, it only matters in which reminder class$\pmod n$ the score lies. So each player chooses a reminder class$\pmod n$ according to a probability distribution $(p_0, p_1,\ldots,p_{n-1})$ (where $p_0$ is the probability that a score is from reminder class $0$ is chosen, a.s.o).

Since the scores where equally probable, with $m+1=qn+r, 0\le r < n$ we get for $i=0,1,\ldots,n-1$: $p_i=\frac{q+1}{m+1}$ if $i<r$ and $p_i=\frac{q}{m+1}$ otherwise.

Note that for $r=0$ this comes out as a nice symmetrical $p_i=\frac1n$ for all $i$.

So given 2 distributions $s_1,s_2$ of reminder classes, what is the distribution of the sum of 2 random variables $x_1, x_2$ distributed according to $s_1$ and $s_2$, resp?

That's easy to calculate:

$$P(x_1+x_2 \equiv i\pmod n) = \sum_{k=0}^{n-1}s_1[k]s_2[i-k],$$

where the index $i-k$ is taken$\pmod n$.

Given this formula, one can calculate the distribution$\pmod n$ of the sum of the scores from 2 persons, then use the formula again to add a third person, a.s.o. After all $n$ persons have been added, the probability that the sum is in reminder class $0$ is the answer to the question.

In the cases where the distribution is uniformly over all reminder classes, the formula above shows that the sum is also uniformly distributed over the reminder classes. That means adding more and more persons will not change that and the final answer is $p=\frac1n$.

It also shows that for fixed $n$ that $\lim_{m \to \infty} p = \frac1n$, because we have a fixed set of continuous calculations to do to find the answer, and the initial probability distribution goes to $(\frac1n,\ldots,\frac1n)$. In other words, if you have $n=10$ but allow scores up to $m=1000$, it doesn't matter much that the probability to choose a number of reminder class $0$ is $\frac{101}{1001}$ and not $\frac1{10}$.