Return to Answer

Equivalently, we are considering a random function $f : [n] \to [n]$ where $[n] = \{ 1, 2, \dots n \}$ is a finite set of size $n$, which assigns to each prank cigarette a pack. The second question is easier to answer so we'll answer it first. The probability that a given pack receives no prank cigarettes is $\left( 1 - \frac{1}{n} \right)^n = e^{-1} - O \left( \frac{1}{n} \right)$, so by linearity of expectation the expected number of packs with no prank cigarettes is

$$E_n = n \left( 1 - \frac{1}{n} \right)^n = e^{-1} n - O(1).$$

This gives

$$\lim_{n \to \infty} \frac{E_n}{n} = e^{-1}$$

and the other limit diverges.

The first question seems trickier but here is a heuristic calculation. The distribution of the size of any specific preimage $|f^{-1}(i)|$ (the number of prank cigarettes in a pack) is a binomial distribution $B(n, \frac{1}{n})$, which is asymptotically Poisson with parameter $\lambda = 1$ by the Poisson limit theorem. They are also asymptotically independent. So $M_n$ should approximately be distributed as the maximum of $n$ independent samples from the Poisson distribution $\text{Pois}(1)$. Some googling gives that this maximum ends up concentrated around $\frac{\log n}{W \left( \frac{\log n}{e} \right)}$, which funnily enough also occurs as an approximate inverse to the factorial; there's likely a relationship here. But I don't know if the Poisson approximation is tight enough that this is likely to be the real answer. This gives, heuristically,

$$\lim_{n \to \infty} \frac{M_n}{\frac{\log n}{\log \log n}} \stackrel{?}{=} 1$$

but quite slowly, so e.g. numerical calculations may not show this. The $W$ function estimate should be testable numerically, though.

Equivalently, we are considering a random function $f : [n] \to [n]$ where $[n] = \{ 1, 2, \dots n \}$ is a finite set of size $n$, which assigns to each prank cigarette a pack. The second question is easier to answer so we'll answer it first. The probability that a given pack receives no prank cigarettes is $\left( 1 - \frac{1}{n} \right)^n = e^{-1} - O \left( \frac{1}{n} \right)$, so by linearity of expectation the expected number of packs with no prank cigarettes is

$$E_n = n \left( 1 - \frac{1}{n} \right)^n = e^{-1} n - O(1).$$

This gives

$$\lim_{n \to \infty} \frac{E_n}{n} = e^{-1}$$

and the other limit diverges.

The first question seems trickier but here is a heuristic calculation. The distribution of the size of any specific preimage $|f^{-1}(i)|$ (the number of prank cigarettes in a pack) is a binomial distribution $B(n, \frac{1}{n})$, which is asymptotically Poisson with parameter $\lambda = 1$ by the Poisson limit theorem. They are also asymptotically independent. So $M_n$ should approximately be distributed as the maximum of $n$ independent samples from the Poisson distribution $\text{Pois}(1)$. Some googling gives that this maximum ends up concentrated around $\frac{\log n}{W \left( \frac{\log n}{e} \right)}$, which funnily enough also occurs as an approximate inverse to the factorial. But I don't know if the Poisson approximation is tight enough that this is likely to be the real answer. This gives, heuristically,

$$\lim_{n \to \infty} \frac{M_n}{\frac{\log n}{\log \log n}} \stackrel{?}{=} 1$$

but quite slowly, so e.g. numerical calculations may not show this. The $W$ function estimate should be testable numerically, though.

Equivalently, we are considering a random function $f : [n] \to [n]$ where $[n] = \{ 1, 2, \dots n \}$ is a finite set of size $n$, which assigns to each prank cigarette a pack. The second question is easier to answer so we'll answer it first. The probability that a given pack receives no prank cigarettes is $\left( 1 - \frac{1}{n} \right)^n = e^{-1} - O \left( \frac{1}{n} \right)$, so by linearity of expectation the expected number of packs with no prank cigarettes is $e^{-1} n - O(1)$; equivalently, the expected size of $\text{im}(f)$ is $(1 - e^{-1}) n + O(1)$. So

$$\lim_{n \to \infty} \frac{E_n}{n} = e^{-1}$$

and the other limit diverges.

The first question seems trickier but here is a heuristic calculation. The distribution of the size of any specific preimage $|f^{-1}(i)|$ (the number of prank cigarettes in a pack) is a binomial distribution $B(n, \frac{1}{n})$, which is asymptotically Poisson with parameter $\lambda = 1$ by the Poisson limit theorem. They are also asymptotically independent. So $M_n$ should approximately be distributed as the maximum of $n$ independent samples from the Poisson distribution $\text{Pois}(1)$. Some googling gives that this maximum ends up concentrated around $\frac{\log n}{W \left( \frac{\log n}{e} \right)}$, which funnily enough also occurs as an approximate inverse to the factorial; there's likely a relationship here. But I don't know if the Poisson approximation is tight enough that this is likely to be the real answer. This gives, heuristically,

$$\lim_{n \to \infty} \frac{M_n}{\frac{\log n}{\log \log n}} = 1$$

but quite slowly, so e.g. numerical calculations may not show this. The $W$ function estimate should be testable numerically, though.

Equivalently, we are considering a random function $f : [n] \to [n]$ where $[n] = \{ 1, 2, \dots n \}$ is a finite set of size $n$, which assigns to each prank cigarette a pack. The second question is easier to answer so we'll answer it first. The probability that a given pack receives no prank cigarettes is $\left( 1 - \frac{1}{n} \right)^n = e^{-1} - O \left( \frac{1}{n} \right)$, so by linearity of expectation the expected number of packs with no prank cigarettes is

$$E_n = n \left( 1 - \frac{1}{n} \right)^n = e^{-1} n - O(1).$$

This gives

$$\lim_{n \to \infty} \frac{E_n}{n} = e^{-1}$$

and the other limit diverges.

The first question seems trickier but here is a heuristic calculation. The distribution of the size of any specific preimage $|f^{-1}(i)|$ (the number of prank cigarettes in a pack) is a binomial distribution $B(n, \frac{1}{n})$, which is asymptotically Poisson with parameter $\lambda = 1$ by the Poisson limit theorem. They are also asymptotically independent. So $M_n$ should approximately be distributed as the maximum of $n$ independent samples from the Poisson distribution $\text{Pois}(1)$. Some googling gives that this maximum ends up concentrated around $\frac{\log n}{W \left( \frac{\log n}{e} \right)}$, which funnily enough also occurs as an approximate inverse to the factorial; there's likely a relationship here. But I don't know if the Poisson approximation is tight enough that this is likely to be the real answer. This gives, heuristically,

$$\lim_{n \to \infty} \frac{M_n}{\frac{\log n}{\log \log n}} \stackrel{?}{=} 1$$

but quite slowly, so e.g. numerical calculations may not show this. The $W$ function estimate should be testable numerically, though.

Equivalently, we are considering a random function $f : [n] \to [n]$ where $[n] = \{ 1, 2, \dots n \}$ is a finite set of size $n$, which assigns to each prank cigarette a pack. The second question is easier to answer so we'll answer it first. The probability that a given pack receives no prank cigarettes is $\left( 1 - \frac{1}{n} \right)^n = e^{-1} - O \left( \frac{1}{n} \right)$, so by linearity of expectation the expected number of packs with no prank cigarettes is $e^{-1} n - O(1)$; equivalently, the expected size of $\text{im}(f)$ is $(1 - e^{-1}) n + O(1)$.

The second question seems trickier but here is a heuristic calculation. The distribution of the size of any specific preimage $|f^{-1}(i)|$ (the number of prank cigarettes in a pack) is a binomial distribution $B(n, \frac{1}{n})$, which is asymptotically Poisson with parameter $\lambda = 1$ by the Poisson limit theorem. They are also asymptotically independent. So $M_n$ should approximately be distributed as the maximum of $n$ independent samples from the Poisson distribution $\text{Pois}(1)$. Some googling gives that this maximum ends up concentrated around $\frac{\log n}{W \left( \frac{\log n}{e} \right)}$, which funnily enough also occurs as an approximate inverse to the factorial; there's likely a relationship here. But I don't know if the Poisson approximation is tight enough that this is likely to be the real answer.

Equivalently, we are considering a random function $f : [n] \to [n]$ where $[n] = \{ 1, 2, \dots n \}$ is a finite set of size $n$, which assigns to each prank cigarette a pack. The second question is easier to answer so we'll answer it first. The probability that a given pack receives no prank cigarettes is $\left( 1 - \frac{1}{n} \right)^n = e^{-1} - O \left( \frac{1}{n} \right)$, so by linearity of expectation the expected number of packs with no prank cigarettes is $e^{-1} n - O(1)$; equivalently, the expected size of $\text{im}(f)$ is $(1 - e^{-1}) n + O(1)$. So

$$\lim_{n \to \infty} \frac{E_n}{n} = e^{-1}$$

and the other limit diverges.

The first question seems trickier but here is a heuristic calculation. The distribution of the size of any specific preimage $|f^{-1}(i)|$ (the number of prank cigarettes in a pack) is a binomial distribution $B(n, \frac{1}{n})$, which is asymptotically Poisson with parameter $\lambda = 1$ by the Poisson limit theorem. They are also asymptotically independent. So $M_n$ should approximately be distributed as the maximum of $n$ independent samples from the Poisson distribution $\text{Pois}(1)$. Some googling gives that this maximum ends up concentrated around $\frac{\log n}{W \left( \frac{\log n}{e} \right)}$, which funnily enough also occurs as an approximate inverse to the factorial; there's likely a relationship here. But I don't know if the Poisson approximation is tight enough that this is likely to be the real answer. This gives, heuristically,

$$\lim_{n \to \infty} \frac{M_n}{\frac{\log n}{\log \log n}} = 1$$

but quite slowly, so e.g. numerical calculations may not show this. The $W$ function estimate should be testable numerically, though.