1
$\begingroup$

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}$?

$\endgroup$
5
  • $\begingroup$ You cannot meaningfully say there are $N=\infty$ people and each has probability $\frac1{\infty}$ of getting their own hat back. $\endgroup$
    – Henry
    Jan 25 at 1:04
  • 1
    $\begingroup$ 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. $\endgroup$
    – Henry
    Jan 25 at 1:12
  • $\begingroup$ 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. $\endgroup$ Jan 25 at 1:25
  • 1
    $\begingroup$ Anyway, when $N$ is finite, the sum $$X_N = \sum_{k=1}^{N}\mathbb{I}[\text{$k$th 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. $\endgroup$ Jan 25 at 1:46
  • $\begingroup$ Thanks everyone...that was helpful... $\endgroup$
    – Kapes Mate
    Jan 25 at 8:56

1 Answer 1

1
$\begingroup$

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{$k$th 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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .