Probability of repeatedly selecting object in group

Question

There are n objects in a list. N random numbers are generated, each pointing to a height in the list. Each time an object gets "hit", it gets 1 point.

What is the probability that an object gets: 1 point, 2 points, 3 points, etc.

I wrote a script that tests it. The result for 1 million objects, so, 36%, 18%, 6%, 1.5%, 0.3%, etc. How is this calculated mathematically? I asked this question, and it was closed, but there is no reason to close it.

population: 1000000
results: 
1:  368282 ,  36.8282 %
2:  184036 ,  18.4036 %
3:  61046 ,  6.1046000000000005 %
4:  15465 ,  1.5465 %
5:  3009 ,  0.3009 %
6:  519 ,  0.0519 %
7:  56 ,  0.0056 %
8:  11 ,  0.0011 %
9:  1 ,  0.000099 %

The script,

# cook your dish here
import math
import random
population = 10*6
registry = [0]population
count = []
for i in range(population):
    randomNumber = random.randint(0, population-1)
    registry[randomNumber] += 1
    if len(count) < registry[randomNumber]: count.append(0)
for i in range(population):
    if registry[i] != 0: count[registry[i]-1]+=1
print("population:", population)
print("results: ")
for i in range(len(count)):
    print(i+1, ": ", count[i], ", ", count[i]/population*100, "%")

Answer 1

Collecting comments,

The probability a specific object was sampled $k$ times with replacement can be seen by counting techniques or binomial distribution as being $$\Pr(X=k)=\frac{\binom{n}{k}(n-1)^{n-k}}{n^n}$$

This, seen by choosing which $k$ of the samplings resulted in our desired object, for the remaining $n-k$ of the samplings choosing which other object was chosen, taken over the $n^n$ different possible ways of sampling our $n$ objects.

We can investigate what happens as we let $n$ continue to grow large. For this, we must first recognize that $\binom{n}{k}=\dfrac{n(n-1)(n-2)\cdots(n-k+1)}{k!}$. In particular, $\binom{n}{k}\sim \frac{n^k}{k!}$ keeping only the first term after expansion as all other terms are of lower order which disappear as we take the limit anyways.

We have $\lim\limits_{n\to\infty}\dfrac{\binom{n}{k}(n-1)^{n-k}}{n^n}=\lim\limits_{n\to\infty}\dfrac{\frac{n^k}{k!}(n-1)^{n-k}}{n^n}=\frac{1}{k!}\lim\limits_{n\to\infty}(1-\frac{1}{n})^{n-k}=\frac{1}{k!}\cdot e^{-1}$

Indeed, this matches closely with your experimental results.

$\begin{array}{c|c|c}k&\text{Your experimental result}&\text{Exact theoretical result}\\\hline 0&.367575&\frac{1}{e}\approx0.36787944\dots\\1&.368282&\frac{1}{e}\approx0.36787944\dots\\ 2&.184036&\frac{1}{2e}\approx0.18393972\dots\\ 3&.061046&\frac{1}{3!e}\approx0.06131324\dots\\ 4&.015465&\frac{1}{4!e}\approx0.01532831\dots\\ 5&.003009&\frac{1}{5!e}\approx0.00306566\dots\\ 6&.000519&\frac{1}{6!e}\approx0.00051094\dots\\ 7&.000056&\frac{1}{7!e}\approx0.00007299\dots\\ \vdots\end{array}$

(Note: $0! = 1$ and so the formula above works for $k=0$ as well. We have in this case that $\Pr(X=0)=\Pr(X=1)=\frac{1}{e}$)

Note further that the expected number of these elements who were never chosen or were chosen exactly once etc... will simply be $n$ times their respective probability of a particular element being chosen that many times as per the linearity of expectation.