Find the expected number of '01's in a string

Question

This is an interview question:

For strings of length m + n, with m 0's and n 1's. Find the expected number of switches from 0 to 1 (a switch can be thought of as presence of '01' in the given string).

I have tried solving it as follows:

Let Xi denote a random variable such that a '01' pattern occurs in the string for a particular '0'. Then

W = X1 + X2 + ............. + Xm

and we have to find E[W]. Now

E[W] = E[X1] + E[X2] + E[X3] + ............... + E[Xm]

Now E[X1] is same as finding expectation such that 0 comes before any 1. It should be n/n+1. This holds for all Xi's. Therefore E[W] = mn/n+1. And this is our final answer.

Please let me know if this is the right approach.

Answer 1

Your answer fails a basic sanity check: the number of switches must certainly be at most $m$ and also must certainly be at most $n$. Your formula does deliver a result that is less than $m$; but, taking (for instance) $n=1$ and $m=4$ yields a result bigger than $n$. So, back to the drawing board!

The issue here is that your $X_i$ are not identically distributed, as you've claimed. The last zero ($X_m$) is less likely to have a one after it than the others... because it could be in the last position!

So, my hint is this. Instead of considering your variables $X_1,\ldots,X_m$, consider the variables $Y_1,\ldots,Y_{n+m-1}$, where $Y_i$ is the indicator that there is a zero in position $i$ and a one in position $i+1$. These ARE identically distributed, their sum is still $W$, and they can lead you to the right answer.

Answer 2

Here is a remodel of the question. I have a string of n '1' characters, and now I am putting m '0' characters before, between and after them. In other words, there are n+1 bins and there are m balls. We are putting m balls into the n+1 bins and we need to see how many non empty bins there are excluding the last bin. I believe that this is what needs to be presented at an interview.