В теорвере рубит кто-нибудь?

[ohshitnotuagain.livejournal.com]

Решаю тривиальную, в общем-то задачку:
"Посчитать мат. ожидание количества бросков монетки для получения последовательности из двух заданных исходов (например, решка-решка)"
Вывел формулу (изобрёл велосипед):


вроде работает, для M=2 (две решки, например) выходит 6 бросков
для 3 - уже 14

но пытаюсь это в общем виде теперь сделать для любого числа возможных равновероятных исходов, не только для орёл-решка
вроде вот так должно быть:

, где:
N - мат. ожидание длительности серии испытаний для получения необходимой последовательности исходов
M - длина целевой последовательности исходов
p - вероятность равновероятных исходов испытаний
K - общее число возможных исходов испытаний
i - инкремент

Но при подсчёте для 3 бросков 10-гранного кубика выходит отрицательное мат. ожидание:
N = 0,9(N+1) + 0,81(N+2) + 0,729(N+3) + 3/1000
-1,439N = 4,71
Чсх, для монетки эта обощённая формула всё ещё работает
а вот как только K > 2, ломается(

Comments

[mudlaws.livejournal.com]

а вопрос?
так то на http://s43.mccme.ru/math/uroki/2009_2010/9mat_0910/spec/19_mathexpectation_beseda_resh.pdf

[ohshitnotuagain.livejournal.com]

вопрос: как посчитать мат. ожидание длины (N) серии бросков для произвольной длины искомой последовательности (M) на кубике с произвольным числом граней (K)

[mudlaws.livejournal.com]

лень. и вообще мне спать уже полчаса надо

[garten-besitzer.livejournal.com]

Скобки трэшево расставлены, однако.

[led-mist.livejournal.com]

похоже на отрицательное биномиальное распределение, но надо переформулировать для заданной последовательности а не 1 успеха

[karpion.livejournal.com]

У меня ощущение, что для разных последовательностей (одной и той же длины) ответ будет разный.

Пусть мы ищем последовательность "АА", и первым символом был "А", а вторым - "Б". Тогда "АА" может появиться не ранее третьего символа.
А если мы ищем "АБ", первым символом был "А", и вторым - снова "А", то "АБ" может начаться уже с второго символа.

Лично я бы начал проверку с написания программы, реализующей полный перебор достаточно длинных строк.

[ohshitnotuagain.livejournal.com]

Я запилил эксельник, симулирующий 100 серий по 100 подбрасываний монетки.
В каждой серии он находит номер подбрасывания, на котором происходит достижение нужной последовательности.
Затем считает среднее значение этих номеров для всех 100 серий.

Пересчитать симуляцию, обновив все случайные числа можно нажатием F9.
В итоге выходит следующее:
11 / 00 - в среднем 6 бросков
01 / 10 - в среднем 4 броска

Вы правы, а я ошибся в формуле.
Но я не знаю, как и где(

На всякий случай ссыль на эксельник:
https://vk.com/doc3380791_440789235

[karpion.livejournal.com]

Тут лучше запилить не рандомную генерацию, а полный перебор.

Вы ошиблись примерно вот где:

1) Допустим, мы ищем шаблон из двух букв (букв те же две - "А" и "Б"). Вероятность того, что первые две буквы оказались нужными = 1/4, тут без вопросов. Допустим, первые две буквы нашей строки оказались не те, что мы ищем.

3) Перескочим вперёд, пропустив второй шаг.
Вероятность того, что третья и четвёртая буквы нашей строки.будут нужными - тоже 1/4, независимо ни от того, что было в первых двух буквах, и от того какую подстроку мы ищем.

2) А теперь вернёмся ко второму пункту - к второй и третьей буквам.
Капитан Очевидность как бы намекает, что вторая буква из первого пункта и вторая буква из второго (этого) пункта - это одна и та же буква. И она ни фига не случайная - если первая буква строки совпала с первой буквой шаблона, то вторая буква строки не совпадает со второй буквой шаблона!

Т.е. я телепатирую, что Вы применяли формулу независимой вероятности, а надо применять условную вероятность.

Upd: Таблицу лучше делать в Гуглодоксе.