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.
→ Обратите внимание
До соревнования
WorldQuant Round 1 (Codeforces Round 1128, Div. 1 + Div. 2)
3 дня
Зарегистрироваться »
WorldQuant Round 1 (Codeforces Round 1128, Div. 1 + Div. 2)
3 дня
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | jiangly | 3670 |
| 3 | Kevin114514 | 3657 |
| 4 | maroonrk | 3355 |
| 5 | Um_nik | 3353 |
| 6 | squareOf105 | 3346 |
| 7 | tourist | 3343 |
| 8 | strapple | 3324 |
| 9 | heuristica | 3322 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | AmShZ | 144 |
| 5 | Um_nik | 141 |
| 6 | Errichto | 139 |
| 7 | adamant | 137 |
| 8 | BledDest | 134 |
| 9 | maroonrk | 133 |
| 10 | qwexd | 130 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2026 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 14.10.2026 22:07:31 (g2).
Десктопная версия, переключиться на мобильную.
При поддержке
E(y) = Sum(n = 1 ~ inf) Integrate(x = [0, 1]) ((Probability that value is x in nth iteration, and >=1 in (n+1)th iteration)xdx)
Probability density function for x in 1th iteration is 1.0
pdf for x in 2nd iteration is x / 1! (integrate above in [0, x])
pdf for x in 3rd iteration is x^2 / 2! (integrate above in [0, x])
pdf for x in 4th iteration is x^3 / 3! (integrate above in [0, x])
pdf for x in nth iteration is x^(n-1) / (n-1)!
So, E(y) = Sum(n = 1 ~ inf) n(n+1) / (n+2)! . I don't know taylor expansion, but hopefully WolframAlpha knew that. So I found E(y) = e-2.
I also thought about it that way :). You can note that if we change order of summation (meaning, sum by n and integral by x) we get that result is an integral from 0 to 1 from exx2 what equals e-2
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
For some 0 ≤ t ≤ 1, let f(t) be the answer if the loop were while(x < t) instead of while(x < 1). Clearly, f(0) = 0
We can say that :
If we differentiate, then we get a differential equation f'(t) = t + f(t)
And the solution is f(t) = et - t - 1
So, f(1) = e - 2
But I don't see why this is strange?
f(0) = undefined behaviour :D
Could you explain why? The way I see it f(0) = 0 is a perfectly fine statement to make.
Because the initial value of y isn't specified.
Nope,
xis assigned to zero before the loop. Not sure if it was there 13 hours ago, though.But we are interested in value of y (not x) and code doesn't enter loop even once
Oh, right. I'm sorry.
Пусть имеем N независимых случайных величин X_i с непрерывным равномерным распределением на отрезке [0, 1]. Каково матожидание
min(abs(x_i-x_j))?ps. Это слабо связано с обсуждаемой темой, простите
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
It was posed on MSU contest on Petrozavodsk Winter 16. However proof is not easy, probably going through some integrals.
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.
I calculated 1,000,000 times in this code:
The link of my code is here.
My code counts the number of times every 0.01 period in range [0, 1).
I used random in 64-bit integer, but 64-bit integer has over 1018 numbers so I think this method is almost real-number random.
I expected the distribution graph draws ax2 graph, but it is little-bit different. I impressed about this.
The expected value of this experiment is about 0.71806197, and this is almost e - 2.