[Daily puzzle] Probability of ending at 1 \ stacker news ~science

pull down to refresh

[Daily puzzle] Probability of ending at 1

901 sats \ 27 comments \ @south_korea_ln 7 Oct 2024 science

Fair warning, this is probably a hard problem compared to other ones I have shared here before. Let's consider this a test to see if there is interest in such problems...

Consider a number $x$ between 0 and 1, and the following game:

At each step, define $d$ as:

 $d = \min(\text{dist}(x, 0), \text{dist}(x, 1))$

You then randomly move $x$ to the left or right by a distance $d$. After each move, update the value of $d$ accordingly, and continue until $x$ reaches either 0 or 1.

To clarify:

At each step, you have a 50% chance of moving $x$ to the nearest endpoint (either 0 or 1).
You also have a 50% chance of moving $x$ away from the nearest endpoint.

The question is: in terms of $x$, what is the probability that the game ends at 1?

I'll post a hint tomorrow in case I don't see any progress in a reasonable amount of time.

Previous iteration: #712599

view all related items

257 sats \ 8 replies \ @Scroogey 7 Oct 2024

Empirically, I'd guess the answer is x. E.g. for x=0.15, the probability is 0.15 (=15%).

201 sats \ 7 replies \ @Undisciplined 7 Oct 2024

I'm leaning towards this answer. It holds for 0.25, 0.5, and 0.75.

137 sats \ 3 replies \ @Scroogey 7 Oct 2024

https://glot.io/snippets/h0mtyotnt0

10 million random runs for some x between 0.0 and 1.0

    x=0.000 p=0.0000
    x=0.050 p=0.0499
    x=0.100 p=0.0999
    x=0.150 p=0.1499
    x=0.200 p=0.2001
    x=0.250 p=0.2500
    x=0.300 p=0.2999
    x=0.350 p=0.3499
    x=0.400 p=0.4000
    x=0.450 p=0.4501
    x=0.500 p=0.5001
    x=0.550 p=0.5501
    x=0.600 p=0.5999
    x=0.650 p=0.6498
    x=0.700 p=0.7001
    x=0.750 p=0.7498
    x=0.800 p=0.7999
    x=0.850 p=0.8500
    x=0.900 p=0.8998
    x=0.950 p=0.9501
    x=1.000 p=1.0000

1 sat \ 1 reply \ @south_korea_ln OP 7 Oct 2024

Careful there, Faketoshi might not be able to understand your code snippet there, using unsigned integers (I presume that's what they are, I am not proficient in cpp)~~

0 sats \ 0 replies \ @south_korea_ln OP 7 Oct 2024

c, not c++

1 sat \ 0 replies \ @south_korea_ln OP 7 Oct 2024

Well, that's one way of proving it :)

27 sats \ 2 replies \ @south_korea_ln OP 7 Oct 2024

Yes, it is $x$.

Now, can one prove it?

0 sats \ 1 reply \ @Undisciplined 7 Oct 2024

I'm sure someone can, but probably not me. I don't have any clever ideas for how to extend the case-based reasoning I was using and I certainly don't have time to do all the cases.

20 sats \ 0 replies \ @south_korea_ln OP 7 Oct 2024

Well, you correctly answered the initial question, so you did what was asked. I should have been clearer in asking for a formal proof.

236 sats \ 3 replies \ @SimpleStacker 7 Oct 2024

Let

f(x)

be the probability that the game ends on 1 when the current position is

x

We can easily verify that

f(0)=0

f(0.5)=0.5

and

f(1)=1

We also know that for

0 < x < 0.5

 $f(x) = 0.5 f(2x)$

And for

0.5 < x < 1

 $f(x) = 0.5 + 0.5f(2x-1)$

We'll assume that

f

is continuous and differentiable (and verify later).

We can therefore write that when

0 < x < 0.5

 $f^\prime(x) = f^\prime(2x)$

And when

0.5 < x < 1

 $f^\prime(x) = f^\prime(2x-1)$

These conditions can only be satisfied if

f^\prime(x)

is a constant. And with the boundary conditions of

f(0)=0

f(1)=1

, we obtain

 $f(x) = x$

(which is continuous and differentiable.)

19 sats \ 2 replies \ @south_korea_ln OP 8 Oct 2024

Great job!

21 sats \ 1 reply \ @SimpleStacker 8 Oct 2024

Thanks :)

Math was always my favorite subject, I was just too chicken to go for a phd in it

Not sure if the proof I gave is the proof you had in mind

0 sats \ 0 replies \ @Bell_curve 8 Oct 2024

You were smart for being chicken

133 sats \ 1 reply \ @0xbitcoiner 7 Oct 2024

I think it's best not to post puzzles that are too difficult! 😂

50% ?

66 sats \ 0 replies \ @south_korea_ln OP 7 Oct 2024

This one indeed will probably be a bit hard for a majority of stackers, but I've seen a select few with decent math skills who might appreciate the beauty of the solution I plan on sharing tomorrow.

PS: It's not 50%. Solution depends on $x$.

114 sats \ 1 reply \ @ek 7 Oct 2024

I really like these math puzzles! They are really refreshing. They also remind me of weekly university homework just without all the pressure haha

34 sats \ 0 replies \ @south_korea_ln OP 7 Oct 2024

Happy to hear that :)

0 sats \ 1 reply \ @south_korea_ln OP 8 Oct 2024

As a hint before I give the full answer when I have more time, an intuitive way to understand why the probability should be equal to $x$ is by representing our fraction in binary representation. You may be familiar with integers in binary representation, but fractions also exist in such representation.

Here the procedure to express a decimal in binary taking 0.625 as an example.

Start with the decimal fraction 0.625 in base 10.
Multiply by 2 (two comes from the binary):

 $0.625 \times 2 = 1.25$

The integer part is 1 (this is the first binary digit after the decimal point).
The fractional part is 0.25, which we carry to the next step.

Take the fractional part 0.25 and multiply it again by 2:

 $0.25 \times 2 = 0.5$

The integer part is 0 (second binary digit)
Fractional part is 0.5, to be used again in next step

Multiply by 2:

 $0.5 \times 2 = 1.0$

Integer part is 1 (third binary digit)
Fractional part is 0.0 and we can thus stop here as there no fraction to convert anymore.

The binary representation of $0.625_{10}$ is thus $0.101_2$.

Reasoning on $0.101_2$ is key in proving the probability being $x$...

0 sats \ 0 replies \ @south_korea_ln OP 8 Oct 2024

Now that we have the binary representation, it is not too hard.

Let's start with the general expression of the binary representation, and then apply it to our specific example above.

General expression:

 $x = 0.a_1a_2a_3\dots$

where $a_1,a_2,a_3,\dots$ are the binary digits of $x$ after the decimal point.

In binary representation, we can interpret the game as follows.

Look at $a_1$.

If a_1 = 1, you are closer to 1, and there's a 50% chance you'll immediately end up at 1.
If a_1 = 0, you are closer to 0, and there's a 50% chance you'll immediately end up at 0.
For each of the above cases, there's also a 50% chance you don't stop there and move to the next binary digit, $a_2$.

If the game continues to $a_2$, you repeat the process.

If a_2 = 1, there's a 50% chance you'll immediately end up at 1.
If a_2 = 0, there's a 50% chance you'll immediately end up at 0.
Again, with a 50% chance, the game can continue to $a_3$.

To calculate the final probability of ending at 1 is determined by the binary digits of $x$. Each step reveals the next binary digit, and the chance to continue to the next digit is always $1/2$.

Let's use this on $x=0.625$ which is $0.101_2$ in binary.

The first digit $a_1=1$ gives a $1/2$ chance to stop at 1 immediately
If the game continues, the second digit $a_2$ gives a 1/4 chance of stopping at 0
If it continues further, the third digit $a_3$ gives a 1/8 chance of stopping at 1.

Thus, the total probability of ending at $1$ for $x=0.625$ is:

 $P (\text{end at 1}) = \frac{1}{2} + \frac{1}{8} = \frac{5}{8} = 0.625.$

In conclusion, for any $x$ in $[0,1]$, the probability of ending at 1 is equal to the value of $x$ itself. This result can be formalized using the fact that the game essentially reads off the binary digits of $x$ and assigns weights based on powers of $\frac{1}{2}$.

0 sats \ 0 replies \ @south_korea_ln OP 7 Oct 2024

I'll post a proof tomorrow that the probability is indeed $x$, as already found by @Scroogey and @Undisciplined.

0 sats \ 2 replies \ @ek 7 Oct 2024

The question is: in terms of $x$, what is the probability that the game ends at 1?

When does the game end?

0 sats \ 1 reply \ @south_korea_ln OP 7 Oct 2024

If you are at 0 or 1.

Say your initial position is at $0.7$... You are closest to 1. So $d$ is $0.3$. You have a 50% chance of ending at $1$, 50% chance of ending at $0.4$. If the latter, repeat. If the former, the game ends. Repeat means here $d$ is 0.4 because closest to zero. 50% chance of ending at 0 (ending the game, but unsuccessfully), 50% chance of moving to 0.8. Repeat until you end at 0 or 1. The question is, what is the probability you end at 1.

0 sats \ 0 replies \ @south_korea_ln OP 7 Oct 2024

Note I edited my answer above just now. It was a bit confusing.

0 sats \ 2 replies \ @Undisciplined 7 Oct 2024

x is different each step, too?

23 sats \ 1 reply \ @south_korea_ln OP 7 Oct 2024

$x$ is the position at the beginning. That's the variable that defines the probability of ending the game at 1. Of course, each step the position will change, but that doesn't change the initial value of $x$.

0 sats \ 0 replies \ @Undisciplined 7 Oct 2024

Thanks

0 sats \ 0 replies \ @south_korea_ln OP 7 Oct 2024

Solution to yesterday's continued fraction problem: #713310