rng_58's blog

By rng_58, history, 7 years ago, In English
x = 0;

while(x < 1){
    y = x;
    x += rand(); // returns a real number between 0 and 1, uniformly at random
}

What is the expected value of y?

It's not very hard, but the result is surprising.

  • Vote: I like it
  • +223
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +44 Vote: I do not like it
My solution
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +28 Vote: I do not like it
    Spoiler
»
7 years ago, # |
Rev. 6   Vote: I like it +108 Vote: I do not like it
My Solution

But I don't see why this is strange?

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +43 Vote: I do not like it

    f(0) = undefined behaviour :D

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Could you explain why? The way I see it f(0) = 0 is a perfectly fine statement to make.

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Because the initial value of y isn't specified.

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Nope, x is assigned to zero before the loop. Not sure if it was there 13 hours ago, though.

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +7 Vote: I do not like it

        But we are interested in value of y (not x) and code doesn't enter loop even once

»
7 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Suppose that we have N independent random variables X_i with a continuous uniform distribution on the interval [0, 1]. What is the expected value of min (abs (x_i-x_j))?

Ps. This is weakly related to the discussion, sorry

  • »
    »
    7 years ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it
    Answer

    It was posed on MSU contest on Petrozavodsk Winter 16. However proof is not easy, probably going through some integrals.

»
7 years ago, # |
  Vote: I like it +24 Vote: I do not like it

I searched answer by a randomize algorithm and I made distribution of each time's result of y.
I think the distribution of y is both surprising.

My approach


Distribution Graph