This problem has been bugging me for a bit, can't find a way to make progress.
I have $n$ lights in a row, all initially turned off, and I would like some specific $k$ positions to be turned on. Without loss of generality, let us say that I would like the first $k$ of them to be turned on.
If I switch the lights from on to off (or vice versa) randomly, what is the expected number of switches it will take to reach my desired configuration?
If I turn one of the first $k$ lights off (after it's already been turned on), I am required to need at least $1$ extra switch to get it to the correct configuration. Same goes for turning the last $n-k$ lights on; they require another switch to turn them off.
Not sure how to tackle this problem. At first I wrote something like:
$$E(x) = \frac{k}{n}(E(x) - 1) + \frac{n-k}{n}(E(x) + 1)$$
Obviously this is wrong, but the idea was on the first turn, if you turn one of the first $k$ lights on you've made one "switch" worth of progress toward your goal, but if you turn one of the last $n-k$ lights on, you're required to at least make one more switch to eventually win. I've used this sort of technique for these sort of "recurrence"-esque probability problems, so I'm wondering if I can extend that to this problem.
The other thing I considered was using Markov chains, but I'm also not sure how to set up the state transition matrix. My guess is there's $k(n-k)$ states since we only care about the number of "on" lights in the first $k$ and the number of "on" lights in the last $n-k$.
Is there an easier way to tackle this problem?
Actually, you only care about the number of lights that are currently in the desired state. So you start out in the state $n-k$, and you want to reach the state $n$. The recurrence is
$$ E_j=1+\frac jnE_{j-1}+\frac{n-j}nE_{j+1}\;. $$
The initial values are $E_n=0$ and $E_{n-1}=2^n-1$ (where the latter is due to the fact that starting from $E_n$ the expected return time is the number of states, $2^n$). I don't see how to derive a closed form, but for given values of $k$ and $n$ you can use the recurrence and the initial values to derive the desired $E_{n-k}$.