Участник:Олеся Кузнецова/Задача random bit generator — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Новая страница: «<latex> Задача: Имеется генератор случайных битов, который выдаёт 0 или 1 с вероятностью $\frac{…»)
 
 
Строка 1: Строка 1:
 
<latex>
 
<latex>
Задача:
 
 
Имеется генератор случайных битов, который выдаёт 0 или 1 с вероятностью $\frac{1}{2}$. Предложите алгоритм,
 
Имеется генератор случайных битов, который выдаёт 0 или 1 с вероятностью $\frac{1}{2}$. Предложите алгоритм,
 
который, используя данный генератор, возвращает 0 с вероятностью $\frac{1}{3}$ и 1 c вероятностью $\frac{2}{3}$. Оцените
 
который, используя данный генератор, возвращает 0 с вероятностью $\frac{1}{3}$ и 1 c вероятностью $\frac{2}{3}$. Оцените
Строка 7: Строка 6:
 
на выходе).
 
на выходе).
  
Ее решение:
+
</latex>
Алгоритм следующий: генерируем последовательность из трех бит до тех пор, пока не получится 000, 001 или 011. Если получилось 000,
+
возвращаем 0, если 001 или 011 - 1. Вероятность получить 0, таким образом, равна
+
$$
+
P(0)=\frac{1}{8}+\frac{5}{8} \cdot \frac{1}{8}+\left(\frac{5}{8}\right)^{2} \cdot \frac{1}{8}+\cdots=\frac{1}{8} \cdot \sum_{k=0}^{\infty}\left(\frac{5}{8}\right)^{k}=\frac{1}{8} \cdot \frac{1}{1-\frac{5}{8}}=\frac{1}{3}
+
$$
+
  
Посчитаем матожидание числа битов $\mathbb{E}(Z)$, которые нужно сгенерировать,чтобы остановиться. Обозначим $p_1=1$, если за три первых бита все получилось, и $p_1 = 0$ иначе (все получается, как можно заметить, в трех случаях извосьми). Тогда
+
[[Категория:Предложенные студентами задачи]]
$$
+
\mathbb{E} Z=\frac{3}{8} \mathbb{E}\left(Z | p_{1}=1\right)+\frac{5}{8} \mathbb{E}\left(Z | p_{1}=0\right)
+
$$
+
Если нас постигла неудача, нужно сгенерировать еще 3 бита. Иначе работа алгоритма заканчивается:
+
$$
+
\mathbb{E}\left(Z | p_{1}=0\right)=3+\mathbb{E} Z, \mathbb{E}\left(Z | p_{1}=1\right)=3
+
$$
+
Разрешаем полученную систему с тремя неизвестными:
+
$$
+
\begin{array}{c}{\mathbb{E} Z=\frac{3}{8} \cdot 3+\frac{5}{8}(3+\mathbb{E} Z)} \\ {\mathbb{E} Z=\frac{9}{8}+\frac{15}{8}+\frac{5}{8} \mathbb{E} Z}\end{array}
+
$$
+
Итого получаем, что в среднем придется сгенерировать 8 бит. В худшем случае, разумеется, бесконечное их число.
+
 
+
</latex>
+
  
 
[[Категория:Предложенные студентами задачи]]
 
[[Категория:Предложенные студентами задачи]]

Текущая версия на 20:27, 15 мая 2019