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:
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
Empirically, I'd guess the answer is x. E.g. for x=0.15, the probability is 0.15 (=15%).
I'm leaning towards this answer. It holds for 0.25, 0.5, and 0.75.
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.0000Careful 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)~~
c, not c++
Well, that's one way of proving it :)
Yes, it is $x$.
Now, can one prove it?
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.
Well, you correctly answered the initial question, so you did what was asked. I should have been clearer in asking for a formal proof.
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,
And for 0.5<x<1,
We'll assume that f is continuous and differentiable (and verify later).
We can therefore write that when 0<x<0.5,
And when 0.5<x<1,
These conditions can only be satisfied if fā²(x) is a constant. And with the boundary conditions of f(0)=0, f(1)=1, we obtain
(which is continuous and differentiable.)
Great job!
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
You were smart for being chicken
I think it's best not to post puzzles that are too difficult! š
50% ?
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$.
I really like these math puzzles! They are really refreshing. They also remind me of weekly university homework just without all the pressure haha
Happy to hear that :)
x is different each step, too?
$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$.
Thanks
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.
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$...
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:
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.
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.
Thus, the total probability of ending at $1$ for $x=0.625$ is:
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}$.
I'll post a proof tomorrow that the probability is indeed $x$, as already found by @Scroogey and @Undisciplined.
When does the game end?
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.
Note I edited my answer above just now. It was a bit confusing.
Solution to yesterday's continued fraction problem: #713310