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.
→ Обратите внимание
До соревнования
Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
17:12:23
Зарегистрироваться »
Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
17:12:23
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 155 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | djm03178 | 152 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 30.11.2024 00:22:38 (k2).
Десктопная версия, переключиться на мобильную.
При поддержке
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.