Это старая версия документа!


Моделирование случайных явлений с помощью «бросания монетки»

Представьте себе, что у Вас есть только одна 5-рублевая монетка (ее можно подбрасывать много раз), а Вы хотите сымитировать (смоделировать) бросания игральной кости. Как это сделать? И как это сделать оптимально, чтобы число подбрасываний было минимальным?

А что делать, если кость «фальшивая», то есть некоторые ее грани выпадают чаще, чем другие?

Ответ на эти (и другие, гораздо более хитрые) вопросы содержится в статье Д. Кнут, Э. Яо. Сложность моделирования неравномерных распределений. Кибернетический сборник, Новая серия, Вып. 19, М. Мир, 1983, стр. 97-158. Предлагается ознакомиться с началом этой статьи – тем ее кусочком, который почти не требует специальных знаний – и решить несколько задач. Сборник есть в библиотеке, файл книги можно получить у руководителя.

Вот варианты заданий. упорядоченных по возрастанию сложности.

Задание 1.

Ознакомиться с первым параграфом статьи – «Предварительные примеры» до 2-го абзаца стр. 103 (дальше в этом разделе идет материал, требующий знаний общей теории вероятностей).

Отчетность

1. Обосновать 2 способа подсчета среднего числа подбрасываний монеты применительно к методам моделирования, изображенным на рис. 1 и 2.

2. Придумать методы битового моделирования для бросания «гнутой» монетки с вероятностями выпадения герба 1/3 и 1/5, а также для бросания пирамидки с вероятностями выпадения граней 1/4, 1/4, 1/3 и 1/6. Подсчитать в этих случаях среднее число подбрасываний монеты.

Баллы

1 курс – 50, 2 курс – 25.

Задание 2.

Разобраться в следующем (втором) разделе работы – «Моделирование дискретных случайных величин». Здесь уже требуется некоторая математическая культура.

Отчетность

1. Закрыть «дырки» в доказательствах и рассуждениях. Под «дырками» понимаются переходы, четкие обоснования которых опущены в тексте, и которые Вам сразу не очевидны. Например, проверить утверждение, что равенство (2.21) «верно также и для H(x)» (в тексте написано, что это «легко видеть»).

2. Построить оптимальный алгоритм моделирования бросания «фальшивой» монеты, которая выпадает гербом с вероятностью p, а решкой – 1-p.

Баллы

1 курс – 100, 2 курс – 50.

Задание 3.

Обобщить результаты 2-й главы на случай, когда у нас есть несколько правильных монет и мы подбрасываем их одновременно. Например, мы подбрасываем одновременно три монеты (снова много раз) и хотим промоделировать результаты бросания игральной кости, причем сделать это оптимально. Как это сделать? Конечно, образец для рассуждений содержится во втором разделе статьи, но обобщение производится не то, чтобы совершенно автоматически.

Отчетность

1. Провести доказательство аналогов Теоремы 2.1 и Следствия (стр. 112) для описанного случая.

Поскольку статья Кнута и Яо – это все-таки научная статья, а не кусок учебника, там могут оказаться не очень понятные рассуждения или результаты, приведенные как известные читателю. В этом случае не нужно стесняться спрашивать что-то у руководителя – я либо все поясню, либо отошлю к подходящему учебнику.

Баллы

1 курс – 150, 2 курс – 75.

Руководитель

Некруткин Владимир Викторович

research/prob_bit.1583782402.txt.gz · Последнее изменение: 2020/03/09 22:33 — nina
Наверх
CC Attribution-Noncommercial-Share Alike 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0