There is a discrete probability distribution $X$ over domain $\{0,... ,N-1\}$.
I get a sample of size $M$, then iterate over the sample and count the number of occurrences for each $n \in \{0,...,N-1\}$,
then I calculate $Z(X, M) = \frac{\text{number of elements in the sample that occured more than once}}{N}$.

  1. What is the right name for $Z$?
  2. Is it true that the uniform distribution will maximize $Z$: $\max (\mathbb{E}[Z(X, M)]) = \mathbb{E}[Z(\operatorname{unif}\{0, N-1\}, M)]$?
  • $\begingroup$ For question 2, it is not even true for the smallest case of interest $M=2,N=2$: you would do better with a distribution which put almost all the probability on one of the two possible values and get $E[Z(X,2)] \approx \frac12$ rather than $E[Z(X,2)] = \frac14$ with your uniform distribution $\endgroup$
    – Henry
    Dec 12, 2022 at 1:34
  • $\begingroup$ @Henry I don't see how you got $\frac{1}{4}$. For $M=2$ $unif\{0,1\}$ will produce sample $(0, 1)$ with probability $\frac{1}{2}$, and samples $(0,0)$ or $(1,1)$ with probability $\frac{1}{4}$ each. This makes $E[Z(unif\{0,1\},2)]=\frac{1}{2}$. $\endgroup$ Dec 12, 2022 at 17:16
  • $\begingroup$ So $\mathbb{E}[Z(\operatorname{unif}\{0, 1\}, 2)] = \frac12\times \frac02+\frac14\times \frac12+\frac14\times \frac12 = \frac14$ when you count number of elements in the sample that occurred more than once and then divide by $N$ $\endgroup$
    – Henry
    Dec 12, 2022 at 17:21


You must log in to answer this question.