Light bulbs randomly chosen

Question

In a room there are N light bulbs, initially they are all switched off. For N times, I do the following: I randomly choose one bulb and switch it on if it is off or switch it off if is on.

What is the probability that after my N actions all light bulbs are off?

The answer is 0 if N is odd. However when N is even I get a bit lost in the computations. I tried a brute force combinatorics approach but I failed. Then I thought of a random walk where each state is the number of light bulbs switched on. This provides me with an algorithm to compute the probability but I cannot find a closed form

Answer 1

The number of sequences of switches is $N^N$.

The number of sequences leaving all the lights off is tabulated at http://oeis.org/A209289 (Number of functions $f:\{\,1,2,\dots,2n\,\}\to\{\,1,2,\dots,2n\,\}$ such that every preimage has an even cardinality). Here $N=2n$. The formula $$a(n) = \sum_{i=0}^{2n} (n-i)^{2n}{\binom {2n}i}$$ and the estimate $$a(n) \sim {c n^{2n} 2^{2n} (1-r)^{2n} \over (2-r)^n r^n e^{2n}}$$ are given, where $r = 0.1664434403990353015638385297757806508596082\dots$ is the root of the equation $((2/r)-1)^{1-r} = e^2$, and $c = 1.66711311920192939687232294044843869828\dots$.

$N^N=(2n)^{2n}=2^{2n}n^{2n}$, so the probability is asymptotic to $${c (1-r)^{2n} \over (2-r)^n r^n e^{2n}}=c\alpha^n$$ where $\alpha=(1-r)^2/((2-r)re^2)$.

Answer 2

Let $P(\ell,f)$ be the probability that $\ell$ bulbs are lit after $f$ flips. We want to find $p_N=P(0,N)$, where $N$ is the number of bulbs.

Note that $P(0,0)=1$, and if we let $P(-1,f)=P(N+1,f)=0$, we can find $P$ recursively*:

$$P(\ell,f)={N-\ell+1\over N}P(\ell-1,f-1)+{\ell+1\over N}P(\ell+1,f-1).$$

Mathematica calculations yield these results:

$\displaystyle p_2={1\over2}={2\over2^2}$,

$\displaystyle p_4={5\over32}={40\over4^4}$,

$\displaystyle p_6={47\over972}={2256\over6^6}$,

$\displaystyle p_8={1957\over131072}={250496\over8^8}$,

$\displaystyle p_{10}={35987\over7812500}={46063360\over10^{10}}$.

The sequence of numerators, $2, 40, 2256, 250496, 46063360, \dots$, is http://oeis.org/A209289, which as Gerry notes in his answer, counts the number of ways to flip the switches so ever switch if flipped an even number of times. And the sequence of denominators is the number of ways to flip switches $2N$ times if there are $2N$ switches in all.

*The two ways that $\ell$ bulbs can be lit after $f$ flips are:

• $\ell-1$ were lit after $f-1$ flips and we chose one of the $N-(\ell-1)$ unlit bulbs to switch.

• $\ell+1$ were lit after $f-1$ flips and we chose one of those $\ell+1$ to switch.