概率分析：赌徒争议下的连续正面概率问题求解

Part (a): Finding the smallest n for >50% winning chance for Gambler 2 #

Alright, let's break this down. Gambler 2 wins if there’s at least one run of consecutive heads (HH) in n coin flips. To make this easier, let’s define:

• $Q(n)$ = probability of not getting consecutive heads in n flips (Gambler 1’s win probability)
• $P(n)$ = probability of getting at least one HH (Gambler 2’s win probability) = $1 - Q(n)$

We need the smallest n where $P(n) > 0.5$, which translates to $Q(n) < 0.5$.

Step 1: Recurrence relation for $Q(n)$ #

Think about the last flip in the sequence:

• If the nth flip is tails (T), the first n-1 flips just need to avoid consecutive heads: probability $\frac{1}{2}Q(n-1)$
• If the nth flip is heads (H), the (n-1)th flip must be tails, and the first n-2 flips avoid consecutive heads: probability $\frac{1}{2}Q(n-2)$

This gives us the recurrence:
$$Q(n) = \frac{1}{2}Q(n-1) + \frac{1}{2}Q(n-2)$$

Step 2: Calculate values with initial conditions #

Start with the base cases:

• $Q(1) = 1$ (only 2 outcomes, no way to get HH)
• $Q(2) = \frac{3}{4}$ (only HH is the losing case for Gambler 1)

Now compute step-by-step (it’s easier to count valid sequences instead of just using the recurrence to avoid mistakes):

• n=3: Valid sequences (no HH) are TTT, TTH, THT, HTT, HTH → 5 total. $Q(3) = \frac{5}{8} = 0.625$, so $P(3) = 0.375$
• n=4: Valid sequences jump to 8 (follows Fibonacci pattern: 2, 3, 5, 8...). $Q(4) = \frac{8}{16} = 0.5$, so $P(4) = 0.5$ (exactly 50%, not over)
• n=5: Valid sequences are 13. $Q(5) = \frac{13}{32} ≈ 0.406$, so $P(5) = 1 - 0.406 ≈ 0.594 > 0.5$

The smallest n where Gambler 2 has over 50% chance is n=5.

Part (b): General formula for $P(n)$ #

We can solve the linear recurrence for $Q(n)$ using characteristic equations. The characteristic equation for $Q(n) = \frac{1}{2}Q(n-1) + \frac{1}{2}Q(n-2)$ is:
$$r^2 = \frac{1}{2}r + \frac{1}{2}$$
Multiply by 2: $2r^2 - r - 1 = 0$, which factors to $(2r+1)(r-1)=0$. The roots are $r=1$ and $r=-\frac{1}{2}$.

The general solution for $Q(n)$ is:
$$Q(n) = A(1)^n + B\left(-\frac{1}{2}\right)^n$$

Using our initial conditions to solve for A and B:

1. For n=1: $A - \frac{1}{2}B = 1$
2. For n=2: $A + \frac{1}{4}B = \frac{3}{4}$

Solving these gives $A=\frac{5}{6}$ and $B=-\frac{1}{3}$. Plugging back in:
$$Q(n) = \frac{5}{6} - \frac{(-1)^n}{3*2n}$$

Since $P(n) = 1 - Q(n)$, we simplify to get:
$$P(n) = \frac{1}{6} + \frac{(-1)^{n+1}}{3*2n}$$

Alternatively, since the number of valid sequences (no HH) follows a Fibonacci-like sequence ($F(n) = F(n-1)+F(n-2)$, $F(1)=2$, $F(2)=3$), we can also write:
$$P(n) = \frac{2^n - F(n)}{2^n}$$

内容的提问来源于stack exchange，提问作者Curious