2
$\begingroup$

If I flip a coin until I get "heads", sooner or later, I will get one occurrence and stop. Probability of success is 1. But what if after each "tails" (failed) draw, odds for the next draw are divided by 2 ? Instead of having successive odds like 0.5, 0,5, 0.5, etc... I have 0.5, 0.25, 0.125, etc... Is it possible to never get "heads"?

Trying to figure out this, I ran the following rust code:

use rand;

fn draw() -> bool {
    const MIN_MAX: f64 = 1e-20;
    let mut max = 1.0;
    while max > MIN_MAX {
        max /= 2.0;
        if rand::random::<f64>() < max {
            return true
        }
    }
    false
}

fn main() {
    const TOTAL: i32 = 10_000_000;
    let mut success = 0;
    for _ in 0..TOTAL {
        if draw() {
            success += 1;
        }
    }
    println!("{} / {}", success, TOTAL);
}

Some comments:

  • I found an overall probability of 0.711
  • The MIN_MAXis the minimum value of individual draw odds at which the program gives up and return false. Changing this value between 1e-20 and 1e-40 does not change the result much.

I would be interested to know if the overall probablity is below 1, and if so, what are the fancy maths to explain the result.

EDIT 1 2021-03-20:

Probability to have success between 1 and n draws would be: $\frac{1}{2}+\frac{1}{2\times4}+\frac{1\times3}{2\times4\times8}+\frac{1\times3\times7}{2\times4\times8\times16}...$ (too bad at jaxmath for formula with n) which converges to 0.7112119049133813

EDIT 3 2021-03-20:

Googling 7112119049I found this: https://forumserver.twoplustwo.com/47/science-math-philosophy/538-riddler-question-about-coin-flipping-game-1719467/

$\endgroup$
1
$\begingroup$

For each positive integer $n$, let $x_n$ be the probability that experiment terminates in at most $n$ flips.

Then we have the recursion $$ x_n=x_{n-1}+(1-x_{n-1})\Bigl({\small{\frac{1}{2}}}\Bigr)^n $$ for $n > 1$, together with the initial value $x_1={\large{\frac{1}{2}}}$.

Claim:$\;$For all $n$ we have $ {\large{\frac{1}{2}}} \le x_n < {\large{\frac{3}{4}}} $.

Proof:

From the definition of $x_n$ (or from the recursion), it's immediate that $x_n\ge x_{n-1}\;$for all $n > 1$.

It follows that $x_n\ge {\large{\frac{1}{2}}}\;$for all $n$.

For the upper bound, we prove the more precise claim: $ x_n \le {\large{\frac{3}{4}}}-{\large{\frac{1}{2^{n+1}}}} $.

Proceed by induction on $n$ . . .

The base case $n=1$ is easily verified.

Next let $n > 1$ and assume the claim holds for the previous value of $n$.$\;$Then \begin{align*} x_n&=x_{n-1}+(1-x_{n-1})\Bigl({\small{\frac{1}{2}}}\Bigr)^n \\[4pt] &\le \left(\frac{3}{4}-\frac{1}{2^n}\right) + \Bigl( \frac{1}{2} \Bigr) \Bigl(\frac{1}{2}\Bigr)^n \\[4pt] &= \frac{3}{4}-\frac{1}{2^{n+1}} \\[4pt] \end{align*} which completes the induction.

$\endgroup$
0
$\begingroup$

Googling 7112119049, I found a discussion (and explanations) very close to this question: https://forumserver.twoplustwo.com/47/science-math-philosophy/538-riddler-question-about-coin-flipping-game-1719467/ Probablity of success is:

$1-phi(\frac{1}{2})$

where phi is the Euler function.

$\endgroup$

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.