Вероятность встречи подстроки n раз

Для начала нужно определиться с терминологией. Вероятность не может быть у подстроки. Вероятность бывает только у события. Например, вероятность вхождения заданной наперед подстроки в некоторую случайную строку. Если мы говорим о случайной строке - нужно определиться, каким распределением вероятности контролируется эта строка, известно ли это распределение, если нет (что скорее всего), - можно ли сделать в его отношении какие-либо предположения.

Если же речь идет о том, чтобы ОЦЕНИТЬ вероятность (т.е. по данным), то это задача еще более сложная и требует еще большего количества уточнений. Если бы в наличии была выборка строк, по которым можно было бы посчитать частоту вхождения в них подстроки, - можно было бы оценить вероятность вхождения подстроки в случайную строку этой частотой (которую, очевидно, можно вычислить). Частота бралась бы по всей выборке. Но если выборка состоит из одного единственного значения случайной строки, - в этих условиях необходимо иметь очень конкретные сведения о распределении вероятностей, которым контролируется эта случайная строка.

> Вероятность не может быть у подстроки.

Я понимаю. С подбрасыванием монет, бросанием кубика и т.д. все понятно. А вот со строками и подстроками что-то как-то не понятно...

Начну из далека: Есть алфавит a, b, c, для каждой буквы задана своя вероятность (вероятность события выпадения соответствующий буквы) p(a), p(b), p(c). p(a)+p(b)+p(c)=1. Есть строка abbcb. Если я буду случайно генерировать пятибуквенные строки с заданными p(a), p(b), p(c), то вероятность того, что очередная строка будет abbcb — произведение вероятностей соответствующих букв.

Предположи, я буду генерировать пятибуквенные строки сериями по 1000 штук. То вероятность появления строки abbcb в 1000 независимых испытаниях m раз можно посчитать, например, с помощью формулы Пуассона. Тут вроде понятно. А вот как считать вероятность если это не 1000 независимых испытаний, это строка из 1000 букв???

Может, тебя устроит матожидание величины n? Это гораздо проще. ;-)

подстрока состоит из букв, вероятность её появления = произведению вероятностей появления нужной буквы на нужном месте... короче, как поток событий, только он может быть нестационарным. Строка с достаточным числом символов может и не появится.

строка в 1000 букв s

p(a)*p(b)*p(c) + p(~a)*p(a)*p(b)*p(c) + p(~a)^2*p(a)*p(b)*p(c) + ... + p(~a)^(1000-3+1)*p(a)*p(b)*p(c)

p(~a) - вероятность непоявления a
наверное как-то так, но что-то, мне кажется, я не додумал

> только он может быть нестационарным

А что это значит?

Понятно. Почитайте про цепи Маркова, думаю что это именно то что Вам нужно. Излагать прямо здесь эту теорию будет довольно затруднительно.

Ну если также из далека. Есть конечный алфавит S, для каждой буквы которого задана вероятность ps: S->R, такая что

сумма ps(a) по всем a из S равна 1;

ps(a) > 0;

Искомое вероятносное пространство: множество последовательностей строк алфавита S длинной N=1000;

Вероятносная мера: p(w) = произведение p(a)^weight(a,w) по всем a из S

где

weight (a,w) = количество вхождений символа a в строку w.

Собственно вероятность события что w содержит K вхождений строки s есть

сумма p(w) по всем w, удовлетворяющим этому критерию

К вопросу как посчитать. Задача конечно зверЪ. Фишка в том, что врождения строк могут перекрываться (например "aaa" содержит 2 вхождения строки "aa"). Если считать по определению, то нереально (экспоненциальное время). Кажется можно наваять алгоритм, который работает

(K*N)^(3*m) + время построение автомата.

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

>Может, тебя устроит матожидание величины n? Это гораздо проще. ;-)

Как ее найти, если не секрет?

Ну как бы:
http://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8...

> Фишка в том, что врождения строк могут перекрываться (например "aaa" содержит 2 вхождения строки "aa").

А если предположить, что они не перекрываются.

>>Может, тебя устроит матожидание величины n? Это гораздо проще. ;-)

>Как ее найти, если не секрет?

матожидание такое же, как в случае, если строки не перекрываются.

Если вероятность того, что вся строка из K букв совпадёт с искомой строкой (длиной те же K букв), есть P, то матожидание числа совпадений этой подстроки в строке длиной N (с той же статистикой) будет P*(N-K+1)/K. (N-K+1 - это число позиций, в которых подстрока могла бы оказаться в строке).

Пояснение этому простое - M(f+g) = M(f) + M(g), и поэтому ей всё равно, зависимы функции f и g или нет.

Понял. Действительно просто. Только там делить на ка не надо.

Просто P*(N-K+1)

>А если предположить, что они не перекрываются.

Еще немного подумал, и понял, что и так тоже не менее сложно.

> матожидание такое же, как в случае, если строки не перекрываются.

> Если вероятность того, что вся строка из K букв совпадёт с искомой строкой (длиной те же K букв), есть P, то матожидание числа совпадений этой подстроки в строке длиной N (с той же статистикой) будет P*(N-K+1)/K. (N-K+1 - это число позиций, в которых подстрока могла бы оказаться в строке).

> Пояснение этому простое - M(f+g) = M(f) + M(g), и поэтому ей всё равно, зависимы функции f и g или нет.

Разясни пожалуста, а то что-то на примере не работает:

Вот пример:

Алфавит бинарный p=0.5

N=3,

K=2,

строка="11",

Sample space: S:={1,0}

Probability space: O:={(a,b,c): a,b,c \in {1,0}}

Random variable: Х:0->S мах количество не перекрывающихся совпадений:

\forall o \in O P(o)=1/8,

P({X=1}) = P(1,1,0)+P(0,1,1)+P(1,1,1)=3/8

E[X]=1*P(X=1)+0*P(X=0)=3/8,

по твоей формуле:

Е[X]=1/4*(3-2+1)/2=1/4

R

Я тебя тоже не совсем понял. Кажется, мы разбираем разные задачи.

Во-первых, у меня ошибка, ival её (выше) уже поправил: "P*(N-K+1)".

Во-вторых, я рассматриваю матожидание числа x = "сколько раз встретится данныя подстрока", а не матожидание y = "встретится строка хоть один раз или нет". (Именно так я понял, о чём речь в исходной задаче - найти распределение x).

У тебя получилось My = 3/8. Учитывая, что в исходе (1,1,1) получается y=1, x=2, то ясно, что Mx = 4/8.

Если учесть мою ошибку (thnx to ival), у меня тоже получается Mx=1/2.

Вроде, всё сходится.

PS. сорри за задержку с ответом.

>Во-вторых, я рассматриваю матожидание числа x = "сколько раз встретится данныя подстрока", а не матожидание y = "встретится строка хоть один раз или нет". (Именно так я понял, о чём речь в исходной задаче - найти распределение x).

Я тоже, просто у меня в премере подстрока "11" в строке (n1,n2,n3) может встретится только один раз. Но таких строк три. Посмотри ещё раз на формулу: E[X]=1*P(X=1)+0*P(X=0)=3/8. Это же тот же интеграл \int_{O} X(o) dP(o) = \int_R x dP^X(x)

> Если учесть мою ошибку (thnx to ival), у меня тоже получается Mx=1/2.

Ну всеровно 1/2 != 3/8.

>У тебя получилось My = 3/8. Учитывая, что в исходе (1,1,1) получается y=1, x=2, то ясно, что Mx = 4/8.

а что здесь х, и что здесь у?

>PS. сорри за задержку с ответом. Без проблем. Я не тот анонимус каторый задал вопрос. Поэтому я подписался "R", мне просто задачка понравилась :). Сорри за английские обозначения, я математику не в России учил.

R.

> а что здесь х, и что здесь у?

x = "сколько раз встретится данная подстрока" (в исходе (111) x=2, в исходах (110) и (011) x=2, в остальных 5 исходах x=0),

y = "1, если строка встретится хотя бы один раз; 0, если строка не встретится ни разу" (в 3 исходах y=1, в 5 исходах y=0).

P(x > 0) = P(y > 0) = 3/8.

Mx = 0*P(x=0) + 1*P(x=1) + 2*P(x=2) = 0 + 1*2/8 + 2*1/8 = 1/2.

My = 0*P(x=0) + 1*P(x>1) = 0 + 1*2/8 + 1*1/8 = 3/8.

Не знаю, что такое E, наверное, тоже мат.ожидание. Да и int_R и P^X мне не понятны, наши теоретики пишут как-то так: M x = \int x dP. Думаю, использованные выше дискретные термины P(condition) и M(expression) более общеприняты :)

>My = 0*P(x=0) + 1*P(x>1) = 0 + 1*2/8 + 1*1/8 = 3/8.

>Не знаю, что такое E, наверное, тоже мат.ожидание. Да и int_R и P^X мне не понятны, наши теоретики пишут как-то так: M x = \int x dP. Думаю, использованные выше дискретные термины P(condition) и M(expression) более общеприняты :)

Мы просто Х разные использовали. Я посчитал что в (1,1,1) строка "11" поместица без перехлёстывания только один раз. А ты счетаешь что в (1,1,1) "11" помещяется два раза. Поэтому и результаты разные.

Разяснение: Е это Expected value судя по википедии действительно "Математическое ожидание". Да и формулы у нас одинаковые \int x dP это и есть \int_{R} x dP^{X} (x) просто я интеграл Лебега на бсём значении функции Х через "Pushforward measure" (к сожалению не нашёл перевода) сделал. Так вродебы проще ошибки искать, если всё точно записать ;). Я просто формулы как в латехе написал.

Спасибо за разьяснение.

R

> без перехлёстывания

Да, действительно. Я об этом даже не подумал. Хотя на практике часто интересен как раз твой случай, "поиск без перехлёстывания".