Как с помошью подбрасывания монетки равновероятно выбрать один из трёх вариантов?

Здравствуйте, WinterMute, Вы писали:

WM>Как с помошью подбрасывания монетки равновероятно выбрать один из трёх вариантов?
Это тут уже было.
Например, кидаешь два раза. ОО, ОР и РО -- это искомые три варианта, а РР -- пересброс. И так пока не повезёт...

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, WinterMute, Вы писали:

WM>>Как с помошью подбрасывания монетки равновероятно выбрать один из трёх вариантов?
E>Это тут уже было.
E>Например, кидаешь два раза. ОО, ОР и РО -- это искомые три варианта, а РР -- пересброс. И так пока не повезёт...

А за гарантированное количество подбрасываний?

Здравствуйте, deniok, Вы писали:

D>А за гарантированное количество подбрасываний?
Зачем? Матожидание конечно и даже невелико...

WM>>>Как с помошью подбрасывания монетки равновероятно выбрать один из трёх вариантов?
E>>Это тут уже было.
E>>Например, кидаешь два раза. ОО, ОР и РО -- это искомые три варианта, а РР -- пересброс. И так пока не повезёт...

D>А за гарантированное количество подбрасываний?

Это я сам пока не знаю. Давайте так: (*) за гарантированное количество подбрасываний, или доказать что это невозмжно.

WM>>Как с помошью подбрасывания монетки равновероятно выбрать один из трёх вариантов?
E>Это тут уже было.
E>Например, кидаешь два раза. ОО, ОР и РО -- это искомые три варианта, а РР -- пересброс. И так пока не повезёт...

Ёпт, а я её вчера придумал в курилке

Здравствуйте, WinterMute, Вы писали:

WM>Это я сам пока не знаю. Давайте так: (*) за гарантированное количество подбрасываний, или доказать что это невозмжно.
А что тут доказывать?

У тебя вроде бы всего один произвол есть. Бросать монетку или не бросать.
Ну пусть у тебя есть какой-то алгорим, который не более чем за N бросков останавливается и выдаёт "синий" "красный" или "жёлтый" в зависимости от того, как падала монетка.

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

получим 2**N равновероятных исходов. Каждый из которых приводит к одному из трёх якобы равновероятных выборов. Но таки 2**N на 3 нифига не делится...

Здравствуйте, Erop, Вы писали:

E>... получим 2**N равновероятных исходов. Каждый из которых приводит к одному из трёх якобы равновероятных выборов. Но таки 2**N на 3 нифига не делится...

А если, например, так:

Пусть орёл соответстует единице, решка -- нулю. Кидаем два раза монетку, и суммируем результат.
На этом этапе результат прямо соответствует выбору. т.е.:
0:0, 1:1, 2:0

Теперь повторяем опыт ещё два раза, но соответствие результата выбору такое:
0:1, 1:2, 2:0
0:2, 1:0, 2:1

Теперь суммируем выборы во всех трёх случаях и делим на 3.

Здравствуйте, WinterMute, Вы писали:

WM>Теперь суммируем выборы во всех трёх случаях и делим на 3.
Не понял. Во всех трёх сериях пусть выпала сумма 2. Какой из трёх исходов берём?

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, WinterMute, Вы писали:

WM>>Теперь суммируем выборы во всех трёх случаях и делим на 3.
E>Не понял. Во всех трёх сериях пусть выпала сумма 2. Какой из трёх исходов берём?

сумма исходов -- число от 0 до 5, соотсветственно:
0,1 : 0
2,3 : 1
4,5 : 2

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, WinterMute, Вы писали:

WM>>Теперь суммируем выборы во всех трёх случаях и делим на 3.
E>Не понял. Во всех трёх сериях пусть выпала сумма 2. Какой из трёх исходов берём?

да, не работает, получается 7 вариантов. Надо подумать ещё.
Что касается твоего доказательства невозможности, оно не кажется мне полностью убедительным.

WM>да, не работает, получается 7 вариантов. Надо подумать ещё.

я вот подумал, а если исходы заксорить?

Здравствуйте, WinterMute, Вы писали:

WM>Что касается твоего доказательства невозможности, оно не кажется мне полностью убедительным.

Если бросать монетку N раз, получится 2^N вариантов. Каждому из них нужно поставить в соответствие один из трех выборов. Как ты собираешься это делать?

Здравствуйте, WinterMute, Вы писали:

WM>Здравствуйте, Erop, Вы писали:

E>>Здравствуйте, WinterMute, Вы писали:

WM>>>Теперь суммируем выборы во всех трёх случаях и делим на 3.
E>>Не понял. Во всех трёх сериях пусть выпала сумма 2. Какой из трёх исходов берём?

WM>сумма исходов -- число от 0 до 5, соотсветственно:
WM>0,1 : 0
WM>2,3 : 1
WM>4,5 : 2

До 6. Распределение первого опыта — (0: 1/4, 1: 1/2, 2: 1/4), второго и третьего — (0: 1/4, 1: 1/4, 2: 1/2), (0: 1/2, 1: 1/4, 2: 1/4). Распределение суммы: (0: 1/32, 1: 7/64, 2: 7/32, 3: 9/32, 4: 7/32, 5: 7/64, 6: 1/32). Все дроби — двоично-рациональные, тройке в знаменателе взяться принципиально неоткуда. 1/3 в двоичной системе — 0.(01), бесконечная периодическая дробь.

WM>я вот подумал, а если исходы заксорить?

Кажется получилось, вышеупомянутый XOR, разумеется троичный. Вот исходники, на которых проверял:

// prob_test.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdlib.h>
#include <stdio.h>
#include <time.h>


int choose_1or0()
{
    return rand() <= RAND_MAX/2 ? 0 : 1;
}

int get_choice()
{
    return choose_1or0() + choose_1or0();
}

int shift_choice( int choice, int shift )
{
    int new_choice = choice + shift;
    return new_choice < 3 ? new_choice : new_choice - 3;
}

int xor3( int a, int b )
{
    int c = a + b;
    return c < 3 ? c : c-3;
}

int xor3( int a, int b, int c )
{
    return xor3( xor3(a,b), c );
}

int _tmain(int argc, _TCHAR* argv[])
{
    srand( (unsigned)time( NULL ) );

    const int prob_num = 30000;
    int choices[3] = {0,0,0};

    for( int i = 0; i < prob_num; i++ )
    {
        int c0 = shift_choice( get_choice(), 0 );
        int c1 = shift_choice( get_choice(), 1 );
        int c2 = shift_choice( get_choice(), 2 );

        int c = xor3( c0, c1, c2 );

        if( c < 0 || c > 2 )
        {
            int g = 0;
        }

        choices[c]++;
    }

    printf( "\nc0=%d, \nc1=%d, \nc2=%d", choices[0], choices[1], choices[2] );

    return 0;
}

Здравствуйте, Roman Odaisky, Вы писали:

RO>Здравствуйте, WinterMute, Вы писали:

WM>>Что касается твоего доказательства невозможности, оно не кажется мне полностью убедительным.

RO>Если бросать монетку N раз, получится 2^N вариантов. Каждому из них нужно поставить в соответствие один из трех выборов. Как ты собираешься это делать?

Семь альтернатив можно выбрать. Почему тогда нельзя три?

KK>Семь альтернатив можно выбрать. Почему тогда нельзя три?

Да вот можно, только на последнем шаге нужно не складывать альтернативы, как я это сначала сделал, а ксорить по модулю 3. Несколькими постами выше есть исходники, которые демонстрируют что такой подход работает. Там, правда, есть небольшое смещение выбора к первому варианту, но мне кажется это издержки работы рандомайзера, иначе это объснить не получается.

Я обобщил подход WinterMute здесь

Автор: WinterMute
Дата: 24.05.08

и получил следующее решение.

Нужно решить уравнение (N*(N-1)+1)%3=0. Недолгим перебором получаем одно из решений N=5. Далее приведена сама процедура выбора.
Допустим 0 — решка, 1 — орел. На каждом из шагов кидаем монету четыре раза. Для кажой комбинации выбираем значение для соответствующего шага из таблицы.

Шаг 1: 0000 -> 0 | 0001 -> 1 | 0010 -> 2 | 0011 -> 3 |  0100...1111 -> 4
-----------------------------------------------------------------
Шаг 2: 0000 -> 4 | 0001 -> 0 | 0010 -> 1 | 0011 -> 2 |  0100...1111 -> 3
-----------------------------------------------------------------
Шаг 3: 0000 -> 3 | 0001 -> 4 | 0010 -> 0 | 0011 -> 1 |  0100...1111 -> 2
-----------------------------------------------------------------
Шаг 4: 0000 -> 2 | 0001 -> 3 | 0010 -> 4 | 0011 -> 0 |  0100...1111 -> 1
-----------------------------------------------------------------
Шаг 5: 0000 -> 1 | 0001 -> 2 | 0010 -> 3 | 0011 -> 4 |  0100...1111 -> 0

Суммируем значения, полученые, на каждом шаге. Получаем число из интервала [0..20]. Т.е. двадцать одно возможное значение. Двадцать один делится на три без остатка.

Здравствуйте, WinterMute, Вы писали:

WM>>я вот подумал, а если исходы заксорить?

WM>Кажется получилось, вышеупомянутый XOR, разумеется троичный. Вот исходники, на которых проверял:

Чушь!
Чем считать по rnd лучше вот что сделай.

Я так понимаю, у тебя монету кидают 9 раз?
Это всего 512 разных вариантов
Вот и напиши программу, которая подсчитает сколько каких комбинаций бит приходится на какой исход. Если у тебя хорошая программа, то на два исхода прийдётся 171 комбинация, а на один, увы, только 170...

Здравствуйте, Ka3a4oK, Вы писали:


KK>

KK>Шаг 1: 0000 -> 0 | 0001 -> 1 | 0010 -> 2 | 0011 -> 3 |  0100...1111 -> 4
KK>-----------------------------------------------------------------
KK>Шаг 2: 0000 -> 4 | 0001 -> 0 | 0010 -> 1 | 0011 -> 2 |  0100...1111 -> 3
KK>-----------------------------------------------------------------
KK>Шаг 3: 0000 -> 3 | 0001 -> 4 | 0010 -> 0 | 0011 -> 1 |  0100...1111 -> 2
KK>-----------------------------------------------------------------
KK>Шаг 4: 0000 -> 2 | 0001 -> 3 | 0010 -> 4 | 0011 -> 0 |  0100...1111 -> 1
KK>-----------------------------------------------------------------
KK>Шаг 5: 0000 -> 1 | 0001 -> 2 | 0010 -> 3 | 0011 -> 4 |  0100...1111 -> 0
KK>

KK>Суммируем значения, полученые, на каждом шаге. Получаем число из интервала [0..20]. Т.е. двадцать одно возможное значение. Двадцать один делится на три без остатка.

А откуда уверенность, что все эти значения равновероятны?
Я так понял, что ты всегда кидаешь монетку 20 раз? Ну значит есть 1024 * 1024 = 1 048 576
1 048 576 / 3 = 349 525 + 1/3. Упс. Один из исходов будет примерно на 1 миллионную (точнее на 1 : 1 048 576) чаще...
Это если у тебя алгоритм хороший... Если плохой, может и не так ровно ( 349 525 к 349 525 к 349 526) получиться...

В целом алгоритм с такими свойствами можно предложить попроще...
Ну типа так:
Бросаем две монеты. получаем число от 00 до 11. Если 01, 10 или 11, то берём 1-й, 2-й или 3-й исход.
иначе повторяем. И так 10 раз. Если за 10 раз не получилось (то есть выбросили 20 решек кряду), то берём третий...