Новый взгляд на гарантированное решение, Мегамозг, монеты и вероятность Опции

[WildKOT]

Подлые оккупанты посадили Мегамозга в тюрьму.
Стражники этой тюрьмы очень любили играть в игру, в которой были события, возникающей с разной вероятностью (от 0 до 1). Проблема в том, что эти вероятности могли быть любыми, даже иррациональными. Оккупанты использовали кубик, чтобы округлять вероятности, но это портило игру.
Тогда оккупанты решили заглянуть к Мегамозгу, дали ему монету и предложили придумать алгоритм бросания монеты для определения результата события в игре. После этого Мегамозг должен этот алгоритм реализовать 100 раз.
Может ли Мегамозг гарантированно освободиться, если он бессмертен.

Задача здесь на открытом обсуждении.
Особенно поощряется обсуждение понятия гарантированности.
Решение задачи я знаю, но с оговоркой на значение данного термина.

[WildKOT]

1) Решение, при котором Мегамозг освободиться за бесконечное время не годится, так как это равносильно тому, что он не освободится.
2) Цель Мегамозга не в том, чтобы монетками набросать число от 0 до 1, а в том, чтобы сгенерировать событие, которое произойдет с заданной вероятностью.
3) Доп. условие Арифметические операции с числами (сложение, умножение) Мегамозг может выполнить за разумное конечное время
Подсказка: при правильном алгоритме Мегамозг справится быстро и сможет практически наверняка освободиться в течении суток

[Sheogorath]

сгенерировать событие, которое произойдет с заданной вероятностью.

Я не понял(
То есть, ММу изначально дано некое заданное значение вероятности (число), а он посредством монетки должен сгенерировать событие, вероятность которого есть это число?

[WildKOT]

Я не понял(
То есть, ММу изначально дано некое заданное значение вероятности (число), а он посредством монетки должен сгенерировать событие, вероятность которого есть это число?

Да. Например если вероятность 0.75 - то он может бросить монетку 2 раза, и в качестве события выбрать то, что орел не выпадет ни разу.

[Breghnev]

Да. Например если вероятность 0.75 - то он может бросить монетку 2 раза, и в качестве события выбрать то, что орел не выпадет ни разу.

Если я не сошел с ума, то вероятность того, что орел не выпадет ни разу, равна вероятности того, что дважды выпадет решка, и это 0.5*0.5=0.25. Если же нам нужно получить 0.75, то нам нужно выбрать событие "орел выпадет хотя бы раз" (то есть событие противоположное событию "решка выпадет дважды") или что-то в этом духе.

Сообщение было отредактировано Breghnev: 4.8.2015, 22:09

[WildKOT]

Если я не сошел с ума, то вероятность того, что орел не выпадет ни разу, равна вероятности того, что дважды выпадет решка, и это 0.5*0.5=0.25. Если же нам нужно получить 0.75, то нам нужно выбрать событие "орел выпадет хотя бы раз" (то есть событие противоположное событию "решка выпадет дважды") или что-то в этом духе.

Верно. У меня была ошибка.
А вот если вероятность 1/3, все намного интереснее.

[Лиходей]

Значит необходимо генерацию случайного числа продолжать не до бесконечности, а только до тех пор, пока это необходимо. Понятно, что для заковыристых вероятностей это может продолжаться долго, но время вроде как сходится к конечной величине, а не к бесконечности.

Принцип:
Изначально вероятность находится в рамках от 0 до 1. При "удачном" броске монетки нижняя граница вероятности идёт вверх, сокращая диапазон вероятности вдвое. При неудачном - аналогично верхняя граница вниз.
Если искомая вероятность находится в диапазоне, продолжаем кидать монетку, уменьшая диапазон.
Если искомая вероятность ниже, значит событие не произошло, выше - произошло (или наоборот, там в программе похоже две ошибки, компенсирующие друг друга).

Программка на Python:

CODE

from random import random

def flip_coin():
    return random() > 0.5

def calc(prob):
    flip_count = 0
    prob_start = 0.
    prob_end = 1.
    while True:
        if prob<=prob_start:
            return [False, flip_count]
        elif prob>=prob_end:
            return [True, flip_count]
        flip_count += 1
        if flip_coin():
            prob_start += (prob_end-prob_start)/2
        else:
            prob_end -= (prob_end-prob_start)/2

def test(prob, iterations = 10**6):
    sucess = 0
    for _ in xrange(iterations):
        if calc(prob)[0]:
            sucess += 1
    print "Expected: %f, resulting: %f" % (prob, float(sucess)/iterations)

def test2(prob, iterations = 10**6):
    sucess = 0
    flip_count = 0
    for _ in xrange(iterations):
        flip = calc(prob)
        if flip[0]:
            sucess += 1
        flip_count += flip[1]
    print "Expected: %f; resulting: %f; flips: %f per prob" % \
          (prob, float(sucess)/iterations, float(flip_count)/iterations)
    
test2(0, 10**7)
test2(1, 10**7)
test2(0.5, 10**7)
test2(0.75, 10**7)
test2(0.125, 10**7)
test2(0.125+0.000001, 10**7)
test2(0.125-0.000001, 10**7)

Результаты симуляции (10М тестов):
требуемая вероятность; полученная вероятность; в среднем брошено монет для получения одной вероятности
Expected: 0.000000; resulting: 0.000000; flips: 0.000000 per prob
Expected: 1.000000; resulting: 1.000000; flips: 0.000000 per prob
Expected: 0.500000; resulting: 0.499721; flips: 1.000000 per prob
Expected: 0.750000; resulting: 0.749866; flips: 1.500128 per prob
Expected: 0.125000; resulting: 0.125103; flips: 1.749930 per prob
Expected: 0.125001; resulting: 0.124900; flips: 2.000272 per prob
Expected: 0.124999; resulting: 0.124988; flips: 2.000092 per prob
Expected: 0.062500; resulting: 0.062517; flips: 1.875052 per prob
Expected: 0.062501; resulting: 0.062611; flips: 2.000211 per prob
Expected: 0.062499; resulting: 0.062519; flips: 2.000323 per prob

Expected: 0.333333; resulting: 0.333207; flips: 2.000563 per prob
Expected: 0.333343; resulting: 0.333406; flips: 1.999871 per prob
Expected: 0.333323; resulting: 0.333547; flips: 2.000427 per prob
Expected: 0.166667; resulting: 0.166593; flips: 1.999216 per prob
Expected: 0.166677; resulting: 0.166559; flips: 2.000446 per prob
Expected: 0.166657; resulting: 0.166683; flips: 1.999807 per prob


Сообщение было отредактировано Лиходей: 25.11.2015, 18:24