0 sats \ 1 reply \ @south_korea_ln OP 8 Oct \ on: [Daily puzzle] Probability of ending at 1 science
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.
  1. Start with the decimal fraction 0.625 in base 10.
  2. Multiply by 2 (two comes from the binary):
  • 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.
  1. Take the fractional part 0.25 and multiply it again by 2:
  • The integer part is 0 (second binary digit)
  • Fractional part is 0.5, to be used again in next step
  1. Multiply by 2:
  • 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$...
write
preview
0 sats \ 0 replies \ @south_korea_ln OP 8 Oct
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.
  1. 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$.
  1. 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:
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}$.
reply