#algorithm
#алгоритм
Вопрос:
Я пытаюсь написать функцию, которая будет возвращать true или false при каждом вызове, но с известной частотой, скажем, в 60% случаев это будет true, в остальных 40% — false. Используя эту функцию, я должен создать другую функцию, которая возвращает true в 50% случаев.
Мой первоначальный подход заключался в использовании функции random и возврате true, если оно меньше 0.6, false, если оно больше. Не уверен, как подойти ко второй части, используя это.
Комментарии:
1. Посмотрите на четыре случая (первый вывод, второй вывод): (1)True True (2) True False (3)False True (4) False False. Чтобы получить True на втором выходе, вам нужно суммировать вероятности случаев (True True) и (False True). Чтобы получить False на втором выходе, вам нужно суммировать вероятность (True False) и (False False)
2. Это кажется излишне сложным. Почему бы не использовать random() напрямую для реализации обоих?
3. О, я ненавижу искусственные проблемы — мир достаточно полон реальных, насколько я могу видеть.
4. @eric: Я бы посоветовал вам проигнорировать комментарий Нила об искусственной проблеме. То, что невозможно придумать какие-либо приложения, не означает, что их нет. К сожалению, вы найдете много подобных (да, я так и сказал: узколобых) комментариев на этом сайте. Я надеюсь, вы не позволите таким комментариям обескуражить вас. И кстати, добро пожаловать на этот сайт.
5. Это вовсе не искусственная проблема. Это реальная проблема. Обычно я видел, что это представлено с неизвестным значением P; Я полагаю, что для некоторых конкретных значений P можно было бы вызвать более быструю конвергенцию. Я думаю, что наиболее очевидным реальным применением для этого является генерация равномерно распределенных битов с учетом источника «действительно случайных» данных (таких как фоновые радиоволны или что-то еще). По сути, это способ отфильтровывать мусор.
Ответ №1:
Давайте рассмотрим общий случай: вы создали функцию F1(), которая возвращает True с вероятностью P (в вашем случае P = 60%). теперь вы создаете вторую функцию таким образом:
F2():
result1 = F1()
result2 = F1()
if result1 = True and result2 = False: return True
elif result1 = False and result2 = True: return False
else: F2()
В этом случае вероятность повторного запуска F1 и получения (True, False) такая же, как и для получения (False, True), и она равна P * (1-P). Вместо этого, если вы получаете либо (True, True), либо (False, False), вы рекурсивно вызываете F2. Это означает, что после запуска F2 вы всегда получаете True или False с вероятностью 1/2, поскольку первые две ветви имеют равные вероятности, а третья всегда будет выдавать вам результат функции с вероятностью 1/2.
Я делаю это вики сообщества на случай, если кто-то захочет сделать мой ответ более понятным. Я понимаю, что может быть немного сложно объяснить концепцию.
Среднее количество вызовов
Вероятность того, что функция F2() завершится сразу после n рекурсивных вызовов, равна:
{(1-P) ^ 2 P ^ 2}^n * 2P(1-P)
Следовательно, среднее количество требуемых рекурсивных вызовов равно:
Sum_{i=0}^infty i*{(1-P) ^ 2 P ^ 2}^i *2P(1-P)
Комментарии:
1. круто, не забудьте принять, если почувствуете, что это отвечает на ваш вопрос 🙂
2. @sawa: Вероятность получения TF или FT равна 6/25. Таким образом, ожидаемое количество вызовов равно 25/6.
3. Я добавил формулу для получения средних вызовов. Может ли кто-нибудь продолжить вычисление?
4. @sawa: Если вероятность выпадения орла равна p, то ожидаемое количество бросков, прежде чем мы увидим орла, равно 1 / p. Это хорошо известный факт, и его можно доказать, используя бесконечный ряд для математического ожидания. Здесь появляется еще одно доказательство: en.wikipedia.org/wiki /…
5. Когда это применяется к реальному миру, часто F1 имеет некоторый конечный резервный поток битов. В этом сценарии общим улучшением для снижения скорости, с которой потребляются базовые данные F1, является добавление result1 в конец базового битового потока F1 в случае, если result1 и result2 равны.
Ответ №2:
Итак, у нас есть некоторая функция, которая генерирует истинное значение с p = 0.60 и ложное значение с p = 0.40 . Предположим на секунду, что мы запускаем эту функцию дважды? Какова вероятность того, что результаты будут одинаковыми.
таким образом, F_1 == true и F_2 == true выполняются с p (0.60 * 0.60) = 0.36
и F_1 == false и F_2 == false происходит при p(0.40 * 0.40) = 0.16
и F_1 != F_2 происходит с p( 0.6 * 0.4 0.6 * 0.4 ) = 0.48
это даст вам функцию, которая возвращает true в 0,52% случаев, что не совсем то, что мы ищем, но интересно.
Гораздо более простым решением было бы сказать: Если у меня значение true в 60% случаев, то в каком проценте времени (с какой вероятностью) я должен менять это значение на false, чтобы оно было true в 50% случаев.
Это все, что я скажу, потому что это домашнее задание.
Комментарии:
1. Это должны были быть F_1 и F_2, а не F_1 и F_1
Ответ №3:
Подход:
Вы запускаете свою функцию 40/60, пока не достигнете результата, который возвращает вероятность 40%. Как только это произойдет, вы вычисляете результат.
0,5 вычисляется таким образом.
0.5 = 0.6 — 0.6^2 0.6^3 0.6^4 — 0.6^5 — 0.6^6 0.6^7 0.6^8 — 0.6^9 ….
(если текущий результат больше 0,5, вы добавляете остальное, которое вычитаете)
Как только вы нажмете 0.4, вы вычисляете результат этой функции. Если оно > 0.5, вы возвращаете true, в противном случае вы возвращаете false.
Ответ №4:
эй, как насчет такого подхода: Мы знаем, что вызов F1 () 10 раз: 6 раз он вернет true и 4 раза false
Итак, в F2 () у нас может быть счетчик, который считает до 5. С каждым вызовом F1() мы увеличиваем счетчик. F2() возвращает то, что возвращает F1(). Когда счетчик достигает 5, F2() возвращает «false» и повторно инициализирует счетчик. Что скажете?