pydata

Keep Looking, Don't Settle

An interesting random walk question and simulation 03

This is to modify the answer to the previous blog about the expectation number of flips to get the pattern of the coin. For example: if flip a fair coin, what is the expected flips to get 3 consecutive Heads (HHH)? What is the expectation of flips to get Head, Tail and Head(HTH) or more status like HHHH?

Take the question of HHH as an example: this is a stochastic question about Markov Chain. The possible status will be {0, H, HH, HHH}. The corresponding status transition matrix is

0 H HH HHH
0 0.5 0.5 0 0
H 0.5 0 0.5 0
HH 0.5 0 0 0.5
HHH 0 0 0 1

Denote the expected flips from 0 to HHH as f(0), the expected flips from H to HHH as f(H), the expected flips from HH to HHH as f(HH) and the expected flips from HHH to HHH as f(HHH). It is clear that f(HHH) = 0 since it is already reaching the status. Title: An interesting random walk question and simulation 03 Date: 2017-10-08 16:08 Modified: 2017-10-08 16:08 Category: Python Tags: python, random walk Slug: Author: Huiming Song Summary: Got some random walk questions from my friend. We may see lots of similar questions in stochastic process. Here is the question.

Based on the status transition matrix, we have

\begin{equation} \begin{cases} f(0) = \frac{1}{2} f(0) + \frac{1}{2} f(H) + 1 \\ f(H) = \frac{1}{2} f(0) + \frac{1}{2} f(HH) + 1 \\ f(HH) = \frac{1}{2} f(0) + \frac{1}{2} f(HHH) + 1 \\ f(HHH) = 0 \end{cases} \end{equation}

Based on these, we can solve f(0) = 14. So the expectation number of flips to get HHH is 14 times.

Similarly, we can calculate the expected number of flips to get HOH as below:

0 H HT HTH
0 0.5 0.5 0 0
H 0 0.5 0.5 0
HT 0.5 0 0 0.5
HTH 0 0 0 1
\begin{equation} \begin{cases} f(0) = \frac{1}{2} f(0) + \frac{1}{2} f(H) + 1 \\ f(H) = \frac{1}{2} f(H) + \frac{1}{2} f(HO) + 1 \\ f(HO) = \frac{1}{2} f(0) + \frac{1}{2} f(HOH) + 1 \\ f(HOH) = 0 \end{cases} \end{equation}

By solving these equations, we will get f(0) = 10.

Similarly, we can calculate the expectation number of flips for HHHH or the other more complicated cases.

0 H HH HHH HHHH
0 0.5 0.5 0 0 0
H 0.5 0 0.5 0 0
HH 0.5 0 0 0.5 0
HHH 0.5 0 0 0 0.5
HHHH 0 0 0 0 1

The following is to simulate the results in python.

def calcpattern(patstr):
    res = []
    t = 0
    while True:
        i = 0
        pos = []
        while True:
            x = np.random.randint(0, 2, 100)
            x = [str(s) for s in x]
            joinx = ''.join(x)
            try:
                p = joinx.index(patstr) + 3
                pos.append(p)
            except Exception as e:
                continue
            i += 1
            if i > 500:
                print('jump out i ' + str(i))
                break

        pos = np.array(pos)
        res.append(np.mean(pos))
        t += 1
        print('jump out t ' + str(t))
        if t > 500:
            break

    res = np.array(res)
    print("The expected number of tosses for pattern %s is %f" %(patstr, np.mean(res)))

calcpattern('101')
calcpattern('010')
calcpattern('110')
calcpattern('1111')