# Limit of lights in rooms

There are $k$ rooms with $n$ lights each. Each light is on with equal probability $p$ independently of other lights. As $k$ stays fixed and $n$ goes to infinity, what is the limit of the probability that Room 1 has the maximum number of lights on (possibly sharing this maximum with other rooms)?

By symmetry, this probability is clearly at least $1/k$ for any $n$. However, for fixed $n$ it is slightly larger than $1/k$ because the maximum can be equal for many rooms. Still I think the limit should be $1/k$.

• When $n$ goes to $\infty$, the binomial distribution approaches a normal distribution. – PSPACEhard Nov 13 '17 at 11:48
• If the on-probability $p$ is fixed and non-zero, as $n$ is taken to infinity, the number of on-lights in all rooms tends to infinity, so does one have to be careful about comparing the number of on-lights in each room? Perhaps you are asking the probability that room-1 has the largest fraction of on-lights? As $n\rightarrow\infty$ the fraction of on-lights, F, goes from a discrete to a continuous RV, so that $p(F_i=F_1)\rightarrow0$ for $i \neq 1$. – Dean Nov 19 '17 at 22:40

It's $1/k,$ because the probability of having a unique maximum tends to $1.$
For a fixed pair of rooms, with number of lights on $X_1$ and $X_2,$ let $p_n$ denote the probability $\mathbb P[X_1=X_2]$ of having an equal number of lights on. Note $X_1-X_2$ is a sum of $n$ i.i.d. $\{-1,0,1\}$-valued variables, where the $j$'th variable is $1$ if the $j$'th lightbulb in room $1$ is on, minus $1$ if the $j$'th lightbulb in room $2$ is on (so $0$ if they are both on or both off). By the central limit theorem, the probability of $X_1-X_2=0$ tends to zero as $n\to\infty:$ for any fixed $\epsilon>0,$ there is some $c$ such that $p_n\leq \mathbb P[-c\sqrt n\leq X_1-X_2\leq c\sqrt n]\leq\epsilon/2$ for sufficiently large $n.$
By a union bound, the probability of any pair of rooms having the same number of lights is at most $\binom k 2 p_n,$ which for any fixed $k$ will tend to zero as $n\to\infty.$
• This only works if $p = 1/2$; you still have to prove it for other $p$. – Mees de Vries Nov 19 '17 at 15:51
• I'm curious why the heavy machinery of the CLT seems necessary. I feel like a simple combinatorial argument, certainly no heavier than Stirling's approximation, should be enough to prove that for $X_n, Y_n \sim \mathrm{Binom}(n, p)$ we have $\lim_{n \to \infty} \mathbb P(X_n = Y_n) = 0$. – Mees de Vries Nov 20 '17 at 13:43
• @Mees de Vires If you don't want to appeal to CLT (or even Stirling): We have $P(X_n=Y_n) \leq \max_{c} P(X_n=c)$. Direct calculation gives $$\frac{P(X_n=c+1)}{P(X_n=c)}=\frac{p}{1-p} \frac{n-c}{c+1}.$$ This tells us two things. (1) The maximum occurs for $c=np$ (possibly rounded up, possibly rounded down), since this is where the ratio crosses $1$. (2) For $c$ close to $np$, the ratio is $1+o(1)$, meaning $P(X_n=c)$ is approximately constant over an interval of length tending to infinity. This means the probability of any point in that interval goes to $0$. – Kevin P. Costello Nov 22 '17 at 21:07