Flip Coin Probelms
This paper aims at solving all coin flipping problems with probability.
Finite Trials Problems
In these problems, there will be a clear number of trials.
For example:
- Flip a coin \(N\) times, what is the probability of having \(M\) heads?
- Flip a coin \(N\) times, what is the probability of having more heads than tails?
- Flip a coin \(N\) times, what is the probability of having \(M\) successive heads?
Q1
Let \(X\) be number of heads. We have \(X\)~\(B(N, p)\). \[ P(X = M) = C_N^Mp^M(1-p)^{N-M}. \]
Q2
Let \(X\) be number of heads, \(Y = N-X\) be number of tails. We have \(X\)~\(B(N, p)\). \[ P(X > Y) = P(X > N/2) = \sum_{n = [N/2]+1}^N P(X = n) = \sum_{n = [N/2]+1}^N C_N^np^n(1-p)^{N-n} \] When \(p = \frac{1}{2},\) we have the symmetry property of binary coefficients. Therefore, when \(N = 2K-1,\) we have \(P(X>Y) = \frac{1}{2}.\) When \(N = 2K,\) we have \[ P(X > Y) = [1 - P(X = K)]/2 = \frac{1}{2} - \frac{C_{2K}^K}{2^{2K+1}}. \]
Q3
Here we set up \(M+1\) variables. \(s_i, i = 1,...,M.\) Here \(s_0\) is starting case or last flip is T. \(s_1\) is last flip is H. \(s_2\) is last two flips are H. ... \(s_{M-1}\) is last \(M-1\) flips are H. \(s_{M}\) is last \(M\) flips are H.
For each \(s_i, i \neq M,\) we have \(\frac{1}{2}\) probability to reach \(s_{i+1}\) and \(\frac{1}{2}\) probability to reach \(s_{0}.\) For \(s_M,\) it has 1 probability reaching itself. The initial state is \(s_0.\) We can construct the probability transfer matrix as \[ a_{n+1} = Aa_n. \] Here \(a_0 = [1, 0, ..., 0]^T \in \mathbb{R}^{M+1}, A \in \mathbb{R}^{(M+1) \times (M+1)}.\) \[ A = \left(\begin{array}{cccccc} 1/2& 1/2& 1/2& ... & 1/2 & 0\\ 1/2& 0& 0& ... & 0 & 0 \\ 0& 1/2& 0& ... & 0 & 0 \\ ... & ... & ... & ... & ... & ...\\ 0& 0& 0& ... & 1/2 & 1 \end{array}\right) \]
Then the final state after \(N\) steps is \(a_N = A^Na_0.\) The final probability of having \(M\) successive heads is the \(M+1\) dimension item of \(a_N.\) The problem turns out to calculate the eigenvalues of \(A.\) The characteristic polynomial of A is \[ \det \left(\begin{array}{cccccc} 1/2 - x& 1/2& 1/2& ... & 1/2 & 0\\ 1/2& -x& 0& ... & 0 & 0 \\ 0& 1/2& -x& ... & 0 & 0 \\ ... & ... & ... & ... & ... & ...\\ 0& 0& 0& ... & 1/2 & 1-x \end{array}\right) \]
\[ = 2^{-(M+1)}\det\left(\begin{array}{cccccc} 1 - 2x& 1& 1& ... & 1 & 0\\ 1& -2x& 0& ... & 0 & 0 \\ 0& 1& -2x& ... & 0 & 0 \\ ... & ... & ... & ... & ... & ...\\ 0& 0& 0& ... & 1 & 2-2x \end{array}\right) \]
\[ = 2^{-(M+1)} (2-2x)\times \det\left(\begin{array}{ccccc} 1 - 2x& 1& 1& ... & 1\\ 1& -2x& 0& ... & 0 \\ 0& 1& -2x& ... & 0 \\ ... & ... & ... & ... & ...\\ 0& 0& 0& ... & -2x \end{array}\right) \] \[ = 2^{-(M+1)} (2-2x)\times[ (1-2x)(-2x)^{M-1} - (-2x)^{M-2} + ... +(-1)^{1+M}\times(-2x)^{0}] \] \[ = 2^{-(M+1)} (2-2x)\times(-1)^{M-1}[ (1-2x)(2x)^{M-1} + (2x)^{M-2} + ... +(-2x)^{0}] \] \[ = 2^{-(M+1)} (2-2x)\times(-1)^{M-1}[(2x)^{M-1} + (2x)^{M-2} + ... +1 - (2x)^M] \] \[ = 2^{-(M+1)}(-1)^{M-1} \times (2-2x)\frac{-(2x)^{M+1} + 2(2x)^M -1}{2x-1} \] \[ = (-2)^{-M} \times (1-x)\frac{(2x)^{M+1} - 2(2x)^M +1}{2x-1} \] Then by letting the \((2x)^{M+1} - 2(2x)^M +1 = 0\) we can have the eigenvalues. Suppose the \(M\) roots(exclude \(x = 1/2\)) for \((2x)^{M+1} - 2(2x)^M +1 = 0\) are \(x_1, x_2, ..., x_M.\) The final solution we want is \(c = <e_{M+1}, a_N>,\) where \(e_{M+1} = [0, 0, ..., 1]^T.\) We know that \(c\) is a linear combination of the power of eigenvalues of \(A\), as \(x_1^N, x_2^N, ..., x_M^N, 1.\) We have \[ c = 1 + c_1x_1^N + c_2 x_2^N+ ...+ c_M x_M^N. \] Then we get \(b_N = 2^N(1-c) = -(c_1(2x_1)^N + ... + c_M(2x_M)^N).\) \(b_N\) has the characteristic polynomial as \((2x)^{M+1} - 2(2x)^M +1 = 0.\) It leads to the iteration formula for \(b_N\) as \(b_{N+M+1} = 2b_{N+M} -b_{N}.\) \[ b_{N+M} = b_{N+M-1} + ... +b_{N} \] Here \(b_N\) is called Fibonacci k-step number, denoted as \(F_{N}^{M}.\) Then we finally have \(c = 1-\frac{F_{N+2}^{M}}{2^N}.\)
cite:
Until Series
In these problems, there will be a stubborn guy who only stops after he gets what he want. Let's call him Mr. Stub. Normally, we would like to calculate the expectation of Mr. Stub to stop.
For example:
- Flip a coin until Stub gets 1 head.
- Flip a coin until Stub gets \(m\) heads.
- Flip a coin until Stub gets \(m\) successive heads.
- Flip a coin until Stub gets HTH pattern.
Q1 Geometric Distribution
Let \(X\) denotes the number of flips. We have \(X\)~\(Geo(p).\) \[ P(X = k) = (1-p)^{k-1}p. \] \[ E[X] = \sum_{k=1}^{\infty} kP(X = k) = \sum_{k=1}^{\infty} k(1-p)^{k-1}p \] \[ = p\sum_{k=1}^{\infty} k(1-p)^{k-1} = \frac{1}{p}. \]
Q2 Negative Binomial Distribution
Let \(X\) denotes the number of flips. We have \(X\)~\(NB(m, p)\) \[ P(X = k) = C_{k-1}^{m-1}p^{m-1}(1-p)^{k-m}p = C_{k-1}^{m-1}p^m(1-p)^{k-m}. \] \[ E[X] = \sum_{k = m}^{\infty} kP(X = k) = m(1-p)p^{-1}. \]
Q3
A naive approach to solve the expectation. Denote the expectation as \(E.\) Then we have \[ E = \frac{1}{2}(E+1) + \frac{1}{4}(E+2) + ... \frac{1}{2^m}(E+m)+\frac{1}{2^m}m \] Solve it we get \(E = 2^{m+1}-2.\)
Generating Function Approach(for special case when \(m = 5\)): Here we have the following basic cases with their probability: T -- 1/2 -- 1/2 \(x\) HT -- 1/4 -- 1/4 \(x^2\) HHT -- 1/8 -- 1/8 \(x^3\) HHHT -- 1/16 -- 1/16 \(x^4\) HHHHT -- 1/32 -- 1/32 \(x^5\) HHHHH -- 1/32 -- 1/32 \(x^5\)
Then all possible sequences that satisfy the requirements is a combination of first 4 cases end up with final case. The generating function with probability of ending after \(n\) toss as the coefficient of \(n\) order is \[ f(x) = \sum_{k = 0}^{\infty} (\frac{1}{2}x + \frac{1}{4}x^2 + \frac{1}{8}x^3 + \frac{1}{16}x^4 + \frac{1}{32}x^5)^k\frac{1}{32}x^5 \] \[ = \frac{\frac{1}{32} x^5}{1 - (\frac{1}{2}x + \frac{1}{4}x^2 + \frac{1}{8}x^3 + \frac{1}{16}x^4 + \frac{1}{32}x^5)} = \frac{\frac{1}{32}x^5 - \frac{1}{64}x^6}{1-x+\frac{1}{64}x^6}. \] Then the expectation is \(f'(1) = 62.\)
cite:
Expected Number of Coin Tosses to Get Five Consecutive Heads
Q4:
Naive approach: Let \(E\) be the expectation of having HTH. \[ E = \frac{1}{2}(E+1) + \frac{1}{2}(\frac{1}{2}(E) + \frac{1}{2}(\frac{1}{2}3 + \frac{1}{2}(E+3))) \] Solve this we get \(E = 10.\)
Martingale Approach: Assume we have a pattern F, then the expectation can be calculated as \[ E = \sum_{k = 1}^{n} f_k \frac{1}{p_1p_2...p_k}. \] Here \(f_i = 1\) when first \(i\) characters are the same as last \(i\) characters. \(p_i\) is the probability of \(i\)-th character happens.
Take HTH for example. k = 1, first 1 character: H, last 1 character H. \(f_1 = 1\) and \(p_1 = 1/2.\) k = 2, first 2 characters: HT, last 2 characters: TH, \(f_2 = 0.\) k = 3, first 3: HTH, last 3: HTH. \(f_3 = 1.\) \(p_1 = p_2 = p_3 = 1/2.\)
Therefore, 2+0+8 = 10.
cite:
Gambling Couples
In these problems, there will be a gambling couple trying to win each other by setting wining conditions. Let's call them Alice and Bob.
For example:
- Flip a coin infinite times. Alice wins when HTH pattern shows. Bob wins when THH shows. What is the probability of each one to win?
Q1
Martingale Solution By constructing a martingale, we could get the following two equations. Solve them we can get \(P_1, P_2.\) \[ E_1*P(Pattern1) = E_2*P(Pattern2) \] \[ P(Pattern1) + P(Pattern2) = 1 \] Then the \(E_1\) and \(E_2\) are calculated as below. \[ E_1 = \sum_{k = 1}^{n} f_k \frac{1}{p_1p_2...p_k} - \sum_{k = 1}^{n} g_k \frac{1}{p_1p_2...p_k}. \] \[ E_2 = \sum_{k = 1}^{n} h_k \frac{1}{p_1p_2...p_k} - \sum_{k = 1}^{n} r_k \frac{1}{p_1p_2...p_k}. \]
\(f_i = 1\) when pattern 1 first \(i\) characters are the same as pattern 1 last \(i\) characters.
\(g_k = 1\) when pattern 2 first \(k\) characters are the same as pattern 1 last \(k\) characters.
\(h_i = 1\) when pattern 2 first \(i\) characters are the same as pattern 2 last \(i\) characters.
\(r_i = 1\) when pattern 1 first \(i\) characters are the same as pattern 2 last \(i\) characters.
\(p_i\) is the probability of \(i\)-th character happens.
For example: Pattern 1: HTH, Pattern 2: THH
\(k =1,\) \(f_1 = 1, g_1 = 0, h_1 = 0, r_1 = 1, E_1 = 2, E_2 = -2.\)
\(k=2, f_2 = 0, g_2 = 1, h_2 = 0, r_2 = 0, E_1 = -2, E_2 = -2.\)
\(k = 3, f_3 = 1, g_3 = 0, h_3 = 1, r_3 = 0, E_1 = 6, E_2 = 6.\)
Therefore, we have \(P_1 = P_2 = \frac{1}{2}.\)
Pattern 1: THH, Pattern 2: TTT
\(k = 1, f_1 = 0, g_1 = 0, h_1 = 1, r_1 = 1, E_1 = 0, E_2 = 0.\)
\(k = 2, f_2 = 0, g_2 = 0, h_2 = 1, r_2 = 0, E_1 = 0, E_2 = 4.\)
\(k = 3, f_3 = 1, g_3 = 0, h_3 = 1, r_3 = 0, E_1 = 8, E_2 = 12.\)
Therefore, we have \(8P_1 = 12P_2, P_1 + P_2 = 1.\) \(P_1 = \frac{2}{5}, P_2 = \frac{3}{5}.\)
cite: