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
Best Answer
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)$.