|
Есть строка длины $%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 
Bazalt |
|
Конечно, эта задача решается без подсчёта вероятностей отдельных событий типа того, что количество "удачных" вхождений равно тому или иному числу. Начнём с частного случая, когда подстрока 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 @falcao, один момент не могу понять. Вот с какой-то вероятностью подстрока длины 6, например, входит с 1 позиции, а с какой-то вероятностью с седьмой позиции. На каком моменте вы "убираете случаи", когда подстрока, опять же с какой-то вероятностью, входит дважды начиная с 1 позиции и с 7?
(23 Май '19 18:10)
Bazalt
@Evgeny Kondr...: я пользуюсь обычными математическими правилами, а именно тем, что матожидание суммы равно сумме матожиданий. Этот факт верен для любых случайных величин -- зависимых, независимых, и так далее. Тут суть в том, что те строки, куда s входит 1 раз, дают мне "средний" доход 1, а строки, куда s входит дважды (не важно, пересекаясь или нет), дают доход 2, и так далее. А средние доходы от разных источников суммируются независимо от их происхождения.
(23 Май '19 19:06)
falcao
@falcao, то есть если проводить аналогию с подбрасыванием моентки, где вероятность выпадания орла одна треть, а решики две трети, получаем что при подсчете мат. ожидания при $%n$% бросаниях, мы рассматриваем каждую позицию оделтьно? Якобы на 1 позиции выпала треть орла и на второй так же, тогда за два броска у нас две трети орла, так что ли?
(23 Май '19 19:51)
Bazalt
@Evgeny Kondr...: я не вижу здесь особой аналогии -- там и там находится матожидание, и делается это по определению или при помощи свойств. Конечно, то, что Вы сейчас описали, верно -- при n бросаниях в среднем выпадает np=n/3 орлов.
(23 Май '19 20:19)
falcao
@falcao, как же не видите? С первой позиции по n - k + 1 вы бросаете монету и происходит выпадение орла с вероятностью для подстроки, которую вы описали выше. Спасибо большое, вроде все прояснилось. Еще сразу удивился, почему в экзамене шесть задач элементарные как 2 + 2, а эта такая сложная.
(23 Май '19 20:39)
Bazalt
@Evgeny Kondr...: какая-то аналогия тут, несомненно, есть, так как в обоих случаях находится матожидание. Но я сказал, что нет особой аналогии, то есть чего-то такого, что пришло бы в голову каждому и что-то принципиально прояснило бы происходящее. Само свойство аддитивности матожидания стандартно.
(23 Май '19 20:57)
falcao
показано 5 из 6
показать еще 1
|
@Evgeny Kondr...: если речь идёт о вероятностях того, что число вхождений подстроки U в строку V равно заданному числу 0,1,2,... , то в возможность точного нахождения таких вещей без компьютера верится слабо. Если же речь о матожидании числа таких вхождений, то эта задача проще, и она решается без явного нахождения вероятностей.
@falcao, само собой надо найти мат.ожидание, как вы это поняли? В моем понимании как раз задача свелась к такой подзадаче, и да, она из программирования. Только в исходном варианте надо найти значение для набора подстрок. Как же это можно посчитать без вероятностей для заданного числа? Здесь же все дискретное.
@Evgeny Kondr...: я просто знаю, что в такого рода задачах матожидание найти легко, а отдельные вероятности -- нет. То есть это как бы не "само собой", так как задачу можно ставить и такую, и этакую. Но у меня возникло предположение, что речь могла идти о матожидании. Его найти довольно легко с использованием свойства аддитивности, а знать вероятности отдельных событий при этом не требуется.
Если задача ставилась именно для матожидания, то желательно дать оригинал формулировки.
@falcao, из онлайн экзамена в ШАД - 2017, https://contest.yandex.ru/contest/8231/enter/, задача № 5. Так же вчера создал тему на http://www.cyberforum.ru/cpp-beginners/thread2457580.html
@falcao, нет идей?