[Math] Expected number of people getting their own hat given that at least one of them gets his hat.

combinatoricsprobability

Suppose there are $N$ people at a party. Their hats get mixed and when leaving they grab a hat at random.

Let $\displaystyle X_i=I(\text{$i$th person gets his own hat})$ and $X=\displaystyle\sum_{i=1}^N X_i$.

It follows, from the linearity of expectation that the expected number of people who get their own hat is $1$.

I want to know how to compute $E(X\mid X\neq 0)$, without having to compute $P(X\neq 0)$. I guess I can't get an exact expression, but is it possible to get a non-trivial lower bound?

My method:

$$E(X\mid X\neq 0)= \sum_{i=1}^N P(X_i=1\mid X\neq 0).$$

To get a lower bound on $P(X_i=1\mid X\neq 0)$, I want to use the the fact that $P(X_i=1\mid X_j=1)=1/(n-1)$.

Is it true that $P(X_i=1\mid X\neq 0)>P(X_i=1\mid X_j=1)$ for $i\neq j$ ?

Best Answer

Let $E=1$ if $X>0$, $E=0$ elsewhere. We want $E(X \mid E=1)$

Then $1=E(X)= E[E[X\mid E]]=E(X \mid E=0)P(E=0)+E(X \mid E=1)P(E=1)$

But $E(X \mid E=0)=0$, hence $E(X\mid E=1)=1/P(E=1)$

Further, calling $!n$ the subfactorial or derangements count:

$$P(E=1)=1 - \frac{!n}{n!}\approx 1-\frac{1}{e}$$

So $E(X \mid E=1) \approx \frac{e}{e-1} = 1.5819767...$

If you want strict bounds: $ n!/e-1/2 \le \,!n\le n!/e+1/2$, hence

$$ \frac{e}{e-1+\frac{e}{2 \, n!}} \le E(X \mid E=1) \le \frac{e}{e-1-\frac{e}{2 \, n!}} $$