Удивительное рядом

[birdwatcher]

Оказывается, если у вас есть кривая монета с вероятностью выпадения орла равной некоторому неизвестному p, с ее помощью можно эмулировать математически точную монету. А именно, надо подбросить ее два раза.

Если выпали орел и решка, считать это орлом;

Если выпали решка и орел, считать это решкой;

Если выпали два орла или две решки, начать сначала.

Comments

[vbvb.livejournal.com]

надо подбросить ее _минимум_ два раза.

[ge-m.livejournal.com]

Гениально. Надо бы для особо садистских интервью приберечь.

[vinopivets.livejournal.com]

Красотища какая. Ряд возьми, да и сойдись куда следует.

[(Anonymous)]

A zhachem rjad to ? (Hot' on i sojdetsja kuda nado). Werojatnost' orla-reshiki jawno ta zhe chto i reshki-orla, a ostal'noe normalizacija.

[dmpogo.livejournal.com]

A zhachem rjad to ? (Hot' on i sojdetsja kuda nado). Werojatnost' orla-reshiki jawno ta zhe chto i reshki-orla, a ostal'noe normalizacija.

[mi-b.livejournal.com]

я ее люблю на интервью давать, если человек говорит, что он в Монте Карло специалист

[birdwatcher.livejournal.com]

В смысле, чтобы он ее решал методом Монте-Карло?

[mi-b.livejournal.com]

нет, решение ожидается то, которое вы привели. просто это довольно стандарный трюк в Монте Карло. следующая задачка - сгенерировать точку, равномерно распределенную на трехмерной сфере S^3 в четырехмерном пространстве если есть генератор независимых чисел с равномерным ранспределением на отрезке

[green-fr.livejournal.com]

Чем-то напоминает другую задачку, про бикфордов шнур с неравномерным горением, который сгорает ровно за час, и который, чтобы отмерить ровно полчаса, надо было поджечь одновременно с двух концов :-)

[birdwatcher.livejournal.com]

Это сгенерировать вектор в R4 с независимыми гауссовыми координатами и отнормировать?

[mi-b.livejournal.com]

с гауссовым мы так сразу не можем - у нас есть равномерный генератор, по условию.

[birdwatcher.livejournal.com]

Tам столь же прекрасный способ, Box-Muller. Ну, допустимо ли не сообразить такую простую вещь на интервью.

[mi-b.livejournal.com]

ну, то, что вы предложили - довольно кривой и неэффективный способ ;)-

[birdwatcher.livejournal.com]

Это практично!!!

[birdwatcher.livejournal.com]

По сравнению с ratio of uniforms? Опять же, можно ли не знать его наизусть!

[mi-b.livejournal.com]

да, можно существенно быстрее

[mi-b.livejournal.com]

без всякого ratio of uniforms

[birdwatcher.livejournal.com]

Существенно быстрее 12 U[0.1] чисел на точку сферы? Сдаюсь!

[mi-b.livejournal.com]

откуда 12 получилось, не понял. есть простой способ с 4/(пи^2/32)=20 равномерных точек. Box-Muller, вроде, потребует меньше, около 10?

[birdwatcher.livejournal.com]

O, нашел у Вольфрама (http://mathworld.wolfram.com/HyperspherePointPicking.html). Очевидно! Очевидно!

[dmpogo.livejournal.com]

Не столько 'минимум' два раза, сколько бросать надо парами. Одним событием является два броска.

[dmpogo.livejournal.com]

Жаль, не дает ответа куда приделывать динамит :)

[birdwatcher.livejournal.com]

В этом вся суть. Иначе это была бы не математика, а физика.

[morfizm.livejournal.com]

Спасибо! Отличное решение.