You toss a coin 30 times. A head is a win, a tails is a loss. What's the probability of getting two heads ahead of the cumulative tails in these 30 tosses. You stop tossing the coin once you have achieved two heads more than tails.
For example:
tails, heads, heads, heads
is a win because you have two more heads than tails.
tails, tails tails, tails, heads, tails, heads, heads, tails, heads, tails, heads, heads, heads, heads, heads
is a win because you have 7 tails, and 9 heads.
What is the probability of having x heads ahead of the cumulative tails in y number of tosses?
Hopefully that makes sense and thanks in advance, and please provide a formula for how this is calculated.
Best Answer
Really interesting question! Thanks for posting. I don't think you have received an answer yet so I will take a bit of time to talk you through it all. Let us use a little formal notation and define some sets that will help us solve this problem. We are going to define and examine 3:
$\bf{\Omega:}$
Let us define $\Omega$ as our sample space of $\textbf{all}$ outcomes. I.e $\Omega$ is the set of all different sequences of $30$ coin flips. Clearly the size of $\Omega$ is $2^{30} $
$\bf{\mathcal{S}}: $
We define $\mathcal{S} \subset \Omega$ As the set of $\bf{all} $ successful sequences. i.e $HHHHHHHTHHHHTHHHHHHHHHHHHHHHTTT \in \mathcal{S} $ Clearly the probability we are after is $\frac{|\mathcal{S}|}{|\Omega|}$ and as we already have $|\Omega|$ all we need is $|\mathcal{S}|$ and we are done. Eyes on the prize.
$\bf{\mathcal{U}:}$
Now call $\mathcal{U}$ this set of unique ways to reach the position where #H = #T $+2$ for the first time. Elements of $\mathcal{U}$ are a sort of truncation of element from $\mathcal{S}$
For example: $HH , THHH, $and the example you gave are all some elements of $\mathcal{U} $
Notice that $\mathcal{U} \not \subset \Omega $ as $\mathcal{U} $ is $\textbf{not}$ a set of $\textbf{full}$ sequences of 30 flips, it is just the opening moves to reach this net $+2$ heads. Elements of $\mathcal{U} $ will correspond somewhat to elements of $\mathcal{F}$ eventually. For example:
$ \mathcal{U} \ni HH \not \in \Omega $ but $HHHHHHHTHHHHTHHHHHHHHHHHHHHHTTT \in \mathcal{S} \subset \Omega$ Every element of $\mathcal{S}$ has one unique corresponding element in $\mathcal{U}$
We are going to solve this problem in 5 distinct steps.
Firstly we will construct a partition of $\Omega$ into $3$ pieces
We will show that $2$ of these pieces belong to $\mathcal{S}$
We will then construct more elements of $\mathcal{S}$ that are not in our initial partitions of $\Omega$
We will then show that $\mathcal{S}$ contains only elements of these three sets, the two partitions of $\Omega$ and the final set we constructed in step 3
The sum of the size of these $3$ pieces make up the size of $\mathcal{S}$ (what we are after)
$\textbf{Step 1:}$
Call $\Omega_{16}, \Omega_{>16} $ and $\Omega_{<16}$ respectively the elements of $\Omega$ that contain 16, more than 16 and less than 16 heads. This is clearly a mutually disjoint partition.
Examples: 16 heads followed by 14 tails is in $\Omega_{16}.$ All heads and all tails a respectively in $\Omega_{>16}$ and $\Omega_{<16}$
$\textbf{Step 2:}$
Clearly elements of $\Omega_{16}$ and $ \Omega_{>16} $ are all elements of $\mathcal{S}$ as these are sequences with at least 16 heads and thus at most 14 tails and as such there exists (at least one) point in which we have 2 more heads than tails. Hence $\Omega_{16} \cup \Omega_{>16} \subseteq \mathcal{S} $
$\textbf{Step 3:}$
What I intended to do now is, for $\textbf{every single element of} $ $\bf{\Omega_{>16}}$, generate another element of $\mathcal{S} $ that is in $\Omega_{<16}$
For each element $x \in \Omega_{>16} \subset \mathcal{S} $ we shall call $u$ the corresponding element in $\mathcal{U}$ For example if $ x = HTHTHTHHHHHHHTTTHHHHHHHHHHHHHHH$ then $u = HTHTHTHH$ or if $ x = HHHHHHHHHHHHHHHHHHHHHHHHHHHHH$ then $u = HH$
Now call $l$ the "leftover" of $x$ when we take away $u$
Examples: if $ x = HTHTHTHHHHHHHTTTHHHHHHHHHHHHHHH$ then $u = HTHTHTHH$ and $l = HHHHHTTTHHHHHHHHHHHHHHH$
Now define a function "flipped", $f:$ Sequences $\to$ Sequences by flipping each tail to a head and each head to a tail.
Example: $f(HTHTTT) = THTHHH $
Now finally for each $x \in \Omega_{>16} $ define $g(x): \mathcal{S} \to \mathcal{S} $ by $g(x) := u +f(l) $
Example: If $x = TTHHHHHHHHHHHTHTHHHHHHHHHHHHHH $ then $g(x) = TTHHHH + f(HHHHHHHTHTHHHHHHHHHHHHHH) = TTHHHH + TTTTTTTHTHTTTTTTTTTTTTTT = TTHHHHTTTTTTTHTHTTTTTTTTTTTTTT$
Properties of g:
As if $x$ has $h$ heads and $t$ tails with $h_u$ heads in $u$ and $h_u - 2$ tails in $u$ with $h$ > 16 (i.e it is in $\Omega_{>16} $ ) then $g(x) $ has $h_u$ heads in $u$ and $t-(h^u-2) = t + 2 - h^u$ heads in $l$ Hence has $t + 2$ heads in total. And as $h = 30 - t > 16 $ we have $t +2 < 16 $ Hence $g(x) \in \Omega_{<16} \iff x \in \Omega_{>16} $ and visa versa
Define $ \Omega_{<16} \supset \Omega_{G} := g(\Omega_{>16}) \subset \mathcal{S} $ as everything in $ \Omega_{>16} $ is in $\mathcal{S} $ and property 1) of g shows that it will keep everything in $\mathcal{S} $
$\textbf{Step 4:}$
We now have $3$ disjoint sets: $\Omega_{16} , \Omega_{>16} , \Omega_{G} $
Define $\mathcal{B} := \Omega_{16} \cup \Omega_{>16} \cup \Omega_{G}$
We will prove $\mathcal{B} = \mathcal{S}$
We have already show that everything in $\Omega_{16} , \Omega_{>16} , \Omega_{G} $ is in $\mathcal{S}$ Hence $\mathcal{B} \subseteq \mathcal{S}$ Thus all we wish to show for equality is : $\mathcal{S} \subseteq \mathcal{B}$
Finally assume $ x \in \mathcal{S}$ we have $3$ options as to which of $\Omega_{16} , \Omega_{>16} , \Omega_{<16} $ $x$ belongs to. If $x$ is in one of the first two then great! As this would imply $x \in \mathcal{B} $
If $ x \in \Omega_{<16} \cap \mathcal{S} \implies g(x) \in \Omega_{>16} \implies g(g(x)) = x \in g(\Omega_{>16}) = \Omega_{G} \implies x \in \mathcal{B} $
Hence $\mathcal{S} \subseteq \mathcal{B}$ and as $\mathcal{B} \subseteq \mathcal{S}$ we have $\mathcal{B} = \mathcal{S}$
$\textbf{Step 5:}$
$|\mathcal{S}| = |\mathcal{B}| = |\Omega_{16} \cup \Omega_{>16} \cup \Omega_{G}| = |\Omega_{16}|+ |\Omega_{>16}|+|\Omega_{G}| $ (as they are disjoint sets.) $ = {30 \choose 16} + \sum\limits_{i=17}^{30}{30 \choose i} + |\Omega_G|$
However $\Omega_G$ is the image of an bijective map from a finite set and as such its size is equal to the size of its domain and as thus$ |\Omega_{>16}|=|\Omega_{G}| = \sum\limits_{i=17}^{30}{30 \choose i} $
And thus : $|\mathcal{S}| = {30 \choose 16} + 2\sum\limits_{i=17}^{30}{30 \choose i} $
And hence probability to have won this game, $\frac{|\mathcal{S}|}{|\Omega|} $ = $\frac{{30 \choose 16} + 2\sum\limits_{i=17}^{30}{30 \choose i}}{2^{30}} \approx 0.720100131817 $
I hope this helped.
Oskar