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

[B@R5uk]

В общем путём самоотверженного мозгового штурма у меня получилось! Ответ на задачу получается поразительно простой и не имеющий ничего общего с теорией вероятности.

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

Ответ строится следующим образом. Каждый символ слова мы заменяем на "1" или "0" по определённому правилу. "1" ставится в том случае, если символы начиная с этого и вплоть до последнего в точности повторяют первые символы слова. В противном случае вместо символа ставится "0". Затем в конце получившегося числа из нулей и единиц дописывается ещё один ноль. Это ответ. Правда записан он в $k$-ичной системе счисления и его надо перевести в десятичную (или в любую другую по желанию ).

Например. У нас есть алфавит из символов "АБВДКР" и задано слово "АБРАКАДАБРА". Сколько в среднем случайных символов надо получить от генератора, прежде чем в последовательности встретится это слово. Решаем:
АБРАКАДАБРА
АБРАКАДАБРА
_______АБРАКАДАБРА
__________АБРАКАДАБРА
100000010010
То есть ответом является число $100000010010_7$ или в десятичной системе $7^{11}+7^4+7^1=1`977`329`151$ символов в среднем.

Или вот в том же алфавите слово "АРАРА":
AРАРА
__АРАРА
____АРАРА
101010
Ответ: $101010_7=17157$.

У меня остаётся только один большой вопрос: как можно догадаться до этого решения в короткое время самостоятельно не прибегая к производящим функциям? Или же эта задача на математическую эрудицию?

-- 20.01.2018, 14:38 --

(Оффтоп)

--mS-- Ещё раз большое СПАСИБО за предоставленные материалы. Ни за что бы сам не догадался до решения.

[atlakatl]

Вместо алфавита используем 10 цифр, считать удобнее. Искомый кортеж $K$ пусть тоже составляет 10 символов. Да хоть 10 нулей.
Имеется случайная последовательность длиной $L$. Какова вероятность, что в ней встретится $K$?
Последовательно прикладываем $K$ началом к каждому символу $L$. И смотрим, совпали ли кортеж и находящийся под ним отрезок $L$. Таких попыток $(L-K+1)$.
Таким образом, задача свелась к подсчёту вероятности, что кортеж встречается в последовательности. Если $P=0,5$, то можем ли мы утверждать, что длина $L$ и есть искомый ответ?
В $L$ с равной вероятностью могут встретиться $10^{10}$ видов отрезков. Тогда $L=1/2 \cdot 10^{10}$, то бишь 5 млрд.
Что-то слишком просто получается. Где я ошибаюсь?
Можно пробить эту схему на компе. ГСЧ выдаёт цифры. Программа их считает и ждёт, когда встретятся подряд 10 нулей.

[B@R5uk]

atlakatl в сообщении #1285943 писал(а):

Можно пробить эту схему на компе. ГСЧ выдаёт цифры.

Попробуйте. Только алфавит стоит взять по-меньше, а слово по-короче, иначе средняя длительность чтения ГСЧ выйдет гигантской, а её дисперсия — ещё больше.

Я на 146% уверен, что моё решение выше правильное даже не потому, что я его вывел из более общего случая, предложенного в статье на прошлой странице, а потому что я это проверил, сдав программу на соответствующую задачу. Я на том сайте типа программировать учусь заочно. Но эта конкретно задача из той серии, где надо напрячься и вывести формулу, а потом просто оформить эту формулу в виде коротенькой программки. Вот поэтому меня и мучает вопрос: КАК??? Как может старшеклассник/студент начальных курсов, профиль которого не матан и физика, а программирование, вывести эту формулу самостоятельно в кратчайшие сроки? Теорвер начинается с 3-го курса и по хорошему тянется семестра 3-4. Производящие функции вводятся даже не в первых двух, если мне память не изменяет (но я был плохой студент, так что могу ошибаться).

[arseniiv]

А вы уже смотрели книжку Кнута, Грэхема, Паташника «Конкретная математика»? Там есть и дискретная вероятность (что полегче общего случая — например, можно особо не задумываться об алгебре событий, т. к. в таком случае обычно достаточно взять сразу весь булеан множества элементарных исходов), и производящие функции. Разделы о них, конечно, пользуются данными о преобразованиях выражений с суммами и прочими вещами из предыдущих разделов, где может быть временами сложно продраться, но я верю, что не обязательно разбирать там абсолютно всё предыдущее. А тогда чтение выглядит вполне подъёмным для неискушённых.

[B@R5uk]

arseniiv в сообщении #1285963 писал(а):

А вы уже смотрели книжку Кнута, Грэхема, Паташника «Конкретная математика»? Там есть и дискретная вероятность

Книжку смотрел, разумеется. Там эта задача решается только для алфавита из двух символов: "орёл" и "решка". И она тоже решается через производящие функции. Потом начались какие-то обобщения процесса решения, и я потерял ход мысли. А дискретная вероятность тут везде: и в исходной задаче, и в той, что решается в статье Александра Соловьёва.

[atlakatl]

Прогнал программу на поиск строки в 10 символов, алфавит 10 цифр, 10 попыток.
В среднем получилось $L=1356090673,2$
В теории должно получиться 5 млн., на практике в 3,7 раз меньше. Надо подумать.

[Someone]

atlakatl в сообщении #1285973 писал(а):

В теории должно получиться 5 млн., на практике в 3,7 раз меньше.

А среднее квадратичное отклонение какое?

[atlakatl]

Someone в сообщении #1285977 писал(а):

среднее квадратичное отклонение какое?

Специально не считал, по прикидкам 500 000 где-то.

[B@R5uk]

atlakatl в сообщении #1285973 писал(а):

Прогнал программу на поиск строки в 10 символов, алфавит 10 цифр, 10 попыток.

10 попыток маловато. А можно текст вашей программы?

[arseniiv]

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

Потом начались какие-то обобщения процесса решения, и я потерял ход мысли.

А, так там даже эта задача рассматривается? Неплохо! Я-то в общем говорил, насчёт части

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

Вот поэтому меня и мучает вопрос: КАК??? Как может старшеклассник/студент начальных курсов, профиль которого не матан и физика, а программирование, вывести эту формулу самостоятельно в кратчайшие сроки? Теорвер начинается с 3-го курса и по хорошему тянется семестра 3-4. Производящие функции вводятся даже не в первых двух, если мне память не изменяет <…>.

Дескать, не всё так плохо.

[atlakatl]

Используется синтаксис Pascal

//Когда в последовательности встретится s нулей?
var
  nHodS: uint64;
  s, s1, k, nSer: byte;

begin
  nHodS := 0;
  s := 10; //Длина строки
  k := 10; //Букв в алфавите
  nSer := 10; //Экспериментов
  var ver := 1 / k;
  for var i := 1 to nSer do
  begin
    var nHod := 0;
    s1 := 0; //Текущее число нулей
    repeat
      if random < ver then inc(s1) else s1 := 0;
      inc(nHod);
    until s1 = s;
    nHodS += nHod;
    writeln('i=', i, ', ходов=', nHodS / i ); //Чтоб динамику счёта видеть
  end;
  writeln('Ходов=', nHodS / nSer);
end.
 

На ноуте она считала где-то час.

[Dmitriy40]

Я тоже сбацал программку на Delphi для алфавита из 8-ми цифр и слова длиной 8 символов, запустил ... Генератор случайных чисел оказался периодичен с периодом около $2^{32}$, это примерно 250 попыток. Среднее значение получилось порядка 17млн, среднее квадратичное отклонение практически равно ему же. Разброс значений огромный (несколько попыток из 250 вылетали за 40млн). Запускал несколько сотен раз, цифры немного менялись, факт почти равенства оставался. Считалось минут 10, ещё столько же рисовал график в Excel и считал им среднее и отклонение. Веры ей нет. Искать нормальный ГСЧ не стал, всё грохнул.

[arseniiv]

Если всё ещё интересно, реализуйте простенький Xorshift, это можно сделать руками, там есть несколько готовых вариантов кода с разной максимальной длиной цикла.

[B@R5uk]

А я говорил брать алфавит и строку по-меньше!

[Dmitriy40]

arseniiv
Ага, спасибо, снова написал, уже на асме и под x64, взял ГСЧ с периодом $2^{1024}-1$, ну чтоб не париться.

Someone
B@R5uk
Алфавит из $10$ символов, ждём строку длиной $8$ нулей ($10$ слишком медленно, там нередки и десятки миллиардов итераций).
За 20 минут работы выполнено $3\,100$ попыток, минимум $20\,245$ итераций, максимум $874\,924\,888$ итераций, среднее $111\,925\,574{,}6$, стандартное отклонение $112\,433\,198{,}1$ (by Excel, среднее гармоническое $12\,804\,710{,}32$, медиана $77\,730\,239{,}5$) - т.е. снова практически совпадают. Причём и среднее и отклонение почти не скачут уже после нескольких сотен попыток. Так что веры такому тесту нет.