How to bet? (part 2)

In the previous article, we tried a strategy called ‘timid play’ where we keep betting a fixed amount every time (on even-stake games) until we reach a target or go broke. Our goal was to find out how to maximize the probability of reaching the target. We saw that it was optimal to increase that fixed amount if the game is unfair. For example, if we have €100 as our initial fortune and our target is €200, it was better to bet €50 on each game than €2

But like the previous article, we need a quick refresher on some maths concepts that will help to fully understand this article.

• binary expansion :

0.65 in binary is 0000.1010011001100110011 because :

any number between 0 and 1 can be written as :

where xᵢ ∈ {0, 1} . This is called the binary expansion of x.

However, some numbers (called dyadic rationals, such as 1/2, 1/4, 3/8, …) have two distinct binary representations. For example, 1/2 can be written as either 0.1 or 0.0111111… (with infinitely repeating 1's). Throughout this article, we adopt the convention of using the first representation.

we note the i-th bit of x as xᵢ, so for example, for the number: 0.1011 x₁=1, x₂=0, x₃=1, x₄​=1.

• How to prove that a distribution of a variable X is continious?

We can just prove that P(X = x)=0 for all x ∈ ℝ. Why does this work? This is based on a characterization of continuous distributions : “a random variable X has a continuous distribution if and only if P(X=x)=0 for all x ∈ ℝ.” It is not very intuitive at first, but we can prove it:

⇒ (If F is continuous, then P(X = x) = 0): Let’s denote F(x) = P(X ≤ x). We know that F is non decreasing and right-continous (the function doesn’t jump if you approach x from the right-hand side. F(x+0.0001) almsot equal to F(x)).We can write: P(X = x) = F(x) − F(x⁻), where F(x⁻) denotes the left-hand limit of F at x. Since F is continuous, we have F(x⁻) = F(x). Therefore, P(X = x) = F(x) − F(x) = 0.

⇐ (If P(X = x) = 0 for all x, then F is continuous): We know that F is always right-continuous, so F(x⁺) = F(x). We also know that P(X = x) = F(x) − F(x⁻) = 0 for all x ∈ ℝ. This implies F(x) = F(x⁻) for all x ∈ ℝ. Combined with right-continuity, we conclude: F(x⁻) = F(x) = F(x⁺) for all x ∈ ℝ. Therefore, F is continuous at every point x.

• induction reasoning : (to prove a statement is true for all n ∈ ℕ)

First, we prove it’s true for n = 0 , then we prove that “if true for n = k, then true for n = k+1”. Once this is done, since it’s true for n = 0 ,it will be true for n = 1 And “true for 1 → true for 2” (inductive step with k=1) and so on…

• Dense set:

In mathematics, a set A is dense in another set B when elements of A are “spread throughout” B in such a way that you can get arbitrarily close to any element of B using elements from A.

More formally, A is dense in B if every point in B is either in A, or is a limit point of A. This means: For any point b in B and any “distance” ε > 0 (no matter how small), you can find a point a in A such that the distance between a and b is less than ε.

What’s interesting about this, is that the dyadic rationals we saw above :

are dense in [0,1]. You can see it for example if you take a random number , let’s say 0.46 , we can approximate it with a dyadic rational for example 30147/2¹⁶ and of course we can find better.

To prove that density property, just pick two reals r and s in [0,1] with r < s. Using the Archimedean property (2ⁿ > 1/(s-r)), you can prove that there exists a dyadic m/2ⁿ between r and s

• end of the refresher

Let’s study this strategy called Bold Play: if our fortune is less than half the target, we bet ALL-IN; otherwise we bet the difference (target minus fortune). So with target a and current fortune x, we bet min{x, a − x}.

Put another way: when x < a/2 we bet x, and when x ≥ a/2 we bet a − x. Our bet size depends on how far we are from the target relative to the halfway point.

Now, we can normalize this by expressing everything as a fraction of the target. If x represents our fortune as a proportion of a (so x ranges from 0 to 1), then when x < 0.5 we bet x, and when x ≥ 0.5 we bet 1 − x (the remaining fraction needed to reach the target). This gives us a simple betting function:

So we can say that the chance to hit target a starting from fortune x equals the chance to hit target 1 starting from x/a.

From now on, we’ll work exclusively with ratios of initial fortune to target. When we write x ∈ [0, 1], we mean x is the ratio fortune/target.

To study this strategy, we need to know the probability of reaching the target from any starting position. Let’s denote F(x) as the probability of reaching target 1 when our current fortune is x. To find the expression for F, we’ll apply the same method as in Part 1: first derive a functional equation, then solve it.

Let’s start: if x ≤ 1/2, we bet all-in but cannot reach the target in a single win. F(x) equals the Pr(winning this bet) x Pr(reaching the target from our new fortune) + Pr(losing) x Pr(reaching the target from zero). this is : F(x) = pF(2x)+qF(0) = pF(2x) and same for x>1/2, we can write : F(x) = p+q*F(2x-1)

From here, we can already calculate some probabilities. For example, suppose our initial fortune is 10€ and we want to reach a target of 80€, with a win probability of p = 0.4. Then the probability of reaching the target is

which is equal to 0.064. (If we used that timid strategy from part1 and bet 5€ each time, the probability of reaching the target is :0.0019 , with a bet of 1€ it is 0.00000….)

We can easily notice that when p = 1/2, F(x) = x is a valid solution to that functional equation, and that this solution is unique

To show uniqueness, suppose there exists another continuous function G(x) satisfying the same functional equation. We can demonstrate that F(x) = G(x) for all x in the dyadic rationals, and since the dyadic rationals are dense in [0,1], we conclude that F(x) = G(x) for all x in [0,1].

Indeed, we proceed by induction. First, we prove the base case: let D₀ = {0,1}. We have F(0) = G(0) = 0 and F(1) = G(1) = 1, so F(x) = G(x) for all dyadic rationals of rank 0. Now assume F = G on Dₙ, where Dₙ denotes the set of dyadic rationals of rank n, i.e., {0, 1/2ⁿ, 2/2ⁿ, 3/2ⁿ, …}.

Let’s now prove that F = G on Dₙ₊₁. Take x in Dₙ₊₁:

• if 0≤x≤0.5 , then x=m/2^(n+1) with m ≤ 2ⁿ. Therefore, 2x = m/2ⁿ, which belongs to Dₙ. By the induction hypothesis, F(2x) = G(2x), and since F(x) = pF(2x) = pG(2x) = G(x), we conclude that F = G on this interval.
• if 0.5≤x≤1 , then x is a dyadic rational of the form x = (2ⁿ + m)/2^(n+1) with m ≤ 2ⁿ. The same reasoning applies, and we again obtain F = G.

Therefore, F = G for all x in Dₙ₊₁.

Since the set of dyadic rationals is dense in [0,1], we can choose any sequence xₖ in the Dyadic rationals set such that the limit of xₖ is x. And then, continuity gives :

so when p=1/2, F(x)=x.

This means that when the game is fair and our initial fortune is x€ and our target is a€ , the probability to reach the target is x/a. It is the same result we’ve seen in the timid play in the previous article.

But that was when p=1/2. Can we guess a general expression for F(x)?

The thing is, it will be impossible to use the characteristic polynomial trick we saw in the last article, because this time we don’t have a linear recurrence… we need to use binary expansions.

Recall that the functional equation is:

Let’s denote d(x) as

(which is just a function that gives the fractional part of 2x). So now F(x) is either pF(d(x)) or p+qF(d(x)). We can show that d(x) is just the left shift of x, because:

Here, x₁ is either 0 or 1, and it will be the integer part of 2x. With a simple change of variables:

And we know that this sum is the fractional part of d(x), so:

the j-th digit of d(x) is xⱼ₊₁, i.e. d(x)ᵢ = xᵢ₊₁.

Great! Let’s continue to find that function F(x).

Let’s denote the outcome of game j as Iⱼ. it can be either 0 or 1. Also, let’s write x as:

where each xᵢ is a bit.

If x₁ is 0, this means that x < 0.5, you agree? So in that case we bet x, and if we lose (so if I = 0) then our fortune will be 0 (bankrupt), and if we win it will be 2x (so d(x)).

If x₁ is 1, this means that x > 0.5, so we bet 1−x, and if we lose (so if I = 0) then our fortune will be x−(1−x) = 2x−1 (so d(x)). And if we win it will be 1 (we reach the target).

In mathematical notation:

Now suppose after k games, we finally reach the target

This means that right before playing the k-th game, the first bit of our fortune was 1 and we won that game. So our fortune evolution was d(x) → d(d(x)) → d(d(d(x))) → … until 1 (every time we play, we shift our fortune bits to the left). We said that we won at game k, so before that, no first bit x₁ was equal to I (see formula above) (because otherwise we would have lost or reached the target before the k-th game).

We showed that if we reach the target after k games, then the k-th bit of x is 1 and all bits xⱼ before that are opposite to Iⱼ.

Now suppose that the k-th bit of x is 1, and we won the k-th game. This means that the fortune at the k-th game is greater than 0.5 so we reach the target at game k.

In conclusion, we reach the target after k games ⟺ we win the k-th game and the k-th bit of x is 1 and all previous bits are mismatched.

(for example, if x is equal to 0.2031, or equivalently 0.0011010…, we will reach the target at the 4th game if we win → win → lose → win.)

This will help us discover what the function F(x) is. Let’s continue…

We’ve just seen that to reach the target at step k we need:

We now define this random variable:

Ij is the outcome of game j

It also has a value between 0 and 1, and what is particular about this variable is that each of its bits is opposite to the sequence of game outcomes.

For example, if we win → win → lose → win → lose, the game outcomes are (I₁, I₂, I₃, I₄, I₅) = (1, 1, 0, 1, 0) and so W will be 0.00101… so the j-th bit of W is wⱼ = 1 − Iⱼ.

We showed previously that we reach the target after k games ⟺ we win the k-th game and the k-th bit of x is 1 and all previous bits are mismatched.

“The k-th bit of x is 1 and all previous bits are mismatched” can be reformulated as “the bits of W are the same as the bits of x except for the k-th bit,” and we know that xₖ is 1 and the k-th bit of W is 0… so that condition can be expressed as “W < x.”

So now we can write:

we reach the target ⟺ W<x.

The random variable W has a continuous distribution because ℙ(W = x) = 0 for any x ∈ [0,1] because :

Recall that

each Iⱼ is the outcome of game j (either 0 or 1).

For W to equal a specific value x ∈ [0,1], we would need:

-Each bit of W’s binary expansion to match the corresponding bit of x’s binary expansion

This means (1-Iⱼ) must equal the j-th bit of x for all j

So I₁ must equal 1-x₁, I₂ must equal 1 — x₂, etc…

Therefore, P(W = x) = P(I₁ = 1-x₁) · P(I₂ = 1-x₂) · … to infinity, and this equals 0. Hence, W has a continuous distribution.

F(x) = P(W ≤x); x ∈ [0;1]

We’re getting more and more information about F…

We have F(x) = Pr(reach 1 from x) = Pr(W < x) = Pr(W ≤ x), and we showed that Pr(W ≤ x) is continuous, so F(x) is also continuous.

We showed previously that we reach the target at game n if and only if:

• xₙ = 1 (the nth bit of x is 1)
• Iₙ = 1 (we win the nth game) with probability p
• For all j < n: Iⱼ ≠ xⱼ (all previous bits mismatch)

So the probability of reaching the target with an initial fortune of x is: Pr(reach the target at game 1) + Pr(reach the target at game 2) + Pr(reach the target at game 3) + etc…

This equals: Pr(win game 1) × Pr(first bit of x is 1) + Pr(win game 2) × Pr(x₁ mismatches I₁) × Pr(x₂ is 1) + Pr(win game 3) × Pr(x₁ and x₂ mismatch I₁ and I₂) × Pr(3rd bit of x is 1) + …

that is: F(x) = p·x₁ + p·Pr(x₁ mismatches I₁)·x₂ + p·Pr(x₁ and x₂ mismatch I₁ and I₂)·x₃ + …+p·Pr(first n−1 games mismatch x₁,…,xₙ₋₁).xₙ

Now what is Pr(first n−1 games mismatch x₁,…,xₙ₋₁)? It is Pr(I₁ ≠ x₁) × Pr(I₂ ≠ x₂) × … × Pr(Iₙ₋₁ ≠ xₙ₋₁). And we know that Pr(Iⱼ ≠ xⱼ) = Pr(Iⱼ = 1)·Pr(xⱼ = 0) + Pr(Iⱼ = 0)·Pr(xⱼ = 1) = p·Pr(xⱼ = 0) + q·Pr(xⱼ = 1) (and this is either p or q), so we write:

we wan express it as :

where

we can write :

and so F(x) is :

wa can also write it like :

Finally we have an expression of F !! and as you can see, it depends on each bit of x.

F is strictly increasing:

we saw that f is F(x) = P(W ≤x); x ∈ [0;1] , this mean that F(x) is non decreasing.

Let’s show that it is strictly increasing. To do this, we need to show that there are no intervals where F is flat. In other words, we need to show that there is no interval [a,b] where P(W ≤ x) is constant for all x in [a,b]. By definition, P(W ≤ x) is non-decreasing, so we need to show that there is no interval [a,b] where P(a < W ≤ b) = 0.

one must show that for every interval (x, y) ⊆ [0, 1]: ℙ(x < W ≤ y) > 0.

Consider a number in [0,1]. Its first n bits are: u₁u₂…uₙ.

We know that there are many other numbers having the same first n bits u₁u₂…uₙ. Let’s put all these numbers in a set I(u₁…uₙ). This is the set of all real numbers in [0,1] whose binary expansion starts with the specific pattern u₁u₂…uₙ. The smallest number in this set is obtained when all remaining digits are 0, and the largest number is obtained when all subsequent bits are 1, which equals the smallest number plus 1/2ⁿ.

Let’s denote A as the smallest number. Then the set I(u₁…uₙ) is the same as the interval:

This set is an interval because fixing the first n binary digits constrains the number to a specific range, and every number in that range can be achieved by choosing appropriate values for the remaining (infinitely many) binary digits.

Now let’s pick x and y in [0,1] such that x < y, and let’s take the midpoint: m = (x+y)/2. Let’s pick n large enough so that 1/2ⁿ < (y-x)/2. We know that the interval I(u₁…uₙ) has length 2⁻ⁿ (and let note u₁…uₙ as the first n bits of m).

so I(u₁…uₙ) contains m and its size is less than (y-x)/2 so

what about our random variable W ? we can say that it has more chance to be inside (x,y) than inside that interval I(u₁…uₙ)

so we can write:

and Pr(W ∈ I(u₁…uₙ)) is Pr(w₁=u₁) × Pr(w₂=u₂) × … × Pr(wₙ=uₙ). Recall that from the definition of W, each digit j is the opposite of the outcome of game j. Therefore, each Pr(wⱼ=uⱼ) is either p or q, so Pr(W ∈ I(u₁…uₙ)) > 0.

so F is strictly increasing on [0,1]

That’s good! this means that once again, the closer our initial fortune is to the target, the higher our chance of reaching the target (this holds for all strategies we’ve seen so far). Also, like before, reaching 920 from 900 gives us a better probability of reaching the target than reaching 120 from 100.

The graph of F for various values of p:

The graph of F for various values of p

Let’s compare our strategies from the first article with the strategy of this article. Let’s say our target is 120€, and p is 0.48 (like the probability of red in roulette).

with a target of 15€:

Bold Play seems to always be better than or equivalent to Timid Play. In the next part, we’ll see a better way to compare them and whether there are better ways to play to maximize the probability of reaching the target.