Интересный вопрос от Я! Как решить проблему неправильных монет?

Question

[monotonegative]

Не так давно, на вступительном испытании на стажировку мне попался следующий вопрос:

Условие
Есть набор из 100 нечестных монеток, у i-ой монеты вероятность выпадения орла равна 1/(2i+1), для (i = 1, 2, ... , 100). Результаты для каждой монеты являются независимыми. Вы бросили все монеты по одному разу, какова вероятность того, что мы получили нечетное количество орлов?

Формат вывода
Если ответ не является целым числом, запишите его в виде десятичной дроби, округлив ответ до 4 знаков после запятой или точки (формат (-)N,NNNN или (-)N.NNNN).

Мое решение (с пояснениями):

import numpy as np

"""     На первом этапе создается массив вероятностей выпадения орла 
    для 100 индивидуальных монет - orels.
"""
orels = []
for i in range (1,101, 1):
    probability = 1/(2*i + 1)
    orels.append(probability)
orels = np.asarray(orels)
"""     Также генерируется массив вероятностей выпадения решек - reshkas.
"""
reshkas = 1 - orels

print(reshkas)

"""     Самое вкусное! 
        Все решение основано на том, что наиболее вероятным НЕЧЕТНЫМ случаем 
    будет выборка с выпадением орла у первой монеты (шанс - 0.(3)) на 99 оставшихся решек.
    Следующий нечетный случай - 3 первых орла на 97 решек, затем 5 первых орлов на 95 решек и т.д.
        Почему я выбрал именно такую последовательность выпадения орлов, а не другую? 
    Да потому, что она наиболее вероятная)) - вероятность выпадения орлов с увеличением i, 
    можно сказать, стремиться к нулю.
        В конечном итоге нужно получит 50 выборок следующего вида:
    Odd_case1 = [О P P P P P...P[100]]
    Odd_case2 = [О O O P P P...P[100]]
    Odd_case3 = [О O O O O P...P[100]]
    ...
    Odd_case50 = [О O ...О[99] Р[100]]
    , где О - орел, Р - решка.

        Чтобы получить такие выборки я итерирую массив решек 'reshkas' с поиндексной 
    заменой i-ой решки на i-го орла из массива 'orels' c шагом 2. 
    В каждом цикле для каждой такой выборки мы  считаем общую вероятность 
    выпадения именно такой комбинации перемножив вероятности всех выпавших монет в выборке. 
        Полученные значения заносятся в новый массив 'oryol_probability', что является 
    массивом вероятностей выпадения i-го числа орлов, где i = 1, 3, 5 ... , 99.
"""

oryol_probability = []
for i in range (1, 100, 2):
    if reshkas[i] > 0:
        reshkas[:i] = orels[:i]
    # print(reshkas) - Unmute, если хотите отследить процесс замены.
    multyplied_coins = np.prod(reshkas)
    oryol_probability = np.append(oryol_probability, [multyplied_coins], axis = 0) 

print('Массив вероятностей выпадения i-го числа орлов:', oryol_probability) 

""" Ответ есть сумма полученных 50 общих вероятностей выборок, в которых наиболее вероятно выпало нечетное количество орлов. 
""" 

odd_orels_probability = np.sum(oryol_probability)
print('Ответ: ', '%.4f' % odd_orels_probability)

Мой ответ:

0.0460

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

Comments

[uvelichitel]

На глаз ответ неправдоподобный, слишком мало. Должно быть ближе к 0.5 С чего бы вдруг вероятность нечетного количества орлов была настолько меньше четного? Чем нечетное хуже возмущается здравый смысл.

[jcmvbkbc]

Все решение основано на том, что наиболее вероятным НЕЧЕТНЫМ случаем будет выборка с выпадением орла у первой монеты (шанс - 0.(3)) на 99 оставшихся решек.

Это не решение, это какая-то догадка. Чтобы найти решение "в лоб" нужно просуммировать вероятности всех исходов с нечётным количеством орлов, но их очень много -- 2^99. Поэтому надо придумать способ сделать это быстрее.

[dollar]

Привет, %новичок%. Здесь действуют правила ресурса. Приветствия, прощания, спасибо, респекты и прочее относится к флуду. Задачи запрещены. Опросы запрещены. В вопросе нужно обозначить четкую однозначную проблему, - например, найти ошибку там, где ты ее битый час не можешь найти. Это на будущее, если надумаешь задать второй вопрос.

[dollar]

DarthWazer, абсолютно точно. Сам часто так говорю. Правда, здесь важно, какой смысл вкладывается в этим слова. В общем, я хотел напомнить, что вопрос могут удалить. Думаю, шанс где-то 40%, что удалят, если не переформулировать.

[monotonegative]

uvelichitel, Если мы ограничимся первыми 2-мя монетами, тогда существует 2 варанта выпадения нечетных орлов O[1]|P[2] и P[1]|O[2]. Вероятность первого 0,33*0,8=0,264 и 0,66*0.2=0,132. Их сумма будет вероятностью выпадения одного нечетного орла. Вроде как близко к 0.5, но с увеличением числа монеток вероятность орла считай стремится к 0, что вносит свои корректировки

[monotonegative]

dollar, спасибо за замечание. Учту на будущее.

[Asparagales]

uvelichitel,

Должно быть ближе к 0.5 С чего бы вдруг вероятность нечетного количества орлов была настолько меньше четного?

Например, если выпадение орла настолько редкое событие, что в серии из 100 бросков, он, как правило, не выпадает больше одного раза. В таком случае, вероятность нечетного количества орлов намного выше 50%.
Впрочем, по математике у меня в школе были одни двойки, а информатики вообще не было. Так что не слушайте меня.
UPD. Вообще мне кажется нужно просчитать все вероятности нечетного выпадения и сложить их. Затем то же проделать для четных выпадений и сравнить между собой.

[Araik]

monotonegative,

вероятность выпадения орлов с увеличением i,
можно сказать, стремиться к нулю.

Т.е. после N раз, сколько не бросай монетку, выпадет решка? Очевидно же, что нет)

Answer 1

[Rsa97]

Предположим, что мы бросили n-1 монет и получили какое-то количество единиц (орлов). Бросаем следующую монету (n). Если выпадет ноль (решка), то количество единиц не изменится, и чётность останется той же. Если выпадет единица, то чётность изменится.
P^odd_n = P^odd_n-1*P⁰_n + P^even_n-1*P¹_n
P^even_n = P^even_n-1*P⁰_n + P^odd_n-1*P¹_n
Но, поскольку события P^even_n и P^odd_n образуют полный набор вариантов (либо чёт, либо нечет), то P^even_n + P^odd_n = 1.
Аналогично, P⁰_n + P¹_n = 1.
Отсюда, P^odd_n = P^odd_n-1*(1-P¹_n) + (1-P^odd_n-1)*P¹_n

var Podd = 0;
var Peven = 1;
for (var i = 1; i <= 100; i++) {
  P1 = 1 / (2 * i + 1);
//  P0 = 1 - P1;
//  Po = Podd * P0 + Peven * P1;
//  Peven = Podd * P1 + Peven * P0;
//  Podd = Po;
// Всё, что выше, ужимается в
  Podd = Podd * (1 - P1) + (1 - Podd) * P1;
}
console.log(Podd);
// 0.49751243781094556

Comments

[o5a]

Только лучше сразу писать

Podd = Podd * P0 + Peven * P1;
Peven = 1 - Podd;

А то так лишний пересчет Peven идет.

[Rsa97]

o5a, Логично. Но тогда можно и сразу считать
Podd = Podd * (1 - P1) + (1 - Podd) * P1;

[monotonegative]

Rsa97, Спасибо за доступность изложения!

Answer 2

[longclaps]

Орёлс, решкас... Стыдно-с лепить горбатого.

from fractions import Fraction


def foo(n):
    a, b = Fraction(1), Fraction(0)
    for i in range(n * 2, 0, -2):
        a, b = (a * i + b) / (i + 1), (a + b * i) / (i + 1),
    return b


print(foo(1))
print(foo(100))

Мое решение, рАвно как и ответ, претендуют на правильность, да-да-да )

Comments

[monotonegative]

longclaps, спасибо. Поясните пожалуйста свое решение.
Поставив шаг 2 в диапазоне 200 для for вы таким образом избавились от двойки при i, верно?

[longclaps]

monotonegative, а что пояснять-то: идеологическимоё решение - двойник решения Rsa97, которое он откомментировал.
И да, я избавился от двойки.

Answer 3

[Alexej Simakov]

Вы в рассуждении говорите о "последовательности" выпадения. Тут нет никакой "последовательности". Монеты можно бросить все сразу или по очереди - разницы нет никакой.

Альтернативно можно решать другую задачу. У нас кубики с пронумерованными сторнами. Первый кубик имеет три стороны (ну представим себе такой), второй - пять, третий - 7, следующий - 2*i+1. Соответственно выбросить единицу на каждом кубике мы можем с вероятностью 1/2*i+1. Нас интересует вероятность того. что после броска всех кубиков количество единиц на них будет нечетным.
Вспомним элементарную задачу. Пусть у нас два шестигранных кубика. Как мы посчитаем вероятность того что мы получим две единицы? Количество благоприятствующих исходов к количеству возможных исходов. т.е. 1 исход из 11. Идем дальше, у нас два кубика. Какова вероятность того что мы бросим нечетное количество единиц? Это вероятность единицы на одном кубике помноженная на вероятнось "не-единицы" на другом. Т.е. 1/6 * 5/6.

Думаю такой подсказки будет достаточно.