We have a string (sequence) of 0s and 1s, and at each step we randomly change a 0 to 1 or a 1 to 0. On average, how many steps do we need to make to get back the original string? How does this depend on the length of string?
For example:
01000101010110
I think the possible states can be modelled as a graph and the steps as some random walk along it. The number of vertices will be $2^n$ where n is the length of the string.
The theory of finite-state discrete-time time-homogenous Markov chains tells us that if we run the game for much more than $2^{n}$ steps, the probabilities to be in each state will converge towards a unique steady distribution. (This is not exactly true, but it would be true if in each step there was some probability, however small, of staying in the same state instead of flipping a bit -- if we want to be rigorous we can let this probability go to 0 at the end of the analysis). By symmetry this steady distribution must have a probability of $2^{-n}$ for each possible string.
So after $M\ggg 2^n$ steps we expect to have been in any given state $M/2^n$ times. (and the law of large numbers tells us that the fraction $1/2^n$ will become more and more precise with probability $1$).
This is especially true for the starting state, which means that at large $M$ we have been in the starting state $M/2^n$ times during $M$ steps -- which means that the average time that has passed between visits to the starting state is $2^n$.
But the process has no memory, so this long-term average will also be the expected time to the first return after we've started the game.