# Infinite sum of correlated Bernoulli variables

Question:

Is there any chance that the infinite sum of correlated Bernoulli variables is Poisson distributed?

Motivation of the question:

I've read a well known derangement problem known as hat check problem (see e.g.: Question on the 'Hat check' problem). Let me cite the problem from the previous attached page, but modify the question a little bit...

$$N$$ men enter the restaurant and put their hats at the reception. Each man gets a random hat back when going back after having dinner, what is the probability that at least one person gets his own hat back, if there are $$N=\infty$$ guests in the restaurant.

To solve this let me use the following notations:

$$\mathbf{P}\left( \begin{array}{c} \text{At least one person gets} \\ \text{his own hat back} \end{array} \right) = \mathbf{P}\left(A_{1} \cup A_{2} \cup \cdots \cup A_{k} \cup \cdots \right),$$

where $$A_{k}$$ denotes the event when the $$k$$th person gets his own hat back. Using Poincaré's formula, for $$N$$ people it is not hard to verify

\begin{align*} \mathbf{P}\left(A_{1} \cup A_{2} \cup \cdots \cup A_{N}\right) &= \sum_{k=1}^{N} (-1)^{k-1} \binom{N}{k} \frac{1}{n\cdot\left(n-1\right)\cdots\left(n-k+1\right)} \\ &= \sum_{k=1}^{N} \frac{(-1)^{k-1}}{k!} \end{align*}

Taking the limit we get the final result

$$\lim_{N\to\infty} \sum_{k=1}^{N} \frac{(-1)^{k-1}}{k!} = 1 - \sum_{k=0}^{\infty} \frac{(-1)^{k}}{k!} = 1 - e^{-1}.$$

However, I see the chance that it can be solved otherwise...

Let $$\chi_{k}=1$$ if the $$k$$th person gets his own hat back, and $$\chi_{k}=0$$ otherwise. It is a Bernoulli variable. We can calculate the $$p_{k}=p$$ common parameter for all $$\chi_{k}$$ if there are $$N$$ people, with the help of the hypergeometric distribution: there are $$M=1$$ correct hat for one person among the $$N$$ hats, therefore the chance he gets his own hat back is $$p=\frac{\binom{1}{1}\binom{N-1}{0}}{\binom{N}{1}}=\frac{1}{N}$$.

However the asked probability for $$N=\infty$$ men is

$$1 - \mathbf{P}\left(\forall k:\chi_{k}=0\right),$$

where $$\left(\forall k:\chi_{k}=0\right)$$ is exactly the same event as $$\left(\sum_{k=1}^{\infty}\chi_{k}=0\right)$$, since $$\chi_{k}$$ can have two values: $$0$$ or $$1$$.

I know $$\chi_{k}$$'s are not independent, since if someone gets a wrong hat, i.e. $$\chi_{k}=0$$ for a given $$k$$, then there will be at least one other $$\chi_{j}$$ $$j\neq k$$ which will be $$0$$, since the $$j$$th person's hat have been taken by the $$k$$th person.

In this point I have a conejcture, that $$\sum_{k=1}^{\infty}\chi_{k}$$ is Poisson distributed with $$\lambda=\lim_{N\rightarrow\infty}N\frac{1}{N}=1$$, since above we got $$1-e^{-1}$$ where $$e^{-1}$$ could be $$\mathbf{P}\left(X=0\right)$$, $$X\sim \text{Poi}(1)$$. I can't prove it and I'm not even sure if it is true or just a simple coincidence...

I tried to prove it with Proof that the hypergeometric distribution with large $N$ approaches the binomial distribution., but here the $$p$$ value can't be fixed. $$p_N$$ is approaches to zero as $$N\rightarrow\infty$$. But if I could solve that the hypergeoemtric distribution here can be approxiamted with binomials, then we could use the following: https://en.wikipedia.org/wiki/Poisson_limit_theorem. This is my idea.

I tried to use Approximating hypergeometric distribution with poisson, but I'm not 100% certain what is hypergeometric distributed here.

In short: What is the distribution of $$\sum_{k=1}^{\infty}\chi_{k}$$?

• You cannot meaningfully say there are $N=\infty$ people and each has probability $\frac1{\infty}$ of getting their own hat back. Jan 25 at 1:04
• But you can say that as finite $N$ increases, the distribution of the number of people getting their own hats back converges to a Poisson distribution with mean $1$. The probability of this being $k$ converges to $\frac{e^{-1}}{k!}$ as $N$ increases, e.g. to $e^{-1}$ when $k=0$ or when $k=1$. This is related to rencontres numbers. Jan 25 at 1:12
• Any $\mathbb{Z}^{\geq0}$-valued RV $X$ can be written as a sum of Bernoulli RVs: $$X = \sum_{n=1}^{\infty}\mathbf{1}_{\{X \leq n\}}.$$ So, if $X$ already has a Poisson distribution, then it can be written as a sum of (correlated) Bernoulli RVs. Jan 25 at 1:25
• Anyway, when $N$ is finite, the sum $$X_N = \sum_{k=1}^{N}\mathbb{I}[\text{kth person gets his own hat}]$$ is not a Poisson random variable. However, $X_N$ converges in distribution to a Poisson variable as $N \to \infty$. In this case, it essentially means that $$\lim_{N\to\infty} \mathbf{P}(X_N = k) = \mathbf{P}_{X\sim\text{Poi}(1)}(X = k),$$ where $\mathbf{P}_{X\sim\text{Poi}(1)}$ means that the random variable $X$ has $\text{Poi}(1)$ distribution under this law. Jan 25 at 1:46
• Thanks everyone...that was helpful... Jan 25 at 8:56

Although the sum is never a Poisson variable for finite $$N$$, the sum converges in distribution to a Poisson variable as $$N \to \infty$$. To show this, let

$$S_N = \sum_{k=1}^{N} \mathbf{1}_{A_k}, \qquad A_k = \{ \text{kth person gets his own hat} \},$$

denote the sum for each finite $$N$$. Then by decomposing the event $$\{S_N = k\}$$ according to the value of the set $$I$$ of people who get their own hats,

\begin{align*} \mathbf{P}(S_N = k) &= \sum_{|I| = k} \mathbf{P}\bigl( \cap_{i \in I} A_i \bigr) \mathbf{P} \bigl( \cap_{j \notin I} A_j^c \mid \cap_{i \in I} A_i \bigr) \\ &= \binom{N}{k}\frac{1}{N(N-1)\cdots(N-k+1)}\mathbf{P}(S_{N-k} = 0) \\ &= \frac{1}{k!} \mathbf{P}(S_{N-k} = 0). \end{align*}

So by letting $$N \to \infty$$,

$$\lim_{N \to \infty} \mathbf{P}(S_N = k) = \frac{1}{k!}e^{-1},$$

which is precisely the PMF of $$\text{Poi}(1)$$ distribution.