Let \(X\) = number of flips until first heads with \(\Pr[\text{heads}] = p\). What method do we use in a memoryless problem like this?
Note 1: ETH::2. Semester::A&W
Deck: ETH::2. Semester::A&W
Note Type: Horvath Classic
GUID:
added
Note Type: Horvath Classic
GUID:
bn:Zftw53>
Previous
Note did not exist
New Note
Front
Back
Let \(X\) = number of flips until first heads with \(\Pr[\text{heads}] = p\). What method do we use in a memoryless problem like this?
Define \(K_1\) = "first flip is heads." Apply total expectation conditioned on \(K_1\): -
- \(\mathbb{E}[X \mid K_1] = 1\) (done immediately)
- \(\mathbb{E}[X \mid \bar{K}_1] = 1 + \mathbb{E}[X]\) (memoryless: after tails, the process restarts identically, plus the one spent flip)
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Front | Let \(X\) = number of flips until first heads with \(\Pr[\text{heads}] = p\). What method do we use in a <i>memoryless</i> problem like this? | |
| Back | Define \(K_1\) = "first flip is heads." Apply total expectation conditioned on \(K_1\): - <br><ul><li>\(\mathbb{E}[X \mid K_1] = 1\) (done immediately) </li><li>\(\mathbb{E}[X \mid \bar{K}_1] = 1 + \mathbb{E}[X]\) (memoryless: after tails, the process restarts identically, plus the one spent flip) </li></ul>Plugging into \(\mathbb{E}[X] = 1 \cdot p + (1 + \mathbb{E}[X])(1-p)\) and solving yields \(\mathbb{E}[X] = 1/p\). Avoids computing \(\sum k \cdot (1-p)^{k-1} p\) directly. |