**"Real-life" motivation.** The German satirical magazine *Der Postillon* [suggested](https://www.der-postillon.com/2016/08/7-wege-rauchen.html) a few measures for deterring smokers from their bad habit. I especially liked the idea of inserting one "prank cigarette" per pack, giving the smoker a reminder in form of a (mild) explosion after lighting it. This motivated the following problem.


**Problem statement.** Suppose we are given $n$ empty packs of cigarettes, each to be filled with $n$ cigarettes. Amongst the $n^2$ cigarettes in total to be distributed to the $n$ empty packs, there are $n$ "prank cigarettes" to be distributed in a uniform manner into the $n$ packs.


**Questions.**


1. Let $M\_n$ be the expected value of the maximum number of prank cigarettes any pack receives. Is there an explicit formula for $M\_n$? If not, do we have $\lim\sup\_{n\to\infty}M\_n/n > 0$ or $\lim\sup\_{n\to\infty}M\_n/\log(n) > 0$?
2. Let $E\_n$ be the expected value of packs without any prank cigarettes. Is there an explicit formula for $E\_n$? If not, do we have $\lim\sup\_{n\to\infty}E\_n/n > 0$ or $\lim\sup\_{n\to\infty}E\_n/\log(n) > 0$?



Expected maximum number of "prank cigarettes" in an average pack
$\newcommand{\Si}{\Sigma}$Let $X\_n$ be the maximum number of prank cigarettes any pack receives, so that $M\_n=EX\_n$. Note that $X\_n=\max(N\_1,\dots,N\_n)$, where $(N\_1,\dots,N\_n)$ has the multinomial distribution with parameters $n;\frac1n,\dots,\frac1n$. So, by Theorem 1 or formula (6) of [Raab and Steger](https://link.springer.com/chapter/10.1007/3-540-49543-6_13),
\begin{equation\*}
 X\_n\sim r\_n:=\frac{\ln n}{\ln\ln n} \tag{1}\label{1}
\end{equation\*}
in probability (as $n\to\infty$).


We will also prove



> 
> **Proposition 1:**
> \begin{equation\*}
>  EX\_n^2\ll r\_n^2. 
> \end{equation\*}
> 
> 
> 


(As usual, we write $A\ll B$ to mean $A=O(B)$.)


By Proposition 1 and the [de la Vallée-Poussin theorem](https://en.wikipedia.org/wiki/Uniform_integrability#Relevant_theorems), $X\_n/r\_n$ is uniformly integrable, which implies



> 
> \begin{equation\*}
> M\_n=EX\_n\sim r\_n 
> \end{equation\*}
> 
> 
> 


(which agrees with Qiaochu Yuan's heuristics/conjecture).


*Proof of Proposition 1:*
Let $[n]:=\{1,\dots,n\}$. Note that
\begin{equation\*}
 EX\_n^2\ll\sum\_{m\in[n]}mP(X\_n\ge m)
=\Si\_1+\Si\_2, \tag{3}\label{3}
\end{equation\*}
where
\begin{equation\*}
 \Si\_1:=\sum\_{1\le m\le 4r\_n}mP(X\_n\ge m),\quad \Si\_2:=\sum\_{4r\_n<m\le n}mP(X\_n\ge m). 
\tag{4}\label{4}
\end{equation\*}
It is easy to bound $\Si\_1$:
\begin{equation}
 \Si\_1\le\sum\_{1\le m\le 4r\_n}m\ll r\_n^2. \tag{5}\label{5}
\end{equation}


Let us now bound $\Si\_2$.
Recall that $X\_n=\max(N\_1,\dots,N\_n)$, where $(N\_1,\dots,N\_n)$ has the multinomial distribution with parameters $n;\frac1n,\dots,\frac1n$. Note that for each $m\in[n]$
\begin{equation\*}
 P(X\_n\ge m)\le\sum\_{i\in[n]}P(N\_i\ge m)
 =nP(N\_1\ge m). \tag{7}\label{7}
\end{equation\*}
Next, $N\_1$ has the binomial distribution with parameters $n$ and $\frac1n$, and hence
\begin{equation\*}
\begin{aligned}
 P(N\_1\ge m)&=\sum\_{k=m}^n\binom nk\frac1{n^k}\Big(1-\frac1n\Big)^{n-k} \\ 
 &\le\sum\_{k=m}^n\binom nk\frac1{n^k}\le\sum\_{k=m}^n\frac1{k!}\ll\frac1{m!}. 
\end{aligned}
\tag{11}\label{11}
\end{equation\*}
Further, for $m>4r\_n$, eventually (that is, for all large enough $n$),
\begin{equation\*}
 m!\ge(m/e)^m=\exp(m\ln(m/e)) \\ 
 \ge\exp\Big(4\frac{\ln n}{\ln\ln n}\,\ln\frac{\ln n}{\ln\ln n}\Big)\ge n^3. \tag{13}\label{13}
\end{equation\*}
So, by \eqref{4}, \eqref{7}, \eqref{11}, and \eqref{13},  

\begin{equation\*}
 \Si\_2\le\sum\_{4r\_n<m\le n}mnP(N\_1\ge m) \\ 
 \ll\sum\_{4r\_n<m\le n}mn\frac1{n^3}\le1\ll r\_n^2. \tag{15}\label{15}
\end{equation\*}
Now Proposition 1 follows immediately from \eqref{3}, \eqref{5}, and \eqref{15}. $\quad\Box$




---


Quite similarly one can show that
\begin{equation\*}
EX\_n^p\sim r\_n^p 
\end{equation\*}
for each real $p>0$.


