Intereting Posts

Decomposition of a manifold
Change of Variables in Limits
Comparison Statement
How to find the vector equation of a plane given the scalar equation?
Prove that if the sum of each row of $A$ equals $s$, then $s$ is an eigenvalue of $A$.
Finding cubic function from points?
Prove $\ker {T^k} \cap {\mathop{\rm Im}\nolimits} {T^k} = \{ 0\}$
Color the edges of $K_6$ red or blue. Prove that there is a cycle of length 4 with monochromatic edges.
Series for envelope of triangle area bisectors
Quotient objects, their universal property and the isomorphism theorems
Low-dimensional Irreducible Representations of $S_n$
I am going to learn these math topics , please suggest me where to start?
Determine all primes $p$ for which $5$ is a quadratic residue modulo $p$
Is half-filled magic square problem NP-complete?
Integral $\int_1^\infty\frac{dx}{1+2^x+3^x}$

If I place $k$ balls in $n$ cells randomly with uniform probability, then for large enough $n$ and $k/n$ small enough, I expect about $n e^{-k/n}$ cells to be empty (using the Poisson approximation to the Binomial.) However, I cannot find the limit of the variance of the number of empty cells?

One can compute explicit cases by using the probability that exactly $m$ cells are empty,

$$var = \sum_{m=0}^nm^2\binom{n}{m}\sum_{\nu=0}^{n-m}(-1)^\nu\binom{n-m}{\nu}\left(1-\frac{m+\nu}{n}\right)^k – \left(1 – \frac{1}{n}\right)^{2k}$$

but I cannot find the limit of this.

- When Jensen's inequality is equality
- Largest Part of a Random Weak Composition
- Show that $\lim\limits_{y\downarrow 0} y\mathbb{E}=0$.
- Probability of two integers' square sum divisible by $10$
- What is the problem in this solution to the Two Child Problem?
- Probability of random walk returning to 0

The same question can be asked of singletons, doubletons, etc.

- Does $P(A\cap B) + P(A\cap B^c) = P(A)$?
- How to approach number guessing game(with a twist) algorithm?
- Inequality involving taking expectations
- combining conditional probabilities
- Find $E(XY)$ assuming no independence with $E(X) = 4$, $E(Y) = 10$, $V(X) = 5$, $V(Y) = 3$, $V(X+Y) = 6$.
- Is Scrabble's method of determining turn order fair?
- Multiple Conditioning on Event Probabilities
- Analogue of the Schwartz–Zippel lemma for subspaces
- Density/probability function of discrete and continuous random variables
- {Thinking}: Why equivalent percentage increase of A and decrease of B is not the same end result?

We use the method of *indicator functions*, which is often useful for this kind of problem. Let $X_i=1$ if the $i$-th cell is empty, and $0$ otherwise. Let

$$Y=\sum_{i=1}^n X_i.$$

Then $Y$ is the number of empty cells. We want the variance of $Y$. This is equal to

$$E(Y^2)-(E(Y))^2.$$

It is easy to find $E(Y)$, since we can find $P(X_i=1)$, and then use the linearity of expectation.

Now we want $E(Y^2)$. To find it, expand $Y^2$, that is, $(X_1+\cdots +X_n)^2$. We get

$$\sum_{i=1}^n X_i^2 + 2\sum_{1\le i<j\le n} X_iX_j.$$

Finding the expectation of $\sum X_i^2$, is easy, indeed we have already found it, since $X_i^2=X_i$. It remains to find the expectation of $2\sum X_iX_j$.

There are $\binom{n}{2}$ terms in the sum. So we need to find the expectation of a typical mixed term $X_iX_j$, and multiply by $2\binom{n}{2}$.

To find $E(X_iX_j)$, all we need to do is to find the probability that cells $i$ and $j$ are both empty. That is not hard to do.

**Comment:** The technique used bypasses the difficult problem of finding the probability distribution of $Y$, then getting an *expression* for the variance, and then somehow simplifying this expression so that we can actually use it for further work.

Note that our random variables $X_i$ are *not independent*. However, that need not be an impediment. The expectation $E(X_iX_j)$ is, in our problem, somewhat harder to calculate than if we had independence, but it is not *much* harder.

The technique will also work for the problems involving singletons, doubletons, etc., proposed in the post.

Let $Y$ be the number of empty cells. We can write $Y = \sum_{i=1}^n Y_i$ where $Y_i$ is $1$ if cell number $i$ is empty, $0$ otherwise.

$E(Y_j)$ is the probability that cell number $j$ is empty, namely $(1 – 1/n)^k$, so $E(Y) = n (1 – 1/n)^k$.

For two distinct cells $j_1$ and $j_2$, $E(Y_{j_1} Y_{j_2}$ is the probability that both are empty, namely

$(1 – 2/n)^k$. There are $n(n-1)$ such ordered pairs. On the other hand

$E(Y_j^2) = E(Y_j) = (1 – 1/n)^k$, and there are $n$ of these. So

$E(Y^2) = n(n-1) (1 – 2/n)^k + n (1 – 1/n)^k$, and

$$\text{Var}(Y) = E(Y^2) – E(Y)^2 = n(n-1)(1 – 2/n)^k + n (1 – 1/n)^k – n^2 (1 – 1/n)^{2k}$$

As $n \to \infty$ with $k = \lambda n$, $(1 – 1/n)^k \approx (1 – \frac{\lambda}{2n}) e^{-\lambda} $,

$(1 – 1/n)^{2k} \approx (1 – \frac{\lambda}{n}) e^{-2\lambda}$

and $(1 – 2/n)^k \approx (1 – 2 \lambda/n) e^{-2 \lambda}$. The end result is $\text{Var}(Y) \approx n (e^{-\lambda} – (1+\lambda) e^{-2\lambda})$.

- How exactly can't $\delta$ depend on $x$ in the definition of uniform continuity?
- Does the fibres being equal dimensional imply flatness?
- Will $2$ linear equations with $2$ unknowns always have a solution?
- Brownian motion martingale
- Expected value of maximum of two random variables from uniform distribution
- Building a 3D matrix of positive integers
- Tensor products of fields
- Showing there exists infinite $n$ such that $n! + 1$ is divisible by atleast two distinct primes
- How to write \mathcal letters by hand?
- Dirac Delta Function of a Function
- Convergence of series implies convergence of Cesaro Mean.
- Evaluate $ \sum_{n=1}^{\infty} \frac{\sin \ n}{ n } $ using the fourier series
- Is there a function such that $f(f(n)) = 2^n$?
- Books about the Riemann Hypothesis
- Does any uncountable set contain two disjoint uncountable sets?