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

[WildKOT]

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

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

[Sheogorath]

Если я правильно понял, то оккупантам требуется алгоритм, который позволит получать числа от 0 до 1, в том числе -- иррациональные. Мегамозгу нужно придумать способ, как эти числа при помощи монетки получать, а потом его реализовать 100 раз.

Так вот,

Если ММ придумает алгоритм, заключающийся в последовательном бросании монетки, то реализовать его 100 раз он его тоже сможет -- достаточно сперва сделать первый бросок для первого раза, потом первый бросок для второго раза, ..., потом первый бросок бросок для сотого раза, потом второй бросок для первого раза и т.д.

Теперь принципиальный алгоритм определения числа:
sum = 0
1. Подкидываем монетку. Если орел -- то sum += 0.5
2. Подкидываем монетку. Если орел -- то sum += 0.25
...
N. Подкидываем монетку. Если орел, то sum += (0.5)^N
...
Продолжаем до бесконечности, последовательность будет сходиться к некоторому числу, вполне, быть может, иррациональному.


Но можно решить и практически:

Закручиваем монетку щелчком по ней и ждем, пока она упадет. От времени в секундах, за которое она упала, отнимаем их целое количество -- полученное число и есть наша вероятность. Возникает сложность с определением 0 и 1, но если вдруг остаток получится нулевым, то тогда можно подкинуть монетку и принять решение.
Такое решение работает даже при условии, когда ММ смертен.

[Owen]

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

[Sheogorath]

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

За конечное число итераций, разумеется, все числа не получатся, но ММ-то бессмертен, так что может себе позволить одну бесконечную последовательность.
А как из одной бесконечной последовательности получить 100, я описал.

UPD. Хотя если бессмертие ММа понимать не как возможность получения бесконечной последовательности, а как возможность получения сколь угодно большой, но конечной, тогда да, не годится.

Сообщение было отредактировано Sheogorath: 6.7.2015, 16:57

[WildKOT]

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

[BuPTy03]

Примечательно, что условие задачи вообще никак не помогает ответить на вопрос

Может ли Мегамозг гарантированно освободиться, если он бессмертен.

Если он не на пожизненном, то по-любому сможет, в противном случае, подозреваю, что правильный алгоритм - это заточить монетку и с её помощью потихоньку выносить стену в штанах как Энди Дюфрейн )

[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