Find the expected number of two consecutive 1's in a random binary string

A computer randomly generates a binary string of 65 bits, a mix of 0’s and 1’s. The question is, how to find the expected number of two consecutive 1’s? For example, 110111 has 3 occurrence, and 010110 has 1 occurrence.

I did some research but still was unable to think through. When I saw the word ‘expect’, my first though was about Bernoulli distribution.

How to calculate the expected value of number of two consecutive zeros in a randomly-generated binary string?

The site above was the one that I tried to understand and kind of understood it, but the case was different, so I am still confused right now.

Thank you very much for helping me 😀

Solutions Collecting From Web of "Find the expected number of two consecutive 1's in a random binary string"

The key here is that expectation is linear. Now, you have $n=65$ (independent) bits $x_1,\dots,x_n$, that you can use to get $n-1=64$ different random variables $X_1,\dots,X_{n-1}$: $X_i$ is equal to $1$ if $(x_i,x_{i+1}) = (1,1)$, and zero otherwise.

  • Step 1: show that $\mathbb{E}[X_i] = \frac{1}{4}$ for all $1\leq i\leq n-1$ (using the fact that $x_i$ and $x_{i+1}$ are independent (uniformly) random bits);
  • Step 2: it is true that the $X_i$’s are not independent. But as stated upfront, the expectation is a linear operator, and does not require independence:
    $$
    \mathbb{E}\left[ \sum_{i=1}^{n-1} X_i \right] = \sum_{i=1}^{n-1} \mathbb{E}\left[X_i \right]
    $$
    even though the $X_i$’s are not independent.

Can you conclude?

Hint: Try working inductively. Solve the problem for $n$ bits, using the fact that when you append a bit to the end of a string, you are only increasing the number of pairs of $2$’s if the bit is a $1$ and if the string ends in a $1$

Another hint. There are 64 pairs of bits in a 65 bit string, and for each pair the probability of 11 is …

The expected number of two consecutive 1s in a random binary string is 25%.