11
$\begingroup$

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

$\endgroup$
  • $\begingroup$ When $n$ goes to $\infty$, the binomial distribution approaches a normal distribution. $\endgroup$ – PSPACEhard Nov 13 '17 at 11:48
  • $\begingroup$ 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$. $\endgroup$ – Dean Nov 19 '17 at 22:40
4
+50
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This only works if $p = 1/2$; you still have to prove it for other $p$. $\endgroup$ – Mees de Vries Nov 19 '17 at 15:51
  • $\begingroup$ @MeesdeVries That's right; my original formulation might not have been clear enough. $\endgroup$ – pi66 Nov 20 '17 at 11:15
  • $\begingroup$ @pi66: ok, I've changed the argument to allow a different probability of being on and off $\endgroup$ – Dap Nov 20 '17 at 13:40
  • $\begingroup$ 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$. $\endgroup$ – Mees de Vries Nov 20 '17 at 13:43
  • 1
    $\begingroup$ @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$. $\endgroup$ – Kevin P. Costello Nov 22 '17 at 21:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.