Probability with Martingales

enter image description here

This was answered here using bounds and here using PGF. I would like to try inclusion-exclusion.

Let $H_1, H_2, ...$ be independent events with $P(H_k) = p$ where $H_k$ means the kth toss is heads.

It seems that ($\cap$ omitted)

$$A_0 = H_1$$

$$A_1 = H_2 \cup H_3$$

$$A_2 = (H_4H_5) \cup (H_5H_6) \cup (H_6H_7) := \bigcup_{i=1}^{3} E_{2,i}$$

$$A_3 = (H_8H_9H_{10}) \cup ... \cup (H_{13}H_{14}H_{15}) := \bigcup_{i=1}^{6} E_{3,i}$$


$$A_k = (H_{2^k}...H_{2^k + k-1}) \cup ... \cup (H_{2^{k+1} - k}...H_{2^{k+1} - 1}) := \bigcup_{i=1}^{2^k - k + 1} E_{k,i}$$

So by inclusion-exclusion, we have

$$P(A_0) = p$$

$$P(A_1) = p + p - p^2$$

$$P(A_2) = 3p^2 - 2p^3$$

$$P(A_3) = \ldots$$

It gets tricky starting $A_3$

$$P(A_3) = P\left(\bigcup_{i=1}^{6} E_{3,i}\right)$$

Attacking that directly is going to lead to problems.

What about this?

$$P\left(\bigcup_{i=1}^{6} E_{3,i}\right)$$

$$ = P\left(\bigcup_{i=1,4} E_{3,i} \cup \bigcup_{i=2,5} E_{3,i} \cup \bigcup_{i=3,6} E_{3,i} \right)$$

$$ := P(F_{3,1} \cup F_{3,2} \cup F_{3,3})$$

Each $F$ is a union of disjoint sets.

  1. Also, I notice independence isn't being used. I guess the $H_k$'s and the $A_k$'s are independent. What about some subset of the the $E$'s? The $F$'s?
  • 1
    $\begingroup$ You can get proper spacing by using \ldots instead of periods. $\endgroup$ – joriki Jun 10 '16 at 16:35
  • $\begingroup$ Not checking all the calculations. For $P(A_2)$, is it $p^2 + p^2 + p^2 - p^3 - p^3 - p^4 + p^4$ instead? $\endgroup$ – BGM Jun 11 '16 at 5:11
  • $\begingroup$ @BGM I'm a dumbass. Thanks! ^-^ I edited my post $\endgroup$ – BCLC Jun 14 '16 at 22:01

The events you are uniting are not independent, and they intersect in intricate ways, so using inclusion-exclusion on them will quickly lead to a mess. Take for instance the union $$H_8H_9H_{10} \cup H_9H_{10}H_{11}\cup\cdots\cup H_{13}H_{14}H_{15}, $$ also known as $A_3$. Taking the sets $H_iH_{i+1}H_{i+2}$ in the union one at a time, they each have probability $p^3$, but intersecting them two at a time will yield events like $H_8H_9H_{10}\cap H_9H_{10}H_{11}=H_8H_9H_{10}H_{11}$ which have probability $p^4$ but also events like $H_8H_9H_{10}\cap H_{10}H_{11}H_{12}=H_8H_9H_{10}H_{11}H_{12}$ with probability $p^5$ and also events like $H_8H_9H_{10}\cap H_{13}H_{14}H_{15}$ with probability $p^6$. You will need to count how many there are of each type. Intersecting them three at a time will yield events with probabilities ranging from $p^5$ to $p^8$, and you're not even done with intersections four at a time and five at a time. It is not obvious whether the general form for $P(A_k)$ is compactly expressible in terms of $p$.

Better to use the bounding approach in the first answer you cited. The $p\ge\frac12$ case of the bounding argument uses the events $E_i$ defined in the hint; the $E_i$ have the advantage of being independent events, so an inclusion-exclusion argument (or finding the probability of a complement event) leads to a tidy expression. It is true that the bounding approach is not calculating the exact prob of $A_k$; rather, it is calculating upper and lower bounds on $P(A_k)$, which are sharp enough to apply the Borel-Cantelli lemma.

  • $\begingroup$ Oh how dumb of me! I screwed up the intersections. Thanks grand _chat! ^-^ I'll try again later $\endgroup$ – BCLC Jun 12 '16 at 10:45
  • $\begingroup$ grand_chat, I edited my post $\endgroup$ – BCLC Jun 14 '16 at 22:00
  • 1
    $\begingroup$ @BCLC Your edit gets you closer to the bounding approach. In your expression $F_{3,1}\cup F_{3,2}\cup F_{3,3}$, the advantage is that each $F$ is the union of independent events. However, the three $F$'s are not disjoint from each other and they still intersect messily. If you throw away all but the first of these $F$'s, keeping just $F_{3,1}:= H_{8,9,10}\cup H_{11,12,13}$ then the two events $E_{3,1}:=H_{8,9,10}$ and $E_{3,2}:=H_{11,12,13}$ you've retained are exactly as in the Hint and you still have the advantage that the two $E$'s are independent. (Note that the $E$'s are not disjoint.) $\endgroup$ – grand_chat Jun 14 '16 at 23:46
  • $\begingroup$ grand_chat, thanks. any idea if the bounding approach in the other question uses inc-exc? $\endgroup$ – BCLC Jun 16 '16 at 22:06
  • 1
    $\begingroup$ For $p<\frac12$ the bounding approach to $P(A_k)$ uses the crude bound $P(A_k)= P(\bigcup F_{k,i})\le \sum P(F_{k,i})$. You can think of the inequality $P(\cup F_i)\le \sum P(F_i)$ as a one-term truncation of inc-exc. For $p\ge\frac12$ the bounding approach computes $P(A_k)\ge P(\bigcup E_{k,i}) \stackrel{(*)}= 1-P(\bigcap E_{k,i}^c)$. Note that it is possible to prove (*) using inc-exc. $\endgroup$ – grand_chat Jun 16 '16 at 22:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.