Let $n_1,..,n_r$ be $r$ positive integers, and let $1 \leq k \leq n$, where $n=n_1+...+n_r$. Consider an urn containing $r$ different types of balls, $n_1$ balls of type 1, $n_2$ balls of type 2,...,$n_r$ balls of type $r$. Extract $k$ balls without replacement from the urn, and let $X=(X_1,...,X_r)$ where $X_i$ is the number of balls of type $i$ drawn. Then $X$ has a multivariate hypergeometric distribution. Consider now to draw $k$ balls from the urn with replacement, and let $Y=(Y_1,...,Y_r)$ where $Y_i$ is the number of balls of type $i$ drawn. Then $Y$ has a multinomial distribution, and we have \begin{equation} E\left(\frac{X}{k}\right)=E\left(\frac{Y}{k}\right)=\mu, \end{equation} where $\mu=(\mu_1,...,\mu_r)$, $\mu_i=n_i/n$. For every $x \in R^{r}$, let $||x||=max\{|x_1|,...,|x_r|\}$. Let $\delta > 0$. Does the following inequality \begin{equation} P \left( \left|\left| \frac{Y}{k} - \mu \right| \right| \geq \delta \right) \geq P \left( \left| \left| \frac{X}{k} - \mu \right| \right| \geq \delta \right) \end{equation} hold? This inequality was implicitly or explicitly used in several game-theoretic works by Shapley, Aumann and others (see the note below), but I could not find any proof.

Thank you very much for your attention.

Historical Note. This inequality was implicitely used for the first time by Lloyd Shapley in the work "Values of Large Games - VII" (a memorandum of the RAND corporation of December 1964). It can be found explicitely stated in Champsaur, Cooperation versus Competition, Journal of Economic Theory (1975), p. 415, Equation (6.13) and in Aumann and Drèze, Values of Markets with Satiation or Fixed Prices, Econometrica (1986), p. 1308. In the book Values of Non-Atomic Games, Aumann and Shapley call this inequality the principle that "sampling without replacment is better than sampling with replacement" (see p. 135, Note 1). Not to say, I could find no proof of the inequality in the literature.

  • $\begingroup$ I start thinking that the inequality is false even in the case $r=2$ (in which it reduces to $P(|Y_1/k-\mu_1| < \delta) \leq P(|X_1/k -\mu_1| < \delta)$, but I couldn't find any numerical counterexample. $\endgroup$ – Maurizio Barbato Oct 20 '14 at 19:03

After some research in the literature I found what I was looking for.

First of all, the inequality is not generally true, as I have conjectured in my previous comment. Take for example, $r=2$, $n_1=1, n_2=4$, $k=2$, $\delta=1/4$. Then you get

$ P( |X_1 / 2 - 1/5 | < 1/4) = 0.64$, while $P(| Y_1/2 - 1/5| < 1/4)=0.6$.

Another counterexample is the following: take $r=2$, $n_1=9, n_2=1$, $k=2$, $\delta=1/20$, for which you get

$ P( |X_1 / 2 - 9/10 | < 1/20) = 0.81$, while $P(| Y_1/2 - 1/5| < 1/4)=0.8$.

Note that in both examples, the closest integer to the mean is an extreme value (that is zero or $k$). I don't know if there is a counterexample in which this is not true.

Indeed, if $r=2$, then for any $\delta$ such that $\delta k \geq 1$, the required inequality holds. This is a consequence of the inequalities proved for the first time by Werner Uhlmann in Vergleich der hypergeometrischen mit der Binomial-Verteilung, Metrika, 10, 145-148 (see the on-line note of R.M.Dudley, An Exposition of the Uhlmann (1966) Inequality Bounding Hypergeometric by Binomial Tail Probabilities, and also Orlitsky & El Gamal, Average and Randomized Communication Complexity, IEEE Transactions on Information Theory, 36 (1990), p. 14).

Let us finally note that all the quoted works in which this "uniformly better principle" was used, it was only a heuristic argument to infer that a Chernoff-type inequality would hold for the hyperometric distribution too, and not only for th binomial distribution. But this is exactly the Hoeffding-Chvatal inequality (see my other question "A Law of Large Numbers without Replacement"), which the authors simply did not know!


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.