Suppose you have a row of $n$ switches with two states each, on ($1$) or off ($0$), as well as a coin that shows heads with probability $p$ and tails with prob. $q=1-p$. Initially, all switches are off. You flip the coin, and if you see tails, you randomly toggle one of the switches (when it's on, you turn it off, and vice versa) and then flip the coin again. If you see heads, you stop and count the number of switches that are on. Q: What probability distribution does this number $K$ of activated switches follow?
I found this is a very easy to simulate but tricky to formalize probability distribution. My thoughts and insights so far: $K$ obviously has support in $\lbrace 0,\dots,n\rbrace$. The number of total flips $M$ follows a geometric distribution with parameter $p$. The probability of switch $i$ being toggled $a_i$ times is the probability of drawing $i$ exactly $a_i$ times out of a uniform distribution over $\lbrace 1,\dots,n\rbrace$ in $M$ tries, so $$P(a_i)=\sum_{m=0}^\infty P(M=m)\cdot{m\choose a_i}\left({1\over n}\right)^{a_i}\left({n-1\over n}\right)^{m-a_i}$$ with $P(M=m)=q^{m}\cdot p$. Now the probability for $K=k$ is the probability that among all $(a_i)_{i\in [n]}$ exactly $k$ are odd. This is where I don't know how to continue, I haven't been able to come up with a closed form solution to this problem.
Some insights:
- For $p\searrow 0$, $P(K=k)$ approaches a
uniformbinomial distribution over $\lbrace 0,\dots,n\rbrace$ (EDIT: Thanks to Henry for the correction) - For large $n\gg \mathbb{E}[M]={1\over q}$, the probability $P(a_i)=1$ approaches $q$, which is by design, i.e. the process simulates flipping all switches independently with probability $q$.
My questions:
- Do you, by any chance, recognize this as a known distribution?
- Do you have an idea for how to find a closed form expression for $P(K=k)$, if it exists at all?
Thanks in advance, best regards! - smuecke