# What is the overall probability of success of infinite draws with exponentially decreasing odds of success per draw?

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);
}

• 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:

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.

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.