Does the uniform distribution minimize the expected value in the coupon collector's problem?

Stanley Yu 07/11/2018. 3 answers, 167 views
probability optimization coupon-collector

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?

3 Answers


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.


HighResolutionMusic.com - Download Hi-Res Songs

1 The Chainsmokers

Beach House flac

The Chainsmokers. 2018. Writer: Andrew Taggart.
2 (G)I-DLE

POP/STARS flac

(G)I-DLE. 2018. Writer: Riot Music Team;Harloe.
3 Anne-Marie

Rewrite The Stars flac

Anne-Marie. 2018. Writer: Benj Pasek;Justin Paul.
4 Ariana Grande

​Thank U, Next flac

Ariana Grande. 2018. Writer: Crazy Mike;Scootie;Victoria Monét;Tayla Parx;TBHits;Ariana Grande.
5 Clean Bandit

Baby flac

Clean Bandit. 2018. Writer: Jack Patterson;Kamille;Jason Evigan;Matthew Knott;Marina;Luis Fonsi.
6 BTS

Waste It On Me flac

BTS. 2018. Writer: Steve Aoki;Jeff Halavacs;Ryan Ogren;Michael Gazzo;Nate Cyphert;Sean Foreman;RM.
7 Imagine Dragons

Bad Liar flac

Imagine Dragons. 2018. Writer: Jorgen Odegard;Daniel Platzman;Ben McKee;Wayne Sermon;Aja Volkman;Dan Reynolds.
8 Nicki Minaj

No Candle No Light flac

Nicki Minaj. 2018. Writer: Denisia “Blu June” Andrews;Kathryn Ostenberg;Brittany "Chi" Coney;Brian Lee;TJ Routon;Tushar Apte;ZAYN;Nicki Minaj.
9 Brooks

Limbo flac

Brooks. 2018.
10 BlackPink

Kiss And Make Up flac

BlackPink. 2018. Writer: Soke;Kny Factory;Billboard;Chelcee Grimes;Teddy Park;Marc Vincent;Dua Lipa.
11 Diplo

Close To Me flac

Diplo. 2018. Writer: Ellie Goulding;Savan Kotecha;Peter Svensson;Ilya;Swae Lee;Diplo.
12 Rita Ora

Velvet Rope flac

Rita Ora. 2018.
13 Fitz And The Tantrums

HandClap flac

Fitz And The Tantrums. 2017. Writer: Fitz And The Tantrums;Eric Frederic;Sam Hollander.
14 Little Mix

Woman Like Me flac

Little Mix. 2018. Writer: Nicki Minaj;Steve Mac;Ed Sheeran;Jess Glynne.
15 Billie Eilish

When The Party's Over flac

Billie Eilish. 2018. Writer: Billie Eilish;FINNEAS.
16 K-391

Mystery flac

K-391. 2018.
17 Cher Lloyd

None Of My Business flac

Cher Lloyd. 2018. Writer: ​iamBADDLUCK;Alexsej Vlasenko;Kate Morgan;Henrik Meinke;Jonas Kalisch;Jeremy Chacon.
18 Backstreet Boys

Chances flac

Backstreet Boys. 2018.
19 Lil Pump

Arms Around You flac

Lil Pump. 2018. Writer: Rio Santana;Lil Pump;Edgar Barrera;Mally Mall;Jon Fx;Skrillex;Maluma;Swae Lee;XXXTENTACION.
20 Kelly Clarkson

Never Enough flac

Kelly Clarkson. 2018. Writer: Benj Pasek;Justin Paul.

Related questions

Hot questions

Language

Popular Tags