| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
Очередная задача по теории вероятностей.
Рассмотрим единичную сферу в n-мерном пространстве: 
. Выберем на ней точку (x1, x2, ..., xn) равномерно. Какое (с точностью до мультипликативной константы) математическое ожидание случайной величины 
?
Ответы (если, конечно, таковые будут) просьба аргументировать.
Слушай, крутая задача! Сижу в центре города на остановке, накорябал чего-то на салфетке. Понял, что не хватает математического аппарата, чтобы проинтегрировать уже для n = 3 из-за равномерного распределения точек. Плюнул, достал девайс, решил быстренько написать Монте-Карло, чтобы посмотреть на ответ, и понял, что случайно генерировать точку на сфере я тоже не умею :-)
UPD: А, генерировать уже научился, тааак, я начинаю видеть свет решения в конце туннеля...
Это не свет, это только мираж ;)
Что-то типа такого. Рассмотрим все возможные точки с x_1 больше, чем k/sqrt(n). Путём отбрасывания разных несущественных частей получаем что вероятность этого примерно e^{-k^2}. С другой строны очевидно, что матожидание не меньше 1/sqrt{n}. Поэтому бесполезно рассматривать k > sqrt (ln (n)). ну и получается, что в среднем число равно sqrt(ln(n)/n). 99% процентов скушано, но вроде я их проделал или, по крайней мере, прикинул.
Вроде все так, да.
Так, а требуется ответ в аналитической форме? Или асимптотика по n? Или что? Я умею предъявлять относительно легко считающийся численно интеграл, хоть на олимпиаду по программированию давай :-)
Имелась ввиду асимптотика ответа в аналитической форме с точностью до константы.
А какой интеграл, кстати?
Абсолютно прямолинейно вытекающий из условия. Говорим, что если взять вектор (x_1, x_2, ... x_n), в котором координаты распределены по гауссиане и отнормировать, то получится случайная точка на сфере (это следует из того, что e - x2e - y2 = e - x2 - y2, значит вероятность попадания в определённую точку пространства до нормировки зависит только от расстояния до неё, а значит все лучи равновероятны и после нормировки все точки на сфере тоже будут равновероятны).
А дальше выписываем ответ. Умею это делать в двух видах — совсем явно так:
С кучей нормировочных коэффициентов сзади из всех гауссиан (для простоты я взял распределение f(x) = e - x2) и из площади поверхности этой (n-1)-мерной сферы. Просто взяли и выписали для каждой точки пространства, какой вклад она даёт в матожидание.
Можно убить максимум следующим образом:
Сказав, что в силу симметрии можно принудительно взять x1 больше всех остальных.
Есть одна проблема. Ни один из таких интегралов не возьмётся аналитически :-) Во всяком случае мною в ближайшие пару лет.
А почему вам кажется, что этот интеграл легко считается численно?
Норма и максимум нормированного вроде бы независимы. Значит, считаем мат. ожидание максимума до нормирования, считаем ожидание нормы и делим.
Максимум до нормирования — это
, норма 
, что вроде бы есть примерно гамма-функция от 
, умноженная на константу от n, которая, кажется, считается.
Вот что делать с первым — не очень понятно.
Не очень понял, почему, если у нас две величины независимы, то матожидание отношения оказывается равным отношению матожиданий. Это же неправда?
В любом случае,
А с erf-ом более-менее можно работать.
Не совсем так. Если две величины (радиус и максимум нормированного) независимы, то мат. ожидание одной (максимума нормированного) есть мат. ождидание произведения (максимума исходного), деленное на мат. ожидание другой (радиуса).
А как можно хорошо посчитать ассимптотику erf вблизи нуля?
Maple, как ни странно, отказывается брать второй интеграл уже при n=3. Либо я неправильно делаю замену, либо одно из двух.
Вам не кажется, что Вы много выпендриваетесь?
В правках глупость, не стоит засорять ей сознание. Спасибо за комментарии нижеуказавших. :)
Вообще не понял перехода от второго абзаца к третьему. Точнее, не понимаю, откуда берётся цепочка равенств в третьем абзаце.
UPD: А ещё у вас вероятность с ростом размерности растёт, а она должна падать из некоторых соображений вида "чую, что это правда" и численно полученного мною ответа: (Метод Монте-Карло, поэтому точность небольшая, не более одного знака после запятой).
(Здесь под спойлером значения.)
UPD2: Да и вообще, для n = 1 у вас выходит 0.5, а на сфере в одномерном пространстве (которая две точки (1) и (-1) на вещественной прямой) у обеих точек модуль координаты — один.
Человек видимо не по сфере, а по шару распределял. И то как-то странно.
Да, спасибо, человек ступил. Рассматривался шар вместо сферы, ошибочно.
По поводу странности — тоже верно, по какому-то странному заблуждению на момент вычислений не совсем так думал о координатах, оттуда и вторая глупость.
Конкретное ответвление темы можно считать закрытым, еще раз спасибо за небольшой, но информативный комментарий :)
Ну так как равномерное распределение на шаре есть равномерное распределение на сфере * какое-то распределение на радиусах (вроде бы с плотностью x^{N+1}/(N+1)), то задачи для шара и сферы одна к другой сводятся. Но совершенно непонятно, будет ли на шаре что-то легче, чем на сфере.