ML Mentor
Назад к подготовке
ВопросСредняяalgorithmsТехническое собеседование

Честная монетка из нечестной

Есть монетка с неизвестной вероятностью орла p, 0 < p < 1. Как получить честный случайный бит 0/1, используя броски этой нечестной монетки?

Ответить самому

Сначала сформулируйте ответ как на собеседовании, затем откройте разбор и оцените себя.

Загрузка

Короткий ответ

Бросаем монетку парами. HT и TH имеют одинаковую вероятность p(1-p), поэтому HT можно вернуть как 0, TH как 1, а HH и TT отбрасывать и повторять.

Полный разбор

Один бросок нечестной монетки не подходит: вероятность орла p неизвестна и не равна 1/2. Но две разные пары симметричны:

P(HT)=p(1−p),P(TH)=(1−p)p.P(HT) = p(1-p), \quad P(TH) = (1-p)p.

Эти вероятности равны при любом p. Поэтому алгоритм фон Неймана:

  1. Бросить монетку два раза.
  2. Если выпало HT, вернуть 0.
  3. Если выпало TH, вернуть 1.
  4. Если выпало HH или TT, отбросить пару и повторить.

Так результат 0 и 1 получается с одинаковой вероятностью. Условие 0 < p < 1 нужно, чтобы разные пары имели ненулевую вероятность и процедура могла завершиться.

Теория

Это Von Neumann extractor: он извлекает unbiased bit из biased independent coin flips за счет симметрии двух разных исходов.

Типичные ошибки

  • Пытаться корректировать p напрямую, хотя p неизвестна.
  • Использовать один бросок.
  • Не отбрасывать одинаковые пары HH и TT.

Как отвечать на собеседовании

  • Сразу сравни вероятности HT и TH.
  • Проговори, что одинаковые пары не дают честного выбора и поэтому повторяются.