rng_58's blog

scott_wu's quiz
By rng_58, history, 8 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

»
8 years ago, # |
  Vote: I like it +44 Vote: I do not like it
My solution
→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +28 Vote: I do not like it
    Spoiler
    → Reply
»
8 years ago, # |
  Vote: I like it +21 Vote: I do not like it

https://www.quora.com/A-machine-outputs-random-real-numbers-between-0-and-1-until-their-sum-exceeds-1-How-many-numbers-will-it-need-to-generate-on-average/answer/Alon-Amit?srid=dE6P

→ Reply
»
8 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?

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

    f(0) = undefined behaviour :D

    → Reply
    • »
      »
      »
      8 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.

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

        Because the initial value of y isn't specified.

        → Reply
    • »
      »
      »
      8 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.

      → Reply
      • »
        »
        »
        »
        8 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

        → Reply
»
8 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

→ Reply
  • »
    »
    8 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.

    → Reply
»
8 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
→ Reply