I am drawing $m$ objects randomly from $n$ types (with replacement). Then I count how many times each type is selected. What is the expected distribution of counts of each type?

More precisely, let $c_k$ be the count of objects of type $k$ (where $k=1\dots n$). What is the probability distribution of $c_k$?

My second question is about the distribution of counts. More precisely, let $q_c$ be the number of types that get counted $c$ times:

$$q_c = \sum_{k=1}^n \delta_{c_k,c}$$

where $\delta_{x,y}$ is Kronecker's delta.

What is the expected value of $q_c$?


I am drawing $m$ objects of $n$ types (with replacement). Let $c_{k}$ be the count of objects of type $k$ ($k=1,\dots,n$). We have: $$ \sum_{k=1}^{n}c_{k}=m $$ and the probabilities of counts are given by:

$$ P\left(c_{1},\dots,c_{n}\right)=\frac{m!}{n^{m}}\frac{1}{c_{1}!\dots c_{n}!} $$ Applying the multinomial theorem, we find that the marginal probability that $c_{k}=c$ is:


and it follows that $\left\langle c_{k}\right\rangle =m/n$. Let $q_{c}$ be the number of types that get selected $c$ times: $$ q_{c}=\sum_{k=1}^{n}\delta_{c_{k},c} $$ By noting that $\left\langle \delta_{c_{k},c}\right\rangle =p_{k}\left(c\right)$, we find: $$ \left\langle q_{c}\right\rangle =\binom{m}{c}\frac{\left(n-1\right)^{m-c}}{n^{m-1}} $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.