?

Log in

No account? Create an account
nyaload

Журнал Пушыстого

Журнал Пушыстого

Previous Entry Share Next Entry
1/3 СЧАСТЬЯ
nyaload
_winnie
Уже несколько раз встречаюсь с программисткой задачей по вероятности, как из букв Ж,О,П,А сложить слово СЧАСТЬЕ. Конкретно - как имея монету орёл/решка или "честный" rand от 0 до 32767 получить вероятность равную точно 1/3.

Тут есть хитрость - с одной стороны это невозможно, с другой стороны это очень просто. Хитрость заключается в том, что бы запретить или разрешить неограниченное время работы алгоритма. Замечу, что "неограниченное" не означает бесконечного зависания, а означает что может работать сколько угодно долго, но в конце концов завершится.

Вероятность 1/3 не получится, если количество бросков ограничено сверху. Так как все вероятностное пространство состояний алгоритма будет поделено на степени двойки (1/2, 1/4, ... 1/2^n), а из сумм степеней двойки получить 1/3 и счастье не выйдет.

Если избавится от ограничения сверху по количеству бросков, то из бесконечного числа степеней двойки можно сложить одну треть.

Наиболее тривиальный способ: бросать D4 из двух монет, получая числа от 1 до 4. Когда выпавшее число будет от 1 до 3, не 4 - то взять это как результат, одно из трёх равновероятных событий.

Несмотря на сколь угодно долгую работу алгоритма - на практике это будет довольно быстро, так как вероятность того что выпадают только орлы - уменьшается экспоненциально.

Есть ещё похожая задача - получить случайную точку внутри шара, без сгущений. Сразу замечу, что тривиально через полярные координаты не выйдет, на полюсах будет плотнее.

Самый простой способ - это цикл вида
do {
    //выбрать точку в кубе
    x = uniform_rand(-1, 1); 
    y = uniform_rand(-1, 1);
    z = uniform_rand(-1, 1);
while (x*x + y*y + z*z > 1);  //пока она не окажется внутри шара
Можно аналитически, но решение с циклом самое простое.


  • 1
Кажется мне, что псевдослучайное число вообще не может имитировать случайное событие для длинной последовательности экспериментов. Но допустим, функция настолько хороша, что достаточно равномерно выдаёт числа из всего доступного диапазона.
Но почему бы тогда не брать остаток от деления на 3? Это будет недостаточно равномерно?

Потому что в диапазоне [0, 2n), n > 1, чисел, дающих остаток 1 будет больше, чем чисел, дающих остаток 0.

> Но допустим, функция настолько хороша,
Угу, она может быть псевдослучайной хорошей, или браться из действительно случайного устройства (спец-генератор из теплового шума или движение мышкой пользователем).

>Но почему бы тогда не брать остаток от деления на 3?
32768 или 4294967296 вариантов, которые обычно берутся из стандартного rand, на три равные группы не делятся.

>Это будет недостаточно равномерно?
В разных задачах по разному. В игровых автоматах для казино погрешность в 1/32768 может быть и важна. Для каких-то численных экспериментов может быть важна и погрешность в 1/4294967296. Для казуальной не-онлайновой игрушки в "Дурака" такая тонкость может быть избыточна.

(Deleted comment)
>Сразу замечу, что тривиально через полярные координаты не выйдет...

А если не тривиально? Т.е. решать таки через полярные координаты и выбирать точку в кубе вместо шара, но брать не uniform_rand, а some_another_rand?

Про сферу я хорошо помню удивительный факт, что можно взять случайный z от -1 до 1 и случаный азимут, получим равномерное распределение на сфере.

Про шар с внутренность - не знаю, можно попробовать глянуть в гугл по "uniform distribution inside sphere". Я обычно использую цикл while на практике.

> равную точно 1/3

Как меня в своё время учили, ничего "точного" в нашем бренном мире не бывает, бывает только большие или меньшие величины погрешностей. ;)

На дискретных объектах нашей вселенной можно построить математику (например, собрать из атомов лист бумаги и мозг математика), внутри которой можно уже развернуться ;)

Метод с шаром - стандартный метод получения всяческих хитрых распределений в методе Монте-Карло для ядернофизических задач.

Так моделируется испускание частиц любого гладкого спектра (график спектра окружается квадратом, в котором делается равномерное распределение, если попали под график - ок, над - бросаем заново), распад нестабильного изотопа в произвольной точке произвольного тела.

Загадка: Почему, если вместо отсеивания точек, не попавших в сферу, делать нормализацию вектора, не получится равномерное распределение точек по поверхности шара (да, это другая задача)?

Нестрого, но тем не менее

Потому что из центра куба в направлении на угол видно больше точек, чем в направлении на центр грани. Поэтому на сфере точки будут тяготеть к проекциям рёбер, а вдоль этих проекций будут тяготеть к проекциям вершин.

Re: Нестрого, но тем не менее

Да, верно.

Получится же на сфере плотность, пропорциональная толщине куба по данному направлению?

Ну да. Одни далеко не глупые в общем и целом люди, делавшие трассировщик лучей, долго не могли понять источник странных артефактов освещения в тестовой сцене, как на зло - cornell box'е. То ли лучи для AO они по полусфере так раскидывали, как я писал, то ли что еще.

Все это
У последней задачи минимум еще два решения:
одно уже было в комментах: берем случайные z и долготу, по ним вычисляем x и y
z = uniform_rand(1,-1)
r = sqrt(1-z*z)
phi = uniform_rand(0, 2*Pi)
x = r * cos(phi)
y = r * sin(phi)

Проще всего доказывается через интегралы, но факт был известен еще Архимеду.

Вариант два: берется вектор из трех компонент с нормальным распределением и нормализуется
x = gaussian_rand()
y = gaussian_rand()
z = gaussian_rand()
inv_r = 1/sqrt(x*x + y*y + z*z)
x *= inv_r
y *= inv_r
z *= inv_r

метод работает и для n-мерных шаров.

ЗЫ: Алгоритмы которые всегда выдают верный ответ, но требуют случайного времени называются Лас-Вегасскими: http://en.wikipedia.org/wiki/Las_Vegas_algorithm

  • 1