Вероятность совпадения части двух последовательностей н.с.в.

[nibble]

У нас есть две последовательности независимых случайных величин:
$a_1$ ... $a_n$ и $b_1 ... b_n$
Каждая случайная величина $a_i$ и $b_i$ может с равной вероятностью принимать значения $0$ и $1$.
Длина $n$ фиксирована.

Нужно найти вероятность того, что найдётся подпоследовательность длины k, присутствующая в обоих последовательностях. То есть:
$P( \exists m: a_i = b_i, \forall i \in [m, m+k] ) = ?$

Казалось бы, простая задача, но никак не могу сообразить решение.
Пробовал выделить всевозможные пары подпоследовательностей из $a$ и $b$ и искать ответ умножая кол-во пар на вероятность совпадения пары. Но эти события не независимы, поэтому способ неудачный.

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

Буду признателен за любую наводку!
Спасибо.

[gris]

Подпоследовательность длины $k$ должна начинаться с одного и того же номера в двух последовательностях? То есть правилен формализованный вопрос?
Можно начать с крайнего случая. Если $k=n$, то ответ — ?
Он совпадает с верояностью получить, например, в $b$ все нули.

Вообще, мы можем считать последовательность $a$ заданной, а считать вероятность того, что в случайной последовательности $b$ будет совпадение длины $k$. Так это или нет?

А можем ли мы считать $a$ заданной определённым образом?

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

[nibble]

Прошу прощения, я, конечно, ошибся. Подпоследовательность может начинаться с разных номеров. То есть, формально:
$P( \exists m, t: a_i = b_j, \forall i \in [m, m+k], j \in [t, t+k] ) = ?$

Если $k=m$, то ответ, очевидно, $2^{-n}$.

Думаю, считать $a$ заданной определённым образом мы не можем. Очевидно, при $k=1$ для $a=00$ и $a=01$ вероятности будут разные.

Если ввести третью последовательность, она будет так же случайна и задача будет сведена к поиску подпоследовательности из $k$ идущих подряд нулей. Но как найти вероятность встретить $k$ нулей подряд я не могу сообразить.
А если соображу, как потом расширить задачу до моего случая, когда подпоследовательности могут начинаться с разных номеров?

[Cash]

А почему вы решили, что члены подпоследовательности идут подряд?
Если разрешить подпоследовательностям быть "обычными" подпоследовательностями - задача только упростится.

[gris]

Кстати для понимания. Если подпоследовательность должна начинаться с одного номера, то мы на самом деле можем задать первую произвольным образом, например единичками. Тогда вторая и будет последовательностью-индикатором различий. Надо найти вероятность того, что в ней встретится $k$ единиц подряд — Вы совершенно правильно сказали. Но это, получается, другая задача.
Размечтался: вот если бы последовательности были циклическими, то мы могли бы вторую сдвигать и смотреть, не встретится ли совпадение первых $k$ номеров.

[nibble]

Допустим, мы умеем решать задачу для векторов длины $n$ и подпоследовательностей, начинающихся с одного и тот же номера. Обозначим решение задачи через $p_n$:

$$P( \exists m: a_i = b_i, \forall i \in [m, m+k], m+k<n ) = p_n$$

Тогда для решения более сложной задачи задачи обозначим:

$$P( \exists m, t: a_i = b_j, \forall i \in [m, m+k], j \in [t, t+k] , m+k<n, t+k<n) = P_n$$

Нам нужно сдвигать один из векторов на единичку до тех пор, пока мы не переберём все номера, с которых может начинаться подпоследовательность. С учётом того, что вектор при этом становятся короче и предположив, что испытания независимы, получим:

$$P_n = \prod_{i=1}^n p_i$$

Верно? Испытания действительно независимы? Мы можем их умножать? Это ведь нужно доказать?
И как искать вероятность встретить $k$ единиц в векторе длины $n$?

[--mS--]

Испытания независимы, а вот события, вероятности которых Вы перемножаете, разумеется, зависимы. Поскольку построены по одним и тем же случайным величинам. Да и вообще непонятно, почему что-то нужно умножать: искомое событие есть объединение, но никак не пересечение событий:

$$ A = \bigcup_{i=0}^{n-k}\bigcup_{j=0}^{n-k}\left\{a_{i+1}=b_{j+1},\,a_{i+2}=b_{j+2},\ldots,a_{i+k}=b_{j+k}\right\}. $$

Может, формула включения-исключения поможет?

[nibble]

Конечно, я написал глупость, а имел в виду совсем другое. Я хотел найти вероятность того, что подстроки ни разу не совпали. Тогда получилось бы событие, обратное к тому, что нам нужно.

$$P_n = 1 - \prod_{i=1}^n (1 - p_i)$$

Так нельзя, потому что события зависимы?

По формуле включения-исключения я должен просуммировать все $p_i$, а потом отнять от этого вероятность того, что события, соответствующие некоторым $p_i$ наступят одновременно. Я правильно понимаю? Но тогда, если события зависимы, у меня возникнет аналогичная проблема.

[--mS--]

Вероятности событий, из которых составлено вот это объединение

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

$$ A = \bigcup_{i=0}^{n-k}\bigcup_{j=0}^{n-k}\left\{a_{i+1}=b_{j+1},\,a_{i+2}=b_{j+2},\ldots,a_{i+k}=b_{j+k}\right\}, $$

находятся легко и просто. Как и вероятности пересечений таковых событий. Вот только слагаемых много, и пересечения у них разные, и от индексов зависят. Ответ обозримым заведомо не будет. Советую получать отчет численным моделированием, будет гораздо быстрее.

[usv99]

Всё-таки совет численного моделирования - здесь совсем от напрасных дебрей.
Немного подправленная схема Бернулли может выглядеть так.
1) Первый - простейший - вопрос nibble о вероятности совпадения с одинакового m-го места (в a и b) k шт. нулей или единиц подряд. Это 2^(-k) на количество таких k-мест, т.е. на n-k.
2) Второй - если с m-го в , с t-го в b. Количество таких k-мест увеличивается в n-k раз, т.е. предыдущая вероятность увеличивается в n-k раз.
3) Если "успех" не 1/2, а другие, то меняйте 2^(-k) на произведение этих других.
4) Если k-тки не одна, а ещё совпадающие r-ки, то сколько таких мест?
Вроде бы так?

[nibble]

Давайте остановимся на простейшем варианте задачи. Когда совпадающая подпоследовательность начинается с одного и тот же индекса и в $a$ и в $b$.
Если фиксировать индекс, то вероятность будет равна $2^{-k}$. Индексов может быть $n-k+1$ штук. Значит, для полной неудачи должно случиться $n-k+1$ неудач и мы получим ответ:

$$p_n = 1 - (1 - 2^{-k})^{n-k+1}$$

usv99 это имел в виду? Это верно? События сравнения последовательностей начиная с разных индексов независимы?

-- Чт мар 07, 2013 14:36:00 --

По логике usv99 при переходе к более сложной задаче, когда индексы могут не совпадать, кол-во экспериментов просто увеличивается в $n-k+1$ раз и мы получамем формулу:

$$P_n = 1 - (1 - 2^{-k})^{(n-k+1)(n-k+1)}$$

Это первое, до чего я додумался, пока решал сам. Но такое решение неверно из-за зависимости событий.

Возьмём для примера $n=2$ и $k=1$. В таком случае правильный ответ $\frac {14} {16}$ (из 16 пар только в двух не будет совпадений: $(00, 11)$ и $(11, 00)$).
Но по формуле мы получим $\frac{15}{16}$. Ошибка связана с тем, что последнее четвертое испытание ($(n-k+1)(n-k+1) = 4$) полностью зависит от предыдущих трёх. А мы в своей формуле этого не учли.

[--mS--]

О, господи... Один складывает вероятности совместных событий, другой перемножает вероятности зависимых событий. Я пас.

[AKM]

usv99,

на форуме есть Правила. В частности, здесь рассказано, как набирать формулы (здесь подробнее)

[Deggial]

Сообщения usv99 отделены

[usv99]

Повторюсь, что задачка nibble имеет "программёрские" приложения, ...

Toucan:

Удалено. См post703651.html#p703651