Вероятность встретить подстроку в строке

[незваный гость]

Задача связана с задачей о самой длинной подпоследовательности 0 (или 1) в строке очевидным образов: вероятность произвольной подстроки длины $l$ не может быть меньше чем фиксированной цепочки (одни 1).

Я рассматривал эту задачу давно, пишу, простите, по памяти. Если вероятность нужного исхода (1) равна $p$, то вероятность $P\{max \leq k\} \sim {\rm e}^{-n (1-p)p^{k+1}}$. Имеем очень симпатичную кривульку, однако.

Максимум достигается при $n (1-p) p^k = -\frac{\ln p}{1-p}$. То есть, он сдвигается как ${\rm O}(\log n)$. Плотность вероятности такого максимума $(1-p) p^{\frac{p}{1-p}}$. Легко вычислить и моменты распределения.

В нашем случае $p = \frac12$, и, соответственно, максимум достигается при $k = \log_2\frac{n}{4 \ln 2}$. Вероятность этого максимума равна $\frac14$.

[Willow]

незваный гость писал(а):

:evil:
Задача связана с задачей о самой длинной подпоследовательности 0 (или 1) в строке очевидным образов: вероятность произвольной подстроки длины $l$ не может быть меньше чем фиксированной цепочки (одни 1).

Во-первых: проблема в том, что не может быть больше - это слишком грубая оценка.
Во-вторых: я откровенно говоря не вижу такой уж непосредственной связи между самой длинной последовательностью из одинаковых символов и моей задачей. Ну предположим есть строка из 20-ти символов. И мы пытаемся оценить вероятность вхождение в нее 3-х символьной строки.
Да очевидно, что если взять случай когда короткая строка это "111", то больше всего она будет встречаться в строке у которой все 20 символов это "1". Но есть же еще строка "1110...1110" (пятикратное повторение одной группы).

[незваный гость]

1) Во-первых, приношу извинения. Лето, мозги сушатся на веревочке после купания… А я на форуме…

2) Существует некоторая неоднозначность условия задачи. А именно, что выбирается случайно: строка, подстрока или обе сразу. (Мы предполагаем равную вероятность всех выбираеммых случайно объектов).

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

3) Связь тем не менее есть: приведенная формула ( $P\{max \leq k\} \sim {\rm e}^{-n (1-p)p^{k+1}}$) позволяют ответить на вопрос о вероятности появления двух конкретных подстрок, $k$ нулей и $k$ единиц. А именно, для того, чтобы была подстрока длинной $k$ необходимо и достаточно, чтобы максимальное количество 0 подряд было больше или равно $k$. То есть, $p \approx 1-e^{-n (1-p) p^k}$, очевидно, монотонно возрастающая с уменьшением $k$. Последнее — очевидный тест; если мы нашли $k$ нулей, то всяко найдем $k-1$. Эта вероятность асимптотически корректна для больших $n$ и $k$, и хорошо согласуется с тестами методом Монте-Карло (выражению «оценка снизу» я придавал смысл, несколько отличный от Вас. Беда в том, что мой смысл смысла не имеет вовсе).

4) Все остальные выкладки в моем предыдущем сообщении — чушь, за которую я повторно извиняюсь . Хотя некоторые идеи остаются верными: например, квинтили $k$ растут как $\log n$. Собственно, она и вычислена для $k = \Theta(\log n)$. И при малых, и при больших $k$ ее точность ограничена, но значения мало отличаются от 0 или 1.

[PAV]

Вероятнее всего, имеется в виду, что независимо друг от друга случайно выбирается и строка, и подстрока. Пусть $n$ - длина строки, $x$ - строка, $m$ - длина подстроки, $m$ - подстрока. Введем функцию $I(x,y)$, которая равна 1, если $y$ входит в $x$, и 0 в противном случае. Тогда искомая вероятность равна

$$P=2^{-(n+m)}\sum_{x}\sum_yI(x,y)$$

Заметим, что если просуммировать только по $x$ (при фиксированном $y$), то это будет количество строк длины $n$, которые включают в себя $y$. Можно наоборот, сначала суммировать по $y$, это будет количество различных подпоследовательностей у заданной последовательности $x$.

Честно говоря, мне не кажется, что это удастся посчитать точно. Можно попытаться строить оценки или оценить численно.

[Willow]

Да я вполне мог бы пользоваться приближенной оценкой, мне главное чтобы знать точность этой оценки,

[PAV]

Это тоже не выглядит простым, требуется исследовать. Строить оценки сверху и снизу.

Для того, чтобы "на пальцах" понять, какой результат может быть получен, можно помоделировать методом Монте-Карло. Брать случайные строки и считать, сколько в них различных подстрок заданной длины. Примерно оценить распределение.

Обращаю внимание, что для длин строк порядка 10-15 (может быть больше) задачу вполне можно решить точно полным перебором.

[незваный гость]

Очень на пальцах, очень неформально, очень грубо:

В строке длины $n$ у нас $n-k+1$ подстрок длины $k$. Вероятность совпадения каждой из них со строкой поиска $2^{-k}$, a любой из них — (грубо) $\frac{n-k+1}{2^k}$. Значит, вероятность того, что строка найдена не будет, $1-\frac{n-k+1}{2^k}$.

Это, разумеется, очень упрощенная оценка. Разумеется, подстроки не независимы. Она также не учитывает «авто-подстрочность» (по аналогии с автокорреляцией) строки, которую мы ищем. Но мне кажется, что эти эффекты относительно малы.

В частности, поведение квинтилей дает их рост как $\ln n$. С другой стороны, эта оценка хорошо согласуется с точным асимптотическим решением при однородной строке.