Number of flips on a binary string to get m consecutive 1s

144 Views Asked by At

I am thinking about a deceptively simple problem, at least for my admittedly poor statistics standard.

A $k$ long binary string of all $0$s is given. A random element is chosen, and flipped. What is the expected number of flips until $m$ consecutive $1$s appear?

I would also be content with a "toroidal" string, such that for example $110001$ counts as a string with $3$ consecutive $1$s.

I could not make any progress at all. The best I have got so far is considering the string as a vertex of a $k$-dimensional hypercube. Then the "flipping" turns the problem to a random walk on the hypercube. But how to characterise vertices that have $m$ consecutive coordinates equal to $1$? Any hint welcome, such as "read chapter X of textbook Y", or "have a look at this technique". Thanks a lot

EDIT Following the remarks from @lulu, I attach below a chart documenting the mean time for reaching $m$ consecutive $1$s on a string long $k$, starting from all $0$s (averages over one thousands trials). enter image description here

The numerical results are (rows for string length, columns for mean flipping time)

\begin{equation} \left( \begin{array}{*5{c}} 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 1 & 3.986 & 0 & 0 & 0\\ 0 & 1 & 5.112 & 13.87 & 0 & 0\\ 0 & 1 & 6.571 & 18.165 & 43.81 & 96.468\\ \end{array}\right) \end{equation}

For completeness's sake I paste below the snippet used to get the numbers and the plot

import numpy as np
import random
import matplotlib.pyplot as plt

def flipping (string_length,m):

    s = np.zeros(string_length,dtype=bool)
    counter = 0
    max_count = 0
    count_one = 0
    while max_count < m: 
        count_one = 0
        max_count = 0
## Choose random element to flip, and flip
        randelem = np.random.randint(string_length)
        s[randelem] = np.logical_not(s[randelem])
## Count consecutive 1s
        for i in range(string_length):
            if s[i] == 0:
                count_one = 0
            else:
                count_one += 1
                max_count = max(max_count, count_one)
                counter +=  1

    return counter,s , max_count



number_of_m = 10
number_of_l = 6
number_of_realis = 1000
## Initialise array to hold results: 
## rows to string lengths, columns to number of required consecutive ##1s
res = np.zeros((number_of_l, number_of_m))
## choose number of trials, initialise array to hold individual ##results
realis = np.zeros(number_of_realis)
## loop using the above defined "flipping" function
for len in range ( number_of_l):
    for m in range (len+1):
        for j in range(number_of_realis):
            realis[j] = flipping(len, m)[0]
        res[len,m] = np.average (realis)

## plot

for i in range (1, 6):
    plt.plot(np.arange(1,i+1),  res[i,1:i+1],label=f"string lenght = {i}")
plt.xlabel("Number of consecutive 1s")
plt.ylabel("Mean number of flips")
plt.legend()
plt.savefig("math_stack.png")

I also add a plot for larger $m$, it is actually quite interesting, it actually reminded me that I would already be quite content getting some result in the limit of string length $\to \infty$, at fixed $m$, maybe this is more tractable. enter image description here