Intereting Posts

How prove $e^x|f(x)|\le 2$ if $f(x)=\int_{x}^{x+1}\sin{(e^t)}dt$
Strong Markov property of Bessel processes
Probability of Drawing a Card from a Deck
A nicer proof of Lagrange's 'best approximations' law?
Proof of Inequality using AM-GM
Solution to the stochastic differential equation
How does the Herglotz trick work?
Do probability measures have to be the same if they agree on a generator of Borel $\sigma$–algebra $\mathcal{B}(\mathbb{R})$?
Generate random numbers following the exponential distribution in a given interval $$
Counting all possible legal board states in Quoridor
Generalized Eisenstein's Criterion over Integral Domains?
Does the nine point circle generalise to some theorem about n-spheres and n-simplices?
Is there something similar for division as this Japanese multiplication method?
Prove that the Pontryagin dual of $\mathbb{R}$ is $\mathbb{R}$.
Differentiate a recurrence relation

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.

- Probability of Random number repeating
- Traditional combination problem with married couples buying seats to a concert.
- 3 balls drawn from 1 urn - probability all same color (with/without replacement)
- Is the Law of Large Numbers empirically proven?
- Proof that the hypergeometric distribution with large $N$ approaches the binomial distribution.
- If $\mathbb E=0$ for all $G\in \mathcal G$, does $X=0$?

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

- Consecutive coupon collection
- $E(X_1 | X_1 + X_2)$ for independent gamma random variables
- Why is that the events (Sum of dice roll=6, first die=4) are dependent, but the events (Sum of dice roll=7, first die =4) are independent?
- What is the probability of this exact same Champions League draw?
- Cramér's Model - “The Prime Numbers and Their Distribution” - Part 1
- Does exceptionalism persist as sample size gets large?
- a generalization of normal distribution to the complex case: complex integral over the real line
- Probability that no car is parked next to a car of the same type
- In Lotto what is the minimum number of tickets you would need to buy to guarantee at least one 3 number match?
- Why is there this strange contradiction between the language of logic and that of set theory?

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})$.

- Log integrals I
- Possible areas for convex regions partitioning a plane and containing each a vertex of a square lattice.
- Compute $\sum_{k=1}^{\infty}e^{-\pi k^2}\left(\pi k^2-\frac{1}{4}\right)$
- continuous linear functional on a reflexive Banach space attains its norm
- prove that line bisect section
- $\mathcal{K}(L^2(\mathbb{R}^m \times \mathbb{R}^n)) = \mathcal{K}(L^2(\mathbb{R}^m)) \otimes \mathcal{K}(L^2(\mathbb{R}^n))$?
- Learning Fibre Bundle from “Topology and Geometry” by Bredon
- Example of topological spaces where sequential continuity does not imply continuity
- Colliding Bullets
- How to use triangle inequality to establish Reverse triangle inequality
- Uniqueness of meets and joins in posets
- How does the determinant change with respect to a base change?
- Why we use the word 'compact' for compact spaces?
- Counting invariant subspaces of a Vector space
- Let $(f_n)$ be a sequence of continuous functions from the reals to the reals. And let $\sup{|f_n(x)-f_m(x)|} \leq \frac1{\min(m,n)}$