2
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Do you understand simple random walks by any chance? $\endgroup$ – oskar szarowicz Nov 19 '20 at 15:55
  • 1
    $\begingroup$ Yes I do, I have a chemistry degree and so remember random walks from Brownian motion. I don't have a thorough understanding and I'm not a genius, so please be kind haha :) $\endgroup$ – pho_pho Nov 19 '20 at 15:59
  • $\begingroup$ Are you familiar with the reflection principle used to figure out the case of "stop when heads >= tails"? $\endgroup$ – Calvin Lin Nov 19 '20 at 16:17
  • $\begingroup$ No not at all, that's beyond my mathematical understanding... $\endgroup$ – pho_pho Nov 19 '20 at 16:22
  • $\begingroup$ I'm guessing that it is difficult to explain the solution simply, in layman's terms?... $\endgroup$ – pho_pho Nov 19 '20 at 16:23
2
$\begingroup$

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.

  1. Firstly we will construct a partition of $\Omega$ into $3$ pieces

  2. We will show that $2$ of these pieces belong to $\mathcal{S}$

  3. We will then construct more elements of $\mathcal{S}$ that are not in our initial partitions of $\Omega$

  4. 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

  5. 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:

  1. If $x \in \mathcal{S} \implies g(x) \in \mathcal{S} $ as g does not change the inital elements $u$ that result in a net $+2$ heads
  2. Notice that $g$ is its own inverse as g never changes the beginning terms, it simply flips the last and the "flipping" function is clearly its own inverse. Hence $g(g(x)) = x $
  3. g is a bijection.
  4. $g : \Omega_{>16} \to \Omega_{< 16}$ or $g : \Omega_{<16} \to \Omega_{> 16}$
    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

$\endgroup$
2
  • $\begingroup$ Wow Oskar... I'm gobsmacked, thank you so much for your explanation and the time that you took to write it out, I really appreciate it! Clearly a very intelligent person and great teacher. Would it be possible please for you to add a generic formula at the bottom for "What is the probability of having x heads ahead of the cumulative tails in y number of tosses?". I'm wondering if the 16 is found using (y/2)+1, and i is (y/2) + 2? If so, and y was odd, would you round up or down? Sorry for the uneducated questions... $\endgroup$ – pho_pho Nov 20 '20 at 7:57
  • $\begingroup$ I have answered this below :) $\endgroup$ – oskar szarowicz Nov 20 '20 at 15:01
1
$\begingroup$

Thank you for your gratitude, always happy to help a chemist! The question is very valid, asking questions is often much more important than answering them in mathematics. For what it is worth your intuition is very nearly perfect.

Let us ask ourself another question to answer yours: Why did we select 16? This is because 16 heads (and thus 30-16 = 14 ) tails was the absolute threshold to ensure we ended with a net +2 heads. Hence for $y$ total tosses to ensure a net of $+x$ we would require $\frac{y+x}{2}$ heads and $\frac{y-x}{2} $ tails. That is where the 16 came from. Hence if $x+y \equiv 0 $ mod 2. I.e are both even or both odd then the final solution is:

$ \frac{{y \choose (\frac{x+y}{2})} + \sum\limits_{i=(\frac{x+y}{2})+1}^{y}2{y \choose i}}{2^{y}}$

Now what about the annoying case of $x+y \equiv 1 $ mod 2. I.e one is odd and the other even. Funnily enough this is soooooo much easier. To ensure a net of at least $+x$ we must have $\frac{y+x+1}{2}$ heads and $\frac{y-x-1}{2}$ tails. Notice these are integers, and sum to $y$ and have difference $x+1$. As having a diffirence of just $x$ after $y$ tosses is not possible. I'd recommend playing around with these numbers using $y=29$ and $x= 2$

Now let $\Omega_{\geq\frac{y+x+1}{2}}$ and $\Omega_{<\frac{y+x+1}{2}}$ Be defined as before and clearly everything in $\Omega_{\geq\frac{y+x+1}{2}}$ eventually has a difference of $+ (x+1)$ heads and thus has is in our "successful set" $\mathcal{S} $

There is again a 1 to 1 correspondence as before by our flipping after we first have net $+x$ heads from $\Omega_{\geq\frac{y+x+1}{2}}$ to $\Omega_{<\frac{y+x+1}{2}}$

Hence the size of our successful set is just double the size of $\Omega_{\geq\frac{y+x+1}{2}}$ and the final answer is : $ \frac{ \sum\limits_{i=(\frac{x+y+1}{2})}^{y}2{y \choose i}}{2^{y}}$

Very happy to answer any further clarity, would definitely recommend you read page $6$ of this article on reflecting as it is exactly what we did.

Oskar

$\endgroup$
2
  • $\begingroup$ Brilliant answer, thanks again Oskar for taking the time to explain things clearly and thoroughly. Nice article as well, will give it a read over the weekend :) I have one more question... the stacked numbers in parentheses (in your other answer, there's one with 30 and 16, another with 30 and i), are they "30 choose 16", as described here quora.com/… and so can be solved using the factorials described in the link? $\endgroup$ – pho_pho Nov 20 '20 at 17:24
  • 1
    $\begingroup$ Indeed the vector (n,r) means n choose r and is n!/(r!)(n-r)! $\endgroup$ – oskar szarowicz Nov 20 '20 at 17:31

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.