Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Рандом

Автор: cupper 25.1.2010, 12:48

Цитата

Предположим, что нам надо выводить 0 и 1 с вероятностью 50%. В нашем распоряжении имеется процедура Biased_Random, которая с вероятностью р выдает 0, и с вероятностью 1 — р — число 1; значение р нам неизвестно. Сформулируйте алгоритм, использующий в качестве подпрограммы процедуру Biased_Random и возвращающий равномерно распределенные числа 0 и 1, т.е. вероятность вывода каждого из них равна 50%. Чему равно математическое ожидание времени работы такой процедуры и как оно зависит от р?

Что то я даже понятия не имею как это сделать, есть у кого идеи ? про матиматическое ожтидание можно пока забыть.

Автор: Loner 25.1.2010, 13:44

Если я правильно понял описание, то

Код


int Unit_Random()
{
    return Biased_Random(0.5);
}

разве нет?

Добавлено через 10 минут и 20 секунд
а, нет, понял

Автор: comcon1 25.1.2010, 14:02

Идея такая:

int a,b;
do {
a = Biased_Random();
b = !Biased_Random();
} while (a != b);
return a;

Почему-то мне кажется, что будет равномерно.

Автор: Loner 25.1.2010, 14:07

нет, не правда.
будет 0 с вероятностью p

Добавлено через 1 минуту и 20 секунд
серия экспериментов будет заканчиваться на 10 с вероятностью p

Добавлено через 4 минуты и 31 секунду
все-таки, ты прав. Я тупанул smile

Автор: Peter 25.1.2010, 14:55

Цитата(comcon1 @ 25.1.2010, 14:02

)

Почему-то мне кажется

Несерьезно.

Автор: cupper 25.1.2010, 15:02

Цитата(comcon1 @ 25.1.2010, 14:02)

Идея такая:

int a,b;
do {
a = Biased_Random();
b = !Biased_Random();
} while (a != b);
return a;

Почему-то мне кажется, что будет равномерно.

незнаю верно или нет но это можно проверить.
Сгенерировать этой функцией 100000 значений и посчитать соотношение нулей и единиц в ней. Домой приду проверю.

ТУПЛЮ, это видоизмененое то что мне уже предлогали, в этой случае вывд будет типа 0 1 0 1 0 1 0 1 это не с вероятностью 50% это просто чероедование :(
Понимаю, это первое что приходит в голову )) мне тоже

Автор: Peter 25.1.2010, 17:49

Подсказка. Рассмотри случайную величину [Biased_Random() + 1 - Biased_Random()]

Автор: comcon1 25.1.2010, 18:15

Цитата(cupper @ 25.1.2010, 15:02

)

ТУПЛЮ, это видоизмененое то что мне уже предлогали, в этой случае вывд будет типа 0 1 0 1 0 1 0 1 это не с вероятностью 50% это просто чероедование

нет, это не чередование. Вероятность выпадения 0 - p, вероятность выпадения 1 - (1-p). Значит вероятность того что выпадет 01 - p(1-p). тогда выведет 0.

00 - p^2 - отсекаем
10 - p(1-p) - принимаем нулем
01 - p(1-p) - принимаем единицей
11 - p^2 - отсекаем

Все верно. Просто возможно, есть вариант поприятнее.

Автор: Peter 25.1.2010, 19:03

Правильно. Или
00 - p^2 - принимаем нулем
10 - p(1-p) - отсекаем
01 - p(1-p) - отсекаем
11 - p^2 - принимаем единицей

Автор: cupper 25.1.2010, 19:54

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

Автор: Peter 25.1.2010, 20:13

comcon1 ошибся и я тоже. Читать так:
00 - p^2 - отсекаем
10 - p(1-p) - принимаем нулем
01 - p(1-p) - принимаем единицей
11 - (1-p)^2 - отсекаем

Автор: esperanto 29.1.2010, 11:42

Цитата(Peter @ 25.1.2010, 20:13)

Время работы вашего алгоритма не ограничего.

Среднее время работы равно 1\(2P(1-p))

Автор: comcon1 29.1.2010, 12:45

Я не ошибся, я отсек то, что нужно.
"11 - p^2 - отсекаем" - просто эту строчку неправильно написал

esperanto, ну извини, да, если p = одна миллионная процента, то работать будет дохрена. У тебя есть идеи быстрее? Мне интуитивно кажется, что должно быть что-то быстрее.

Автор: esperanto 29.1.2010, 17:54

Цитата(comcon1 @ 29.1.2010, 12:45)

Есть значения р, для которых возможны алгоритмы останавливающиеся через конечно время.

Есть значения для которых нет алгоритма выдающего ровно 0.5 0.5 через конечное время.

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

Автор: comcon1 30.1.2010, 04:52

esperanto, было бы прикольно, если бы ты что-то написал конкретное, хотя бы в общих чертах. Потому что это интересно.

Автор: esperanto 30.1.2010, 10:59

Цитата(comcon1 @ 30.1.2010, 04:52)

Есть много статей научных на эти темы

Например можете начать отсюда "http://www.eecs.umich.edu/~qstout/pap/AnnProb84.pdf"
Там в списке литературы еще много источников.

А если в кратце, то это то, что я вам уже написал.