Разбор задачек с собеседований vol. 4 🍏

Сегодня у нас снова тервер, и снова мы будем бросать монетки 🪙 Задачка с интервью в 📱, давали ее причем на стажерско-джунскую позицию. Условие:

Имеется фальшивая монета с неизвестной вероятностью выпадения орла или решки. Как из нее получить честную монету (p = 0.5 на каждый исход)?

➡️ Что такое нечестная монетка?

Любая монетка = орел выпадает с какой-то вероятностью p, решка с 1 - p. Для честной монетки p=0.5, для нечестной - p≠0.5. В общем-то, и все 🦅


➡️ Что мы вообще можем делать?

Единственное, что мы можем делать, - как-то бросать нечестную монетку, получая значение с перекосом от 0.5, а потом пытаться этот перекос как-то скорректировать.


➡️ Главная проблема - p неизвестна

Базово мы не знаем, в какую сторону корректировать обозначенный выше перекос и на какую величину. Нужен трюк, который сработает для любого p, при этом само p знать не требуется ☺️


➡️ Идея: ищем симметрию

Нам нужно найти какую-то комбинацию, когда исходы равновероятны, вне зависимости от p. Все остальные "неудобные" исходы мы будем выкидывать 🗑 Если мы бросаем монетку один раз - такое невозможно:
• О → p
• Р → (1 − p)

Попробуем бросать дважды. Возможны 4 исхода:
• ОО → p²
• РР → (1 − p)²
• ОР → p · (1 − p)
• РО → (1 − p) · p

Смотрим внимательно на ОР и РО. Их вероятности равны при любом p! В таком случае мы можем закодить алгоритм следующим образом:
• ОР → выдаём 0
• РО → выдаём 1
• ОО или РР → выбрасываем и бросаем пару заново


➡️ Кодим!


def fair_coin():
while True:
a, b = biased(), biased() ## дважды бросили монетку
if a != b: ## пара "разная"
return a ## 0 или 1, каждое с вероятностью 1/2


❗️Мы нигде в коде не используем значение p. За честность отвечает не знание перекоса, а симметрия двух "смешанных" исходов.

На самом деле очень похоже на то, что было у нас тут. Имхо, даже чуть попроще в понимании 🥰 Мы тоже исключаем неудобные исходы, но теперь не просто оставляем "удобные", а оставляем "удобные" + симметричные по вероятности.


➡️ Есть ли риск, что алгоритм не завершится?

Нет, если 0 < p < 1. Формально пара ОО/РР может выпадать сколь угодно долго, но вероятность этого
• Единица, если p=0 или p=1
• Стремится к нулю во всех остальных случаях

Чем кривее монетка, тем больше понадобится бросков:
• При p = 0.1 это ~11 бросков
• При p = 0.01 это ~101 бросок

Но в конце концов мы все равно достигнем результата.


➡️ Откуда тут берется количество бросков?

Удобно считать попыткой не отдельный бросок, а пару бросков. Одна попытка либо "срабатывает" (когда выпало OP/PO), либо "проваливается" (когда выпало ОО/РP). Вероятность, что пара сработает:

q = P(ОР) + P(РО) = p(1 − p) + (1 − p)p = 2p(1 − p)

Если каждая попытка независимо успешна с вероятностью q, то среднее число попыток до первого успеха = 1/q.

Докажем это. Обозначим E = искомое матожидание числа попыток (не бросков! бросков в два раза больше). Делаем первую попытку, и дальше два варианта:

• с вероятностью q она сразу удалась (потратили 1 попытку);
• с вероятностью (1-q) провалилась (потратили 1 попытку и оказались ровно в том же положении, что и в начале, то есть впереди еще в среднем E попыток).

E = q · 1 + (1 − q) · (1 + E)
E = q + (1 − q) + (1 − q)E
E = 1 + (1 − q)E
E − (1 − q)E = 1
qE = 1
E = 1/q

Получается, что матожидание количества попыток = 1/q = 1/[2p(1-p)]. А бросков = 2 · 1/[2p(1-p)] = 1/[p(1-p)]

Отсюда если p=0.1, то бросков будет 1/[0.1 · 0.9] = 11.11 😉

————
Давайте в этот раз проголосуем реакциями ❤️

❤️ - побольше задачек на SQL
🔥 - Python!!
👍 - еще тервера 💪

————
Зацените также предыдущие посты!
• Разбор задачек с собеседований vol. 1
• Разбор задачек с собеседований vol. 2
• Разбор задачек с собеседований vol. 3