Skip to main content
Commonmark migration
Source Link

Here is a proof using generating functions. Let $c\geq 2$ and $k\geq 2$ be fixed.

Let $X=(X_1(n),\ldots,X_k(n))$ be the $k$-tuple of occupancy numbers at time $n$, i.e. $X_i(n)$ = number of bins of type $i$ drawn at time $n$.
Clearly $X$ has the multinomial distribution with parameters $n$ and $p=(p_1,\ldots,p_k)$. Therefore
$$\mathbb{P}( \max X_i(n)\leq c-1)=n!\,[t^n] \prod _{i=1}^n q_c(p_it)$$

where $q_c(t):=\sum_{j=0}^{c-1}\frac{t^j}{j!}$ is the $c$th partial sum of $\exp(t)$.

The following lemma is the key.

Lemma
When $p_i,p_j$ are each replaced by their arithmetic mean $a:=(p_i+p_j)/2$
$\mathbb{P}(\max X_i(n) \leq c-1 )$ will not decrease.
If $c\leq n \leq k(c-1)$ and all other $p_\ell$ are positive $\mathbb{P}(\max X_i(n) \leq c-1 )$ will strictly increase if $p_i\not = p_j$.

Proof Consider first the case of two factors. Let $x,y\in\mathbb{R}_+,x<y$. We show that $$ [t^m] q_c(xt)q_c(yt)\leq [t^m] \left(q_c(((x+y)/2)t\right)^2\;\;.$$It is easy to see that equality holds for $m\leq c-1$ and $m>2c-2$. Let $c\leq m \leq 2c-2$. We have $$m!\,[t^m] q_{c}(xt)q_c(yt)=(x+y)^m-\sum_{i=0}^{m-c} {m \choose i}\left(x^i y^{m-i}+y^i x^{m-i}\right) $$ For fixed sum $s=x+y$ the function $x \mapsto f(x):=\sum_{i=0}^{m-c} {m \choose i}\left(x^i y^{m-i}+y^i x^{m-i}\right)$ has the derivative $f^\prime(x)=(m-c+1){m \choose c} \left(x^{m-c+1}(s-x)^c-(s-x)^{m-c+1}x^c\right)$. Thus $x\mapsto f(x)$ is strictly decreasing (resp. increasing) on $[0,s/2]$ (resp. $[s/2,s]$), attaining its minimum at $x=s/2$. The rest is easy. End proof.

For any distribution $p=(p_1,\ldots,p_k)$ we have that $\mathbb{P}( \max X_i(n)\leq c-1)=1$ for $n\leq c-1$, and $\mathbb{P}( \max X_i(n)\leq c-1)=0$ for $n > k(c-1)$, so that only the cases $c\leq n \leq k(c-1)$ are of interest.

Corollary
For $c\leq n \leq k(c-1)$ the uniform distribution $p_1=\ldots=p_k=\tfrac{1}{k}$ uniquely maximises $\mathbb{P}(\max X_i(n) \leq c-1 )$.

Proof: Since we are maximising a continuous function (multivariate polynomial) on a compact set (simplex) the maximum is attained. Let $p$ be a maximising distribution. No $p_i$ can be $0$ (else replacing the last $0$ strictly increases the probability). But then $p$ can only be maximising if $p$ is the uniform distribution. End proof.

Remark Lemma 2 shows that the probability $\mathbb{P}(\max X_i(n) \leq c-1 )$ is a Schur-concave function on the simplex $p_i\geq 0, \sum_{i=1}^k p_i=1$. Possibly the result can be found under this heading in the literature (but a brief Google-search didn't reveal anything).

Here is a proof using generating functions. Let $c\geq 2$ and $k\geq 2$ be fixed.

Let $X=(X_1(n),\ldots,X_k(n))$ be the $k$-tuple of occupancy numbers at time $n$, i.e. $X_i(n)$ = number of bins of type $i$ drawn at time $n$.
Clearly $X$ has the multinomial distribution with parameters $n$ and $p=(p_1,\ldots,p_k)$. Therefore
$$\mathbb{P}( \max X_i(n)\leq c-1)=n!\,[t^n] \prod _{i=1}^n q_c(p_it)$$

where $q_c(t):=\sum_{j=0}^{c-1}\frac{t^j}{j!}$ is the $c$th partial sum of $\exp(t)$.

The following lemma is the key.

Lemma
When $p_i,p_j$ are each replaced by their arithmetic mean $a:=(p_i+p_j)/2$
$\mathbb{P}(\max X_i(n) \leq c-1 )$ will not decrease.
If $c\leq n \leq k(c-1)$ and all other $p_\ell$ are positive $\mathbb{P}(\max X_i(n) \leq c-1 )$ will strictly increase if $p_i\not = p_j$.

Proof Consider first the case of two factors. Let $x,y\in\mathbb{R}_+,x<y$. We show that $$ [t^m] q_c(xt)q_c(yt)\leq [t^m] \left(q_c(((x+y)/2)t\right)^2\;\;.$$It is easy to see that equality holds for $m\leq c-1$ and $m>2c-2$. Let $c\leq m \leq 2c-2$. We have $$m!\,[t^m] q_{c}(xt)q_c(yt)=(x+y)^m-\sum_{i=0}^{m-c} {m \choose i}\left(x^i y^{m-i}+y^i x^{m-i}\right) $$ For fixed sum $s=x+y$ the function $x \mapsto f(x):=\sum_{i=0}^{m-c} {m \choose i}\left(x^i y^{m-i}+y^i x^{m-i}\right)$ has the derivative $f^\prime(x)=(m-c+1){m \choose c} \left(x^{m-c+1}(s-x)^c-(s-x)^{m-c+1}x^c\right)$. Thus $x\mapsto f(x)$ is strictly decreasing (resp. increasing) on $[0,s/2]$ (resp. $[s/2,s]$), attaining its minimum at $x=s/2$. The rest is easy. End proof.

For any distribution $p=(p_1,\ldots,p_k)$ we have that $\mathbb{P}( \max X_i(n)\leq c-1)=1$ for $n\leq c-1$, and $\mathbb{P}( \max X_i(n)\leq c-1)=0$ for $n > k(c-1)$, so that only the cases $c\leq n \leq k(c-1)$ are of interest.

Corollary
For $c\leq n \leq k(c-1)$ the uniform distribution $p_1=\ldots=p_k=\tfrac{1}{k}$ uniquely maximises $\mathbb{P}(\max X_i(n) \leq c-1 )$.

Proof: Since we are maximising a continuous function (multivariate polynomial) on a compact set (simplex) the maximum is attained. Let $p$ be a maximising distribution. No $p_i$ can be $0$ (else replacing the last $0$ strictly increases the probability). But then $p$ can only be maximising if $p$ is the uniform distribution. End proof.

Remark Lemma 2 shows that the probability $\mathbb{P}(\max X_i(n) \leq c-1 )$ is a Schur-concave function on the simplex $p_i\geq 0, \sum_{i=1}^k p_i=1$. Possibly the result can be found under this heading in the literature (but a brief Google-search didn't reveal anything).

Here is a proof using generating functions. Let $c\geq 2$ and $k\geq 2$ be fixed.

Let $X=(X_1(n),\ldots,X_k(n))$ be the $k$-tuple of occupancy numbers at time $n$, i.e. $X_i(n)$ = number of bins of type $i$ drawn at time $n$.
Clearly $X$ has the multinomial distribution with parameters $n$ and $p=(p_1,\ldots,p_k)$. Therefore
$$\mathbb{P}( \max X_i(n)\leq c-1)=n!\,[t^n] \prod _{i=1}^n q_c(p_it)$$

where $q_c(t):=\sum_{j=0}^{c-1}\frac{t^j}{j!}$ is the $c$th partial sum of $\exp(t)$.

The following lemma is the key.

Lemma
When $p_i,p_j$ are each replaced by their arithmetic mean $a:=(p_i+p_j)/2$
$\mathbb{P}(\max X_i(n) \leq c-1 )$ will not decrease.
If $c\leq n \leq k(c-1)$ and all other $p_\ell$ are positive $\mathbb{P}(\max X_i(n) \leq c-1 )$ will strictly increase if $p_i\not = p_j$.

Proof Consider first the case of two factors. Let $x,y\in\mathbb{R}_+,x<y$. We show that $$ [t^m] q_c(xt)q_c(yt)\leq [t^m] \left(q_c(((x+y)/2)t\right)^2\;\;.$$It is easy to see that equality holds for $m\leq c-1$ and $m>2c-2$. Let $c\leq m \leq 2c-2$. We have $$m!\,[t^m] q_{c}(xt)q_c(yt)=(x+y)^m-\sum_{i=0}^{m-c} {m \choose i}\left(x^i y^{m-i}+y^i x^{m-i}\right) $$ For fixed sum $s=x+y$ the function $x \mapsto f(x):=\sum_{i=0}^{m-c} {m \choose i}\left(x^i y^{m-i}+y^i x^{m-i}\right)$ has the derivative $f^\prime(x)=(m-c+1){m \choose c} \left(x^{m-c+1}(s-x)^c-(s-x)^{m-c+1}x^c\right)$. Thus $x\mapsto f(x)$ is strictly decreasing (resp. increasing) on $[0,s/2]$ (resp. $[s/2,s]$), attaining its minimum at $x=s/2$. The rest is easy. End proof.

For any distribution $p=(p_1,\ldots,p_k)$ we have that $\mathbb{P}( \max X_i(n)\leq c-1)=1$ for $n\leq c-1$, and $\mathbb{P}( \max X_i(n)\leq c-1)=0$ for $n > k(c-1)$, so that only the cases $c\leq n \leq k(c-1)$ are of interest.

Corollary
For $c\leq n \leq k(c-1)$ the uniform distribution $p_1=\ldots=p_k=\tfrac{1}{k}$ uniquely maximises $\mathbb{P}(\max X_i(n) \leq c-1 )$.

Proof: Since we are maximising a continuous function (multivariate polynomial) on a compact set (simplex) the maximum is attained. Let $p$ be a maximising distribution. No $p_i$ can be $0$ (else replacing the last $0$ strictly increases the probability). But then $p$ can only be maximising if $p$ is the uniform distribution. End proof.

Remark Lemma 2 shows that the probability $\mathbb{P}(\max X_i(n) \leq c-1 )$ is a Schur-concave function on the simplex $p_i\geq 0, \sum_{i=1}^k p_i=1$. Possibly the result can be found under this heading in the literature (but a brief Google-search didn't reveal anything).

simplification and a remark on Schur concavity added
Source Link
esg
  • 3.3k
  • 11
  • 15

Here is a proof using generating functions. Let $c\geq 2$ and $k\geq 2$ be fixed.

Let $X=(X_1(n),\ldots,X_k(n))$ be the $k$-tuple of occupancy numbers at time $n$, i.e. $X_i(n)$ = number of bins of type $i$ drawn at time $n$.
Clearly $X$ has the multinomial distribution with parameters $n$ and $p=(p_1,\ldots,p_k)$. Therefore
$$\mathbb{P}( \max X_i(n)\leq c-1)=n!\,[t^n] \prod _{i=1}^n q_c(p_it)$$

where $q_c(t):=\sum_{j=0}^{c-1}\frac{t^j}{j!}$ is the $c$th partial sum of $\exp(t)$.

The following lemma is the key.

Lemma
When $p_i,p_j$ are each replaced by their arithmetic mean $a:=(p_i+p_j)/2$
(1) $\mathbb{P}(\max X_i(n) \leq c-1 )$ will not decrease.
(2)If $c\leq n \leq k(c-1)$ and all other $p_\ell$ are positive $\mathbb{P}(\max X_i(n) \leq c-1 )$ will strictly increase if $p_i\not = p_j$.   

Proof (1) ConsiderConsider first the case of two factors. Let $x,y\in\mathbb{R}_+,x<y$. We show that $$ [t^m] q_c(xt)q_c(yt)\leq [t^m] \left(q_c(((x+y)/2)t\right)^2\;\;.$$It is easy to see that equality holds for $m\leq c-1$ and $m>2c-2$. Let $c\leq m \leq 2c-2$. We have $$m!\,[t^m] q_{c}(xt)q_c(yt)=(x+y)^m-\sum_{i=0}^{m-c} {m \choose i}\left(x^i y^{m-i}+y^i x^{m-i}\right) $$ For fixed sum $s=x+y$ the function $x \mapsto f(x):=\sum_{i=0}^{m-c} {m \choose i}\left(x^i y^{m-i}+y^i x^{m-i}\right)$ has the derivative $f^\prime(x)=(m-c+1){m \choose c} \left(x^{m-c+1}(s-x)^c-(s-x)^{m-c+1}x^c\right)$. Thus $x\mapsto f(x)$ is strictly decreasing (resp. increasing) on $[0,s/2]$ (resp. $[s/2,s]$), attaining its minimum at $x=s/2$. The rest is easy. End proof.

For any distribution $p=(p_1,\ldots,p_k)$ we have that $\mathbb{P}( \max X_i(n)\leq c-1)=1$ for $n\leq c-1$, and $\mathbb{P}( \max X_i(n)\leq c-1)=0$ for $n > k(c-1)$, so that only the cases $c\leq n \leq k(c-1)$ are of interest.

Corollary
For $c\leq n \leq k(c-1)$ the uniform distribution $p_1=\ldots=p_k=\tfrac{1}{k}$ uniquely maximises $\mathbb{P}(\max X_i(n) \leq c-1 )$.

Proof: Since we are maximising a continuous function (multivariate polynomial) on a compact set (simplex) the maximum is attained. Let $p$ be a maximising distribution. If some No $p_i$ arecan be $0$ we may replace $p$ by a distribution which has all $p_i$ positive ( by partelse replacing the last (1) of$0$ strictly increases the lemmaprobability). But But then (by part 2 of the lemma) $p$ can only be maximising if $p$ is the uniform distribution. End proof.

Remark Lemma 2 shows that the probability $\mathbb{P}(\max X_i(n) \leq c-1 )$ is a Schur-concave function on the simplex $p_i\geq 0, \sum_{i=1}^k p_i=1$. Possibly the result can be found under this heading in the literature (but a brief Google-search didn't reveal anything).

Here is a proof using generating functions. Let $c\geq 2$ and $k\geq 2$ be fixed.

Let $X=(X_1(n),\ldots,X_k(n))$ be the $k$-tuple of occupancy numbers at time $n$, i.e. $X_i(n)$ = number of bins of type $i$ drawn at time $n$.
Clearly $X$ has the multinomial distribution with parameters $n$ and $p=(p_1,\ldots,p_k)$. Therefore
$$\mathbb{P}( \max X_i(n)\leq c-1)=n!\,[t^n] \prod _{i=1}^n q_c(p_it)$$

where $q_c(t):=\sum_{j=0}^{c-1}\frac{t^j}{j!}$ is the $c$th partial sum of $\exp(t)$.

The following lemma is the key.

Lemma
When $p_i,p_j$ are each replaced by their arithmetic mean $a:=(p_i+p_j)/2$
(1) $\mathbb{P}(\max X_i(n) \leq c-1 )$ will not decrease
(2)If $c\leq n \leq k(c-1)$ and all $p_\ell$ are positive $\mathbb{P}(\max X_i(n) \leq c-1 )$ will strictly increase if $p_i\not = p_j$.  Proof (1) Consider first the case of two factors. Let $x,y\in\mathbb{R}_+,x<y$. We show that $$ [t^m] q_c(xt)q_c(yt)\leq [t^m] \left(q_c(((x+y)/2)t\right)^2\;\;.$$It is easy to see that equality holds for $m\leq c-1$ and $m>2c-2$. Let $c\leq m \leq 2c-2$. We have $$m!\,[t^m] q_{c}(xt)q_c(yt)=(x+y)^m-\sum_{i=0}^{m-c} {m \choose i}\left(x^i y^{m-i}+y^i x^{m-i}\right) $$ For fixed sum $s=x+y$ the function $x \mapsto f(x):=\sum_{i=0}^{m-c} {m \choose i}\left(x^i y^{m-i}+y^i x^{m-i}\right)$ has the derivative $f^\prime(x)=(m-c+1){m \choose c} \left(x^{m-c+1}(s-x)^c-(s-x)^{m-c+1}x^c\right)$. Thus $x\mapsto f(x)$ is strictly decreasing (resp. increasing) on $[0,s/2]$ (resp. $[s/2,s]$), attaining its minimum at $x=s/2$. The rest is easy. End proof.

For any distribution $p=(p_1,\ldots,p_k)$ we have that $\mathbb{P}( \max X_i(n)\leq c-1)=1$ for $n\leq c-1$, and $\mathbb{P}( \max X_i(n)\leq c-1)=0$ for $n > k(c-1)$, so that only the cases $c\leq n \leq k(c-1)$ are of interest.

Corollary
For $c\leq n \leq k(c-1)$ the uniform distribution $p_1=\ldots=p_k=\tfrac{1}{k}$ uniquely maximises $\mathbb{P}(\max X_i(n) \leq c-1 )$.

Proof: Since we are maximising a continuous function (multivariate polynomial) on a compact set (simplex) the maximum is attained. Let $p$ be a maximising distribution. If some $p_i$ are $0$ we may replace $p$ by a distribution which has all $p_i$ positive ( by part (1) of the lemma). But then (by part 2 of the lemma) $p$ can only be maximising if $p$ is the uniform distribution. End proof.

Here is a proof using generating functions. Let $c\geq 2$ and $k\geq 2$ be fixed.

Let $X=(X_1(n),\ldots,X_k(n))$ be the $k$-tuple of occupancy numbers at time $n$, i.e. $X_i(n)$ = number of bins of type $i$ drawn at time $n$.
Clearly $X$ has the multinomial distribution with parameters $n$ and $p=(p_1,\ldots,p_k)$. Therefore
$$\mathbb{P}( \max X_i(n)\leq c-1)=n!\,[t^n] \prod _{i=1}^n q_c(p_it)$$

where $q_c(t):=\sum_{j=0}^{c-1}\frac{t^j}{j!}$ is the $c$th partial sum of $\exp(t)$.

The following lemma is the key.

Lemma
When $p_i,p_j$ are each replaced by their arithmetic mean $a:=(p_i+p_j)/2$
$\mathbb{P}(\max X_i(n) \leq c-1 )$ will not decrease.
If $c\leq n \leq k(c-1)$ and all other $p_\ell$ are positive $\mathbb{P}(\max X_i(n) \leq c-1 )$ will strictly increase if $p_i\not = p_j$. 

Proof Consider first the case of two factors. Let $x,y\in\mathbb{R}_+,x<y$. We show that $$ [t^m] q_c(xt)q_c(yt)\leq [t^m] \left(q_c(((x+y)/2)t\right)^2\;\;.$$It is easy to see that equality holds for $m\leq c-1$ and $m>2c-2$. Let $c\leq m \leq 2c-2$. We have $$m!\,[t^m] q_{c}(xt)q_c(yt)=(x+y)^m-\sum_{i=0}^{m-c} {m \choose i}\left(x^i y^{m-i}+y^i x^{m-i}\right) $$ For fixed sum $s=x+y$ the function $x \mapsto f(x):=\sum_{i=0}^{m-c} {m \choose i}\left(x^i y^{m-i}+y^i x^{m-i}\right)$ has the derivative $f^\prime(x)=(m-c+1){m \choose c} \left(x^{m-c+1}(s-x)^c-(s-x)^{m-c+1}x^c\right)$. Thus $x\mapsto f(x)$ is strictly decreasing (resp. increasing) on $[0,s/2]$ (resp. $[s/2,s]$), attaining its minimum at $x=s/2$. The rest is easy. End proof.

For any distribution $p=(p_1,\ldots,p_k)$ we have that $\mathbb{P}( \max X_i(n)\leq c-1)=1$ for $n\leq c-1$, and $\mathbb{P}( \max X_i(n)\leq c-1)=0$ for $n > k(c-1)$, so that only the cases $c\leq n \leq k(c-1)$ are of interest.

Corollary
For $c\leq n \leq k(c-1)$ the uniform distribution $p_1=\ldots=p_k=\tfrac{1}{k}$ uniquely maximises $\mathbb{P}(\max X_i(n) \leq c-1 )$.

Proof: Since we are maximising a continuous function (multivariate polynomial) on a compact set (simplex) the maximum is attained. Let $p$ be a maximising distribution. No $p_i$ can be $0$ (else replacing the last $0$ strictly increases the probability). But then $p$ can only be maximising if $p$ is the uniform distribution. End proof.

Remark Lemma 2 shows that the probability $\mathbb{P}(\max X_i(n) \leq c-1 )$ is a Schur-concave function on the simplex $p_i\geq 0, \sum_{i=1}^k p_i=1$. Possibly the result can be found under this heading in the literature (but a brief Google-search didn't reveal anything).

Source Link
esg
  • 3.3k
  • 11
  • 15

Here is a proof using generating functions. Let $c\geq 2$ and $k\geq 2$ be fixed.

Let $X=(X_1(n),\ldots,X_k(n))$ be the $k$-tuple of occupancy numbers at time $n$, i.e. $X_i(n)$ = number of bins of type $i$ drawn at time $n$.
Clearly $X$ has the multinomial distribution with parameters $n$ and $p=(p_1,\ldots,p_k)$. Therefore
$$\mathbb{P}( \max X_i(n)\leq c-1)=n!\,[t^n] \prod _{i=1}^n q_c(p_it)$$

where $q_c(t):=\sum_{j=0}^{c-1}\frac{t^j}{j!}$ is the $c$th partial sum of $\exp(t)$.

The following lemma is the key.

Lemma
When $p_i,p_j$ are each replaced by their arithmetic mean $a:=(p_i+p_j)/2$
(1) $\mathbb{P}(\max X_i(n) \leq c-1 )$ will not decrease
(2)If $c\leq n \leq k(c-1)$ and all $p_\ell$ are positive $\mathbb{P}(\max X_i(n) \leq c-1 )$ will strictly increase if $p_i\not = p_j$. Proof (1) Consider first the case of two factors. Let $x,y\in\mathbb{R}_+,x<y$. We show that $$ [t^m] q_c(xt)q_c(yt)\leq [t^m] \left(q_c(((x+y)/2)t\right)^2\;\;.$$It is easy to see that equality holds for $m\leq c-1$ and $m>2c-2$. Let $c\leq m \leq 2c-2$. We have $$m!\,[t^m] q_{c}(xt)q_c(yt)=(x+y)^m-\sum_{i=0}^{m-c} {m \choose i}\left(x^i y^{m-i}+y^i x^{m-i}\right) $$ For fixed sum $s=x+y$ the function $x \mapsto f(x):=\sum_{i=0}^{m-c} {m \choose i}\left(x^i y^{m-i}+y^i x^{m-i}\right)$ has the derivative $f^\prime(x)=(m-c+1){m \choose c} \left(x^{m-c+1}(s-x)^c-(s-x)^{m-c+1}x^c\right)$. Thus $x\mapsto f(x)$ is strictly decreasing (resp. increasing) on $[0,s/2]$ (resp. $[s/2,s]$), attaining its minimum at $x=s/2$. The rest is easy. End proof.

For any distribution $p=(p_1,\ldots,p_k)$ we have that $\mathbb{P}( \max X_i(n)\leq c-1)=1$ for $n\leq c-1$, and $\mathbb{P}( \max X_i(n)\leq c-1)=0$ for $n > k(c-1)$, so that only the cases $c\leq n \leq k(c-1)$ are of interest.

Corollary
For $c\leq n \leq k(c-1)$ the uniform distribution $p_1=\ldots=p_k=\tfrac{1}{k}$ uniquely maximises $\mathbb{P}(\max X_i(n) \leq c-1 )$.

Proof: Since we are maximising a continuous function (multivariate polynomial) on a compact set (simplex) the maximum is attained. Let $p$ be a maximising distribution. If some $p_i$ are $0$ we may replace $p$ by a distribution which has all $p_i$ positive ( by part (1) of the lemma). But then (by part 2 of the lemma) $p$ can only be maximising if $p$ is the uniform distribution. End proof.