Нет кого спросить, помогите пожалуйста решить задачу по математике.⁠⁠

Всем привет, повторяю школьный курс математики (вообще ничего не помню). Меня заинтересовала тема: "теория вероятностей".
Например, вероятность того, что выпадет 3 решки подряд - 1 к 8.
Попробовал проделать тоже самое с игральной костью, мол, какая вероятность выпадения одной и той же грани 10 раз подряд? вероятность составила 1 к 60 466 176. (Я правильно посчитал?)

Проконсультируйте пожалуйста по другому вопросу теперь. Я возможно запутался, но хочу разобраться.
Допустим у меня есть 500 попыток, и задача поймать орла (не решку) 7 раз подряд, какова будет вероятность выполнения данной задачи? (хочу узнать, как осуществить данный расчет)

Спасибо заранее.

Вы смотрите срез комментариев. Показать все

atomic

7 лет назад

надо определить количество возможных интервалов, на которых возможно искомое событие.

Т.е. мы можем получить семь решек подряд на экспериментах:

1,2,3,4,5,6,7 (интервал 1)

2,3,4,5,6,7,8 (интервал 2)

...

494,495,496,497,498,499,500 (интервал 494)

Всего, совпадение возможно на 494 интервалах.

__________

Во-вторых, нужно заранее условиться, является ли выпадение решки восемь раз подряд как два искомых события, или после наступления события, интервал обнуляется.

Т.е. если у нас выпали решки на интервале от 1 до 7, то считаем ли мы выпадение восьмой решки (интервал от 2 до 8) как еще одно искомое событие или нет?

В первом случае, количество событий на 500 экспериментах равна [ (1/2)^7 ] * 494.

Во втором случае... Думайте сами :)

раскрыть ветку (12)

nbvehbectw

7 лет назад

А какая разница, будем ли мы считать 8 решек подряд за два или за одно событие? Нам ведь нужно найти не количество таких событий, а найти вероятность появления хотя бы одно.

Во-вторых, вероятность считается как количество положительных исходов, деленная на количество всевозможных исходов. Количество всевозможных исходов равно 2^500. Чтобы посчитать количество положительных, можно было бы перебирать варианты с 7 подряд идущими решками и остальными монетами произвольными, получив 494*2^493. Но тогда мы бы два раза посчитали одну и ту же комбинацию, в которой есть более одной последовательности из 7 решек. Ты как раз и допустил эту ошибку.

раскрыть ветку (11)

atomic

7 лет назад

это как раз-таки вы ошибаетесь.

Посудите здраво. Если вероятность выкинуть решку 7 раз подряд (искомое событие) равна (1/2)^7, то вероятность получить искомое событие, произведя не 7 экспериментов, а 500, должна быть ЯВНО ВЫШЕ.

Я упрощу задачу:

какова вероятность выкинуть одну решку при одном броске? 50%.

Какова вероятность выкинуть хотя бы одну решку при 10 бросках? По вашей формуле, это (1/2) / 2^10.

И вы серьезно так утверждаете, что вероятность получить хотя бы одну решку на 10 бросках равна 0,5/1024 (0,049%), в то время как вероятность получить хотя бы одну решку на 1 броске равна 50%.

раскрыть ветку (10)

nbvehbectw

7 лет назад

Выше, не спорю. Но 494*(1/2)^7 - далеко не единственное число, большее (1/2)^7. Ответ где-то между ними.

По моей формуле в числителе вообще не может стоять дробного числа, так как делится количество на количество. Количество положительных исходов здесь 2^10-1 (все, кроме десяти орлов), количество всех исходов - 2^10, итого вероятность выкинуть хотя бы одну решку равна (2^10-1)/2^10.

Я позволю себе сократить общее количество бросков до 4, а длину искомой цепочки до 2, чтобы была возможность перебрать все варианты. Тогда все возможные исходы:

0000 0001 0010 0011

0100 0101 0110 0111

1000 1001 1010 1011

1100 1101 1110 1111

Содержащие цепочку из единиц длины 2:

0011

0110 0111

1011

1100 1101 1110 1111

Итого 8 исходов из 16, вероятность 1/2.

По твоей же формуле вероятность получить одну цепочку длины 2 равна 1/4, а получить ее можно на следующих экспериментах:

1, 2 (интервал 1)

2, 3 (интервал 2)

3, 4 (интервал 3)

Умножая 1/4 на 3, получаем ошибочную вероятность 3/4. Если записать ее в виде 12/16, то станет видно, что ты посчитал 4 лишних эксперимента, а именно дважды посчитал 0111 (попадает под описание интервалов 1 и 2) и 1110 (интервалы 2 и 3), и трижды посчитал 1111 (все три интервала).

раскрыть ветку (9)

atomic

7 лет назад

я тут уже практически вывел метод расчета...

Загвоздка задачи в том, что в количестве событий (494*2^493) мы не дважды считаем одну и ту же комбинацию, а многократно.

Так, если у нас выпало 7 решек на интервале [1;7] - мы имеем 2^493 возможных исходов.

Среди этих исходов, будут и другие выпадения 7 решек, например, на интервале [8;14], который мы затем повторно засчитываем (в случае 494*2^493).

Значит, нам нужно посчитать количество исходов, при которых событие наступает на интервале [1;7] и не наступает на интервале [8;500]. (Будем считать, что таких исходов у нас X.)

И только затем умножать сумму на количество таких исходов (494).

Также, нам понадобится посчитать количество исходов, при которых событие наступает более одного раза, например, на интервале [1;7] и [8;14], или [1;7] и [9;15] и [16;22] и т.д.

(сумма этих исходов равна Y, как ее посчитать - хз).

Итого у нас будет 494X + Y исходов, при которых событие наступило.

Для того, чтобы посчитать количество событий, при которых искомое событие не наступило на интервале [8;500], нам нужно посчитать количество исходов, при которых это событие наступило (Z), и вычесть из общего количества исходов для этого интервала (2^494 - Z).

Мы будем считать Z также, как считали X, в итоге сдвигаясь на интервал [15;500].

Затем опять сдвиг на интервал [22;500] и т.д. до последнего сдвига на интервал [491;500]

Т.е. у нас будет 70 однотипных интервалов вида [1;7]...[484;490] и один дополнительный интервал [491;500].

На последнем интервале, 7 событий наступают в четырех исходах [491;497], [492;498], [493;499] и [494;500].

Для каждого из этих исходов, общее количество событий равно 8.

Но среди 8 событий первого интервала есть такие, которые повторяются на других интервалах. А не повторяются только 4 события (498 = орел). Аналогично для интервала [494;500] (493 = орел) - также 4 события.

Для второго и третьего интервала таких неповторяющихся события всего два (499 = орел для второго интервала).

Итого 12 неповторяющихся событий.

Повторяющиеся события - не больше 8 решек подряд (3 события), 9 решек подряд (2 события) и 10 решек подряд (1 событие).

Всего 12 неповторяющихся + 6 повторяющихся = 18 возможных событий выпадения 7 решек из общей суммы в 8*4 = 32 событий.

Так, вероятность для последнего интервала [491;500] = 18/32.

После этого считаем интервал [484;490], от него считаем предыдущий и т.д. до первого интервала.

_______________________

Расчет можно сделать одним простым циклом.

Но есть неизвестность с расчетом Y.

раскрыть ветку (8)

nbvehbectw

7 лет назад

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

На самом деле можно и не разделять наборы по количеству входящих в них последовательностей из семи решек. Можно для каждого интервала [q; q+6] считать количество таких наборов, где все, что выпало после q+6 - произвольно, а все, что выпало до q не содержит семи решек подряд (а это считать уже рекурсивно сдвигая интервал). Так будет посчитан каждый набор и по одному разу. А после этого просто просуммировать полученные значение для каждого q.

И "простым циклом" - это громко сказано. Нам нужна память для целого числа, способная содержать в себе числа аж до 2^500. А это 501 бит. Не так уж и много, но все же придется самостоятельно реализовывать в виде массива, ибо даже если компы с такой разрядностью и существуют, то явно не у нас. А время работы программы для такого перебора я уж и боюсь представить.

раскрыть ветку (7)

atomic

7 лет назад

я думаю, можно обойтись без перебора всех значений. Существуют формулы в ТВМС, по которым задачу можно значительно упростить.

Нам в памяти не нужно хранить все 2^500 чисел. Нам же нужно количество исходов, а не их идентификаторы.

Описанная вами последовательность [q;q+6] в целом аналогична предложенной мной.

Просто вы сдвигаете интервал с 1 до 494 и считаете количество исходов слева от интервала (не содержащих 7 решек подряд), а я предложил считать количество исходов справа.

По сути это симметрия:

для интервала [8;14] мы считаем количество исходов, когда на предыдущих интервалах не было семи решек.

Количество таких исходов равно количеству других исходов - когда после интервала [487;493] не попадаются семь решек.

Тут очередность прохода цикла (с конца или с начала) значения не имеет, количество итераций остается неизменным.

раскрыть ветку (6)

nbvehbectw

7 лет назад

Если бы кто-то из нас эти формулы знал, мы бы не выдумывали сейчас всякие дурные циклы. Это точно не схема Бернулли. Да и проблема не в переборе всех значений, а в огромном количестве рекурсивных вызовов. То есть чтобы решить эту задачу для последовательности длины 500, нужно для этого решить ту же задачу для длины 493, а для этой - длины 486, и т.д.

Я говорю не о количестве чисел, а о их размере. Всего исходов 2^500, а значит это число нужно хранить в памяти, чтобы на него потом разделить. У меня, например, процессор 64-разрядный. То есть максимальное целое число, с которым он может работать - это 2^64-1. Чтобы работать с числами больше этого, нужно их искусственно реализовывать.

Не аналогична. У тебя есть некоторый Y, который ты не знаешь, как вычислить, и который по сути и портит всю малину. Я же предложил не считать отдельно X и Y, а вычислять все сразу.

раскрыть ветку (5)

atomic

7 лет назад

Метод перебора не подходит для такого количества значений.

Значит, надо выводить общую формулу.

Я подозреваю, что у нас в числителе окажется 2 в н-ной степени, а значит, степени просто сократятся. Нет нужды вычислять и хранить 2^500, для этого достаточно хранить только 2 числа (2, 500) и в коде учесть, что их отношение это степень. Соответственно, обработку этого числа также производить по степеням.

Т.е. если у нас в числителе, например, N * 2^400, а в знаменателе - 2^500, нам нет нужды вычислять ни 2^400, ни 2^500, причем, в результате каждого сокращения, не высчитывать конечное число, т.к. оно на каждой следующей итерации может также сокращаться.

Суммарно у нас будет 72 рекурсии, причем каждая следующая по количеству итераций будет на порядки меньше предыдущей. Наибольшее количество итераций нужно будет рассчитать только для самого первого (в вашем случае - последнего) интервала.

раскрыть ветку (4)

nbvehbectw

7 лет назад

Короче, вот код на c++ https://drive.google.com/open?id=0BzM2caNTM82AeGxqQXVzblMxbm...

Прога последовательно считает количество положительных исходов и вероятность для последовательностей возрастающей длины, используя при подсчете уже вычисленные значения. Константа MAX_LEN - это длина максимальной последовательности, SEQ - количество цепочки из решек подряд, которые мы ищем. Однако, если указать MAX_LEN больше 63, прога перестанет работать по причине, о которой я говорил выше. Насчет времени - да, я просчитался, прога работает быстро. Насчет 2 в n-ой степени в числителе - нет, там произвольные числа, в том числе и нечетные.

Для примера, для последовательности длины 63 вероятность хоть раз выкинуть 7 решек подряд равна 1917489155220795135 / 9223372036854775808 = 0.20789459078077807

P.S. Только что заметил, 494*(1/2)^7 = 3,859375. Вероятность больше единицы - это замечательно :3

раскрыть ветку (3)

atomic

7 лет назад

знаете, так заморачиваться - вредно :)

По грубым подсчетам из разряда "пальцем в небо", я прикинул, что вероятность будет близка к 100%.

Я также заметил, что 494*((1/2)^7)>1 - именно после этого я и понял первоначальную ошибку и задумался о расчете рекурсией.

С помощью вашего кода, можно сделать приблизительный расчет.

Смысл такой:

мы подкидываем монету 500 раз, но делаем перерывы после каждых 63 бросков.

У нас будет 8 интервалов (по 63 броска каждый), для каждого из которых вероятность получить 7 событий подряд составит 20,79%.

Теперь мы считаем не броски, а группы бросков (далее округлю).

В итоге мы считаем ненаступление события "7 решек хотя бы разово" + "хотя бы на одном из 8 интервалов".

вероятность не выкинуть 7 решек хотя бы однажды на 1 интервале: 80%.

Второе событие связано с первым (вторая группа производится в 80% случаев после первой). Уже 0,8^2.

И т.д. до восьмого интервала. Получим 0,8^8, или 16,78% (если точнее, то 15,49%)

далее 100% - 16,78% = 83,22% - вероятность получить 7 решек хотя бы раз в хотя бы одной из групп бросков (если точнее, то 84,5%).

________________

Между группой 1 и группой 2 есть невидимое разделение (условие аппроксимации). Посчитаем количество возможных исходов, увеличивающих нашу искомую вероятность:

// здесь * - любое значение, эти исходы в каждой группе уже учтены, мы лишь считаем количество событий на разрезах

(...группа 1 | группа 2 ...)

0*****1 | 1111110 // 32 исхода

0****11 | 111110 // 16 исходов

0***111 | 11110 // 8 исходов

0**1111 | 1110 // 4 исхода

0*11111 | 110 // 2 исхода

0111111 | 10 // 1 исход

Т.е. всего у нас 63 события.

Разрезов у нас собственно N-1, где N=8 - количество групп.

Итак, досчитываем число искомых исходов на разрезах: 63*7 = 441.

Ну и собственно 441 / 2^500 - вот на столько они увеличат нашу первонайденную вероятность. То есть, в пересчете на сотые доли, на 0,00%.

Если еще сильнее заморочиться, то можно взять вероятность ненаступления события "7 решек" на первой группе, затем помножить на вероятность ненаступления события на разрезе_1 (~ (1 - 63/2^70) ), затем опять помножить на ненаступление на второй группе и т.д.

Т.е. первонайденную вероятность мы помножим на (1 - 63/2^70)^8 - это число я считать не буду, но и так понятно что это ~ 1. Т.е. невесомо для сотых долей.

раскрыть ветку (2)

Вы смотрите срез комментариев. Чтобы написать комментарий, перейдите к общему списку