Матожидание для случайной последовательности символов

[B@R5uk]

Пусть у нас есть генератор случайных символов из некоторого алфавита длины $k$. Причём все символы, выдаваемые этим генератором равновероятны и не зависят от предыдущих. И у нас есть некоторая строка длины $m$ символов из того же алфавита. Вопрос в том, сколько в среднем потребуется нагенерировать символов, чтобы в качестве последних $m$ получилась искомая строка.

Если честно, то я без понятия с какого боку к этой задаче вообще подойти. Единственное, что приходит в голову, — это взять какие-нибудь простейшие случаи и посчитать в лоб. Вот, например, пусть искомая строка имеет длину один. Тогда нам всё равно из какого символа она состоит, так как все они равновероятны. Вероятность того, что искомый символ выпадет на n-ой позиции равна:

$${{p}_{n}}=\frac{1}{k}{{\left( \frac{k-1}{k} \right)}^{n-1}}$$

Тогда средняя ожидаемая длина последовательности будет

$$L=1\cdot \frac{1}{k}+2\cdot \frac{k-1}{k}\frac{1}{k}+3\cdot {{\left( \frac{k-1}{k} \right)}^{2}}\frac{1}{k}+4\cdot {{\left( \frac{k-1}{k} \right)}^{3}}\frac{1}{k}+\ldots =\frac{1}{k}\sum\limits_{n=1}^{\infty }{n{{\left( \frac{k-1}{k} \right)}^{n-1}}}$$

Выведя вот такую формулу:

$$\[\sum\limits_{n=0}^{\infty }{\left( n+1 \right){{a}^{n}}}=\frac{\partial }{\partial a}\left( \sum\limits_{n=0}^{\infty }{{{a}^{n+1}}} \right)=\frac{\partial }{\partial a}\left( \frac{a}{1-a} \right)=\frac{1}{1-a}+\frac{a}{{{\left( 1-a \right)}^{2}}}=\frac{1}{{{\left( 1-a \right)}^{2}}}\]$$

Можно посчитать и длину:

$$L=\frac{1}{k}\sum\limits_{n=0}^{\infty }{\left( n+1 \right){{\left( \frac{k-1}{k} \right)}^{n}}}=\frac{1}{k{{\left( 1-\frac{k-1}{k} \right)}^{2}}}=k$$

Удивительно, что результат — это целое число.

Можно видеть что даже в простейшем случае получаются не хилые такие выкладки. Дальше ещё интереснее. Пусть теперь для простоты длина алфавита будет два. Опять же для простоты пусть это будут символы "А" и "Б". И пусть искомая стока — это пара символов "АА". Для этого случая я составил такую последовательность:
А 1/2
Б 1/2

АА! 1/4
БА 1/4
?Б 2/4

БАА! 1/8
?БА 2/8
??Б 3/8

?БАА! 2/16
??БА 3/16
???Б 5/16

??БАА! 3/32
???БА 5/32
????Б 8/32

???БАА! 5/32
????БА 8/32
?????Б 13/32
В этой последовательности числа в числителях вероятности ни что иное, как числа Фибоначчи!!! Кто бы мог подумать! В результате формула для средней длины последовательности получается такая:

$$\[L=\sum\limits_{n=1}^{\infty }{\frac{\left( n+1 \right){{F}_{n}}}{{{2}^{n+1}}}}\]$$

Я без понятия как такую бесконечную сумму можно свернуть, но численный расчёт показал, что значение очень близко к 6. Аналогично рассматривается поиск пары символов "АБ". В этом случае ответ такой:

$$\[L=\frac{1}{4}\sum\limits_{n=1}^{\infty }{\frac{n\left( n+1 \right)}{{{2}^{n-1}}}}=\frac{1}{4}{{\left. \frac{{{\partial }^{2}}}{\partial {{a}^{2}}}\left( \sum\limits_{n=1}^{\infty }{{{a}^{n+1}}} \right) \right|}_{a={1}/{2}\;}}=\frac{1}{4}{{\left. \frac{{{\partial }^{2}}}{\partial {{a}^{2}}}\left( \frac{{{a}^{2}}}{1-a} \right) \right|}_{a={1}/{2}\;}}=\frac{1}{4}{{\left. \frac{2}{{{\left( 1-a \right)}^{3}}} \right|}_{a={1}/{2}\;}}=4\]$$

Тоже целое число.

То, что результатами являются целые числа, вызывает у меня смутное подозрение, что здесь есть какая-то хитрость. Возможно какая-то рекуррентная формула или что-то ещё, что сильно упрощает расчёт. Подскажите, пожалуйста, в каком направлении копать?

[wrest]

B@R5uk
Дальше, кмк, будут вылезать трибоначчи, тетраначчи и т.п.

[upgrade]

B@R5uk в сообщении #1285161 писал(а):

сколько в среднем потребуется нагенерировать символов, чтобы в качестве последних $m$ получилась искомая строка

Это чтобы гарантировано получилась вы хотите узнать сколько в среднем? Тогда возьмите монетку, задайте вопрос - сколько в среднем надо ее подбросить, чтобы гарантировано выпал орел (неважно на каком броске).

[B@R5uk]

upgrade в сообщении #1285170 писал(а):

Тогда возьмите монетку...

Так я, вроде, эту задачу решил выше: $k=2$, $m=1$; ответ: $L=k=2$. Или вы что-то другое имеете в виду?

[mihaild]

Ответ как минимум зависит от строки (а не только от длины).
Можно считать, что у нас марковский процесс, состояние - длина наибольшего префикса нашей строки, являющегося суффиксом сгенерированной на текущей момент части строки. Матрица переходов выписывается, и дальше остается оценить среднее время до попадания в состояние "длина всей строки".

upgrade в сообщении #1285170 писал(а):

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

Непонятно, по чему тут можно предлагается усреднять.

[upgrade]

B@R5uk
mihaild
Да, я имел ввиду, что если гарантировано, то ответ не получить, теперь вижу, что надо считать среднее число шагов до заданной последовательности.

[B@R5uk]

mihaild в сообщении #1285188 писал(а):

Ответ как минимум зависит от строки (а не только от длины).

Разумеется! Например, последовательность "АБАБ" значительно проще встретить, чем "АБББ".

mihaild в сообщении #1285188 писал(а):

Можно считать, что у нас марковский процесс...

Я, к сожалению, не владею этой наукой. И у меня есть подозрение, что задачу можно как-то свести к подсчёту каких-нибудь комбинаций из символов.

[mihaild]

B@R5uk в сообщении #1285232 писал(а):

Я, к сожалению, не владею этой наукой.

Тут ничем особо владеть не надо.
У нас есть граф из $n + 1$ вершин, мы находимся в вершине с номером, равным длине наибольшего префикса искомой строки, являющегося одновременно суффиксом прочитанной. Вероятности перехода из одной вершины в другую понятно какие. И дальше нужно просто посчитать, когда мы в первый момент придем в точку $n$.

[--mS--]

B@R5uk в сообщении #1285232 писал(а):

mihaild в сообщении #1285188 писал(а):

Ответ как минимум зависит от строки (а не только от длины).

Разумеется! Например, последовательность "АБАБ" значительно проще встретить, чем "АБББ".

Среднее время ожидания последовательности "АБАБ" больше среднего времени ожидания последовательности "АБББ".
Например, об это можно прочесть в книге Грэхем, Кнут, Паташник "Конкретная математика", параграф 8.4 (начиная с формулы 8.76). В статье А.Д.Соловьёва 1966 есть и формулы для общего случая (стр. 318): http://www.mathnet.ru/links/f00bd2db1da ... tvp626.pdf

[B@R5uk]

--mS--, большое спасибо за ссылки! Статью просмотрел по диагонали. Там в конце, конечно, есть формула, которая вроде бы даже является ответом на мой вопрос, но я не понимаю не то что её вывод, даже посылки к нему, слишком уж изложение матанизировано. Не уверен, что и формулой смогу правильно воспользоваться. Кнута скачал, попробую почитать, может в нём будет понятнее.

[B@R5uk]

--mS-- в сообщении #1285276 писал(а):

В статье А.Д.Соловьёва 1966 есть и формулы для общего случая

Там приводится такая формула:

$${{\alpha }_{i}}=\sum{\operatorname{P}\left\{ {{A}_{1}}{{A}_{{{k}_{1}}}}\ldots {{A}_{{{k}_{j-1}}}}{{A}_{i}} \right\}{{\left( -1 \right)}^{j}}}$$

где суммирование ведётся по всем числам $k_s$, удовлетворяющим условию:

$$\begin{matrix} 0<{{k}_{1}}-1\le m \\ 0<{{k}_{2}}-{{k}_{1}}\le m \\ \ldots \\ 0<{{k}_{j-1}}-{{k}_{j-2}}\le m \\ 0<i-{{k}_{j-1}}\le m \\ \end{matrix}$$

Я правильно понимаю, что $\alpha_1=\operatorname{P}\left\{A_1\right\}$, то бишь просто вероятность события $A_1$ ?

[--mS--]

Похоже, что так.

[B@R5uk]

Спасибо.

Далее в статье есть конкретный пример применения. Пишут следующее:

Цитата:

Пусть дана последовательность независимых испытаний, при каждом из которых появляется один из $n$ символов $1,2,\ldots,n$, причём $k$-й символ появляется с вероятностью $p_k$.

Рассмотрим бесконечную реализацию этих испытаний $a_1,a_2,\ldots,a_N,\ldots$. Отрезок этой последовательности $a_i a_{i+1},\ldots,a_{i+m}$ назовём словом длины $(m+1)$, стоящим на $i$-м месте. Возьмём фиксированное слово $c_0 c_1,\ldots,c_m$ длины $(m+1)$. Скажем, что произошло событие $A_i$, если в нашей реализации на $i$-ом месте появилось это слово.

...

Введём условные вероятности $\pi_i=\opertoraname{P}\{A_{i+1}|A_1\}$, $i=1,2,\ldots,m$,...

Я правильно понимаю, что если первые $(m+1-i)$ символов слова $c_0 c_1,\ldots,c_m$ не совпадают с его $(m+1-i)$ символами, то эта условная вероятность $\pi_i$ равняется нулю, а если же совпадают, то она равна произведению вероятностей $p_{c_s}$ последних $i$ символов? То есть

$${\pi_i}=\prod\limits_{s=m+2-i}^{m+1}{p_{c_s}}$$

[--mS--]

Скорее, единице.

(Оффтоп)

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

[B@R5uk]

--mS-- в сообщении #1285877 писал(а):

если в результате мне же и придётся совершенно ненужную мне статью разбирать

Что поделаешь, если мои способности весьма ограничены, а в статье нет наглядных примеров? Кстати, большое спасибо за книжку про суммирование. Я этой темой одно время очень сильно интересовался, даже сайт запилил со своими наивными поделками. Вывод формулы с суммой последовательных $n\sin(\omega n)$ — это была настоящая жесть! Пришлось изрядно поизвращаться добавляя/вычитая простые суммы, чтобы это всё дело свернулось в телескопическую сумму. Я уже даже и не помню как именно это получилось.

--mS-- в сообщении #1285877 писал(а):

Скорее, единице.

Почему это единице? Если суффикс слова совпадает с префиксом, то это не значит, что всё, следующее после префикса, выпадет с единичной вероятностью. Или я не правильно понял смысл условных вероятностей $\pi_i$?