Given a discrete probability distribution with $n$ possible outcomes and the task of repeatedly sampling until getting each outcome at least once, does the uniform distribution give the smallest expected value for the total number of samples?

Clement C. 07/11/2018.

**Yes.** This is shown e.g. in [1], under the name *Collector's inequality*:

The result we wish to point out is that $A(\mathbf{p})$ is a Schur-convex function of the probability vector $\mathbf{p}$. That is, if $\mathbf{p} \gg \mathbf{q}$, then $A(\mathbf{p}) > A(\mathbf{q})$. Thus, the minimum value of $A(\mathbf{p})$ occurs when $\mathbf{p}$ is the uniform distribution $\mathbf{u} = (1/n,\dots,1/n)$.

[1] Clevenson, M. Lawrence, and William Watkins. *Majorization and the Birthday Inequality.* Mathematics Magazine, vol. 64, no. 3, 1991, pp. 183–188. JSTOR, JSTOR, www.jstor.org/stable/2691301.

saulspatz 07/11/2018.

In the paper "Birthday paradox, coupon collectors, caching algorithms and self-organizing search" equation $(13b)$ gives the expected number of draws to get a complete collection of $m$ coupons, where coupon $i$ has probability $p_i$ as $$\int_0^{\infty}\left(1-\prod_{i=1}^m(1-e^{-p_it})\right)\mathrm{dt}$$ Clearly it is enough to show that for every $t\ge0,$the maximum value of $\prod_{i=1}^m(1-e^{-p_it}),$ subject to $0\le p_i,\ i=1,\dots,m$ and $\sum_{i=1}^mp_i=1,$ occurs when all the $p_i=1/m.$ This is easy; take the logarithm of the product and use Lagrange multipliers.

joriki 07/11/2018.

Ignore all but two of the coupon types. Conditional on the combined number $n$ of coupons of these two types having been drawn, the probability that both types have been drawn is $1-p^n-(1-p)^n$, where $p$ is the probability that a coupon of one of these two types is of the first type. This is maximal for $p=\frac12$. Thus a distribution is only optimal if $p=\frac12$ for all pairs of types, that is, if it is uniform.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

- Solution to rarity-generalized coupon-collector's problem?
- Expiring coupon collector's problem
- Probability distribution in the coupon collector's problem
- Expected Value - Uniform distribution over infinite interval
- Coupon Collector's Problem — Expected Value of each item
- Variation of Coupon Collector's Problem
- Variant of the Coupon Collector's Problem with Two Probabilities
- Coupon Collector's Problem with Partial Collections and Coupon Packages
- does it make sense to ask the expected value for discrete values in non-enumerable sets?
- Expected Distribution of the Outcome Counts When Sampling from a Categorical Random Variable

- What to tell students who want to know how to succeed in your class
- Is it a good practice to create a desktop shortcut on mac?
- Why is the debate on the composition of the U.S. Supreme Court so politicised?
- How to dispel greater invisibility?
- Why hasn't Rita Skeeter registered as an Animagus?
- Is there a name for text that reads the same upside-down?
- Can Find Familiar be cast using the Magic Initiate feat?
- Where can I find the list of the example images of graphicx?
- How did the Kavanaugh confirmation move so quickly despite the serious allegations?
- Was the German V2 rocket the only weapon whose production killed more than its use?
- Mortgage interest tax deduction
- Will an array of multiple ion engines still be more efficient than a single chemical engine?
- C++ code to sort a list of elements
- 100 using only 5 number of digits
- remove comma from a specific portion of a long string
- Etiquette regarding borrowing of power tools
- Unique buffer for each set of points separately and in one procedure in QGIS
- One liner to check for file exists
- How to communicate to my aunt that she made an honest mistake when buying food for a family meal?
- How would a 16-year-old girl from Cleopatra's era curse?
- Why the A380 doesn't have front windows on the top floor?
- How do you write unit tests for code with difficult to predict results?
- Biggest possible battleship that can be built?
- Be there, for the square