Есть строка длины $%k$%, каждый из символов которой берется из множества $%\{A, C, G, T\}$% с вероятностями, $% p_A, p_C, p_G, p_T $% соответственно, $%0 \leq p_A, p_C, p_G, p_T \leq 1, p_A + p_C + p_G + p_T = 1 $%. Пусть есть фиксированная подстрока длины $% 1 \leq n \leq k $%, которая может состоять из тех же символов.

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

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

задан 22 Май '19 19:13

@Evgeny Kondr...: если речь идёт о вероятностях того, что число вхождений подстроки U в строку V равно заданному числу 0,1,2,... , то в возможность точного нахождения таких вещей без компьютера верится слабо. Если же речь о матожидании числа таких вхождений, то эта задача проще, и она решается без явного нахождения вероятностей.

(23 Май '19 5:28) falcao

@falcao, само собой надо найти мат.ожидание, как вы это поняли? В моем понимании как раз задача свелась к такой подзадаче, и да, она из программирования. Только в исходном варианте надо найти значение для набора подстрок. Как же это можно посчитать без вероятностей для заданного числа? Здесь же все дискретное.

(23 Май '19 6:17) Evgeny Kondr...

@Evgeny Kondr...: я просто знаю, что в такого рода задачах матожидание найти легко, а отдельные вероятности -- нет. То есть это как бы не "само собой", так как задачу можно ставить и такую, и этакую. Но у меня возникло предположение, что речь могла идти о матожидании. Его найти довольно легко с использованием свойства аддитивности, а знать вероятности отдельных событий при этом не требуется.

Если задача ставилась именно для матожидания, то желательно дать оригинал формулировки.

(23 Май '19 6:39) falcao

@falcao, из онлайн экзамена в ШАД - 2017, https://contest.yandex.ru/contest/8231/enter/, задача № 5. Так же вчера создал тему на http://www.cyberforum.ru/cpp-beginners/thread2457580.html

(23 Май '19 7:35) Evgeny Kondr...

@falcao, нет идей?

(23 Май '19 16:42) Evgeny Kondr...
10|600 символов нужно символов осталось
0

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

Начнём с частного случая, когда подстрока s всего одна. Пусть она имеет длину k. В случайном слове длиной n имеется n-k+1 вхождений подслова длиной k. Введём случайную величину X(i), которая равна 1, если подслово от i-й до (k+i-1)-й позиции равно s. Если не равно, то X(i)=0. Тогда сумма X(1)+X(2)+... (по i от 1 до n-k+1) показывает число вхождений s в случайном слове длиной n. Матожидание суммы равно сумме матожиданий. Для данного i величина MX(i) равна P(X(i)=1), то есть вероятности того, что заданное вхождение длиной k равно s. От i это значение не зависит, и равно произведению вероятностей букв. Например, для s=abacbd вероятность равна p(a)p(b)p(a)p(c)p(b)p(d), что легко вычисляется для каждой строки s. Обозначим эту величину через p(s). Она складывается с собой n-k+1 раз, где k=k(s) есть длина s. Это и будет искомое матожидание.

Если строк у нас несколько, то надо сложить величины вида (n-k(s)+1)p(s) по всем строкам заданного набора. Это даст матожидание числа "удачных" вхождений строк в силу всё того же принципа аддитивности.

ссылка

отвечен 23 Май '19 17:15

@falcao, один момент не могу понять. Вот с какой-то вероятностью подстрока длины 6, например, входит с 1 позиции, а с какой-то вероятностью с седьмой позиции. На каком моменте вы "убираете случаи", когда подстрока, опять же с какой-то вероятностью, входит дважды начиная с 1 позиции и с 7?

(23 Май '19 18:10) Evgeny Kondr...

@Evgeny Kondr...: я пользуюсь обычными математическими правилами, а именно тем, что матожидание суммы равно сумме матожиданий. Этот факт верен для любых случайных величин -- зависимых, независимых, и так далее. Тут суть в том, что те строки, куда s входит 1 раз, дают мне "средний" доход 1, а строки, куда s входит дважды (не важно, пересекаясь или нет), дают доход 2, и так далее. А средние доходы от разных источников суммируются независимо от их происхождения.

(23 Май '19 19:06) falcao

@falcao, то есть если проводить аналогию с подбрасыванием моентки, где вероятность выпадания орла одна треть, а решики две трети, получаем что при подсчете мат. ожидания при $%n$% бросаниях, мы рассматриваем каждую позицию оделтьно? Якобы на 1 позиции выпала треть орла и на второй так же, тогда за два броска у нас две трети орла, так что ли?

(23 Май '19 19:51) Evgeny Kondr...

@Evgeny Kondr...: я не вижу здесь особой аналогии -- там и там находится матожидание, и делается это по определению или при помощи свойств. Конечно, то, что Вы сейчас описали, верно -- при n бросаниях в среднем выпадает np=n/3 орлов.

(23 Май '19 20:19) falcao

@falcao, как же не видите? С первой позиции по n - k + 1 вы бросаете монету и происходит выпадение орла с вероятностью для подстроки, которую вы описали выше. Спасибо большое, вроде все прояснилось. Еще сразу удивился, почему в экзамене шесть задач элементарные как 2 + 2, а эта такая сложная.

(23 Май '19 20:39) Evgeny Kondr...

@Evgeny Kondr...: какая-то аналогия тут, несомненно, есть, так как в обоих случаях находится матожидание. Но я сказал, что нет особой аналогии, то есть чего-то такого, что пришло бы в голову каждому и что-то принципиально прояснило бы происходящее. Само свойство аддитивности матожидания стандартно.

(23 Май '19 20:57) falcao
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×3,000
×56

задан
22 Май '19 19:13

показан
266 раз

обновлен
23 Май '19 20:57

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru