Повторение букв

Имеется текст заданной длины на известном языке. Найти математическое ожидание и дисперсию числа повторений букв.

это по математике задачка или по информатике? нужен алгоритм или просто формула?

Вопрос сложный.... для меня. Конечно же хотелось иметь формулу.. А ведь есть науки кроме математики и информатики. По Нобелю математика вообще не наука, а язык. Что совсем не умаляет ее достоинств.

"Вы хотите об этом поговорить?" (с)

А что такое повторения букв?
ААА — это повторение или два?

Это три повторения. Так считают криптографы.

Три повторения потому что есть блоки АА, АА и ААА?
Или по какой-то еще причине?

Первая буква А совпадает со второй и третьей, вторая совпадает с третьей.
Можно посмотреть на Народ.ру."Параметры распределения числа повторений букв в тексте"

Ссылка для скачивания
http://narod.ru/disk/27891329001/%D0%9F%D0%B0%D1%80%D0%B0%D0%BC%D0%B5%D1%82%D1%80%D1%8B%20%D1%80%D0%B0%D1%81%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F%20%D1%87%D0%B8%D1%81%D0%BB%D0%B0%20%D0%BF%D0%BE%D0%B2%D1%82%D0%BE%D1%80%D0%B5%D0%BD%D0%B8%D0%B9%20%D0%B1%D1%83%D0%BA%D0%B2%20%D0%B2%20%D1%82%D0%B5%D0%BA%D1%81%D1%82%D0%B5.docx.html

Это задача , рассматриваемая в криптоанализе. Она имеет разные степени сложности в зависимости от принимаемой Вами модели текста. Простейшая модель-текст есть реализация полиномиальной схемы,когда считается , что буквы появляются независимо. Можно считать текст реализацией цепи Маркова, простой или сложной.
Решение в полиномиальной постановке для мат. ожидания не слишком сложное. Для дисперсии есть некоторые технико-математические сложности . Открытую ссылку затрудняюсь дать.

Вот для Вас выдержка из моих лекций.
Пусть имеется реализация объема n полиномиальной схемы с N исходами и известными вероятностями исходов p , i=1,2,…, N. Требуется найти математическое ожидание и дисперсию числа повторений исходов в этой реализации.
Проведем маркировку реализации, то есть подсчитаем частоты исходов в реализации r i=1,2,…, N. Тогда статистика числа повторений очевидно запишется в виде .
Теперь, используя определение математического ожидания, легко получить Е= .
Заметим, что для всех европейских языков с мощностью алфавита N=26 сумма практически константа и равна

К сожалению, индексы и формулы не копируются. Думайте теперь сами.

"Высылайте либретто, музыку подберём сами!" (с)

Прошла по ссылке, Там и индексы и формулы.Стала ясной математическая постановка. Но для меня не легко (как сказано в ссылке) получить полученную там формулу для математического ожидания. Можно ли привести подробный вывод?
А что означают послания г. Безбородова? Совсем не поняла.

Вот ссылка на народ.ру, где подробный вывод мат ожидания. С дисперсией сложнее.
http://narod.ru/disk/28032760001/%D0%9C%D0%B0%D1%82%20%D0%BE%D0%B6%D0%B8%D0%B4%D0%B0%D0%BD%D0%B8%D0%B5%20%D1%87%D0%B8%D1%81%D0%BB%D0%B0%20%D0%BF%D0%BB%D0%B2%D1%82%D0%BE%D1%80%D0%B5%D0%BD%D0%B8%D0%B9.jpg.html

Прошу извинить, уважаемая Наталья, за несмешные шутки.

1. (#4 по поводу #3) Думаю, что в исходной постановке задачи трудно перепутать алгоритм и формулу — тому, кто различает эти два понятия. А кто не различает — вполне может об этом, не стыдясь, сказать. (И не разводя лирику относительно места математики в системе научного знания.) Здесь люди с пониманием и тактом — тем, кто менее сведущ, объясняют обычно подробнее.

2. Математический текст, из которого по той или иной причине выпали формулы, чаще всего производит гротескное впечатление.

Рассказывают, что когда в Петербурге с громадным успехом в первый раз прошла оперетта Оффенбаха "Прекрасная Елена", в одесском театре решили повторить эту постановку и отправили в столичную театральную библиотеку запрос относительно стоимости оркестровки, партитуры и либретто оффенбаховской оперетты. Из Петербурга ответили, что оркестровка и партитура стоят 300 рублей, а либретто 50 копеек. Тогда одесский антрепренёр телеграфировал: "Высылайте либретто, музыку подберём сами".

(Хотя я в принципе могу понять уважаемого полковника, который так торопился помочь Вам, что пренебрёг встроенным в движок форума интерпретатором формул в формате [m]\TeX[/m])

, i=1,2,…, N. Требуется найти математическое ожидание и дисперсию числа повторений исходов в этой реализации.
Проведем маркировку реализации, то есть подсчитаем частоты исходов в реализации r[m]_{i}[/m] i=1,2,…, N. Тогда статистика числа повторений очевидно запишется в виде [m]\sum\limits_{i=1}^{n}{C_{{{r}_{i}}}^{2}}[/m].
Теперь, используя определение математического ожидания, легко получить Е= [m]\sum\limits_{i=1}^{N}{C_{n}^{2}}p_{i}^{2}[/m].
Заметим, что для всех европейских языков с мощностью алфавита N=26 сумма [m]\sum\limits_{i=1}^{26}{p_{i}^{2}}[/m] практически константа и равна 1/13.
Быть может, теперь вы сможете проявить себя как математик вместо неуместного здесь сарказма.

А, так под повторением подразумевается просто число пар одинаковых букв в любых местах. Я-то воспринял повторение как подряд идущие буквы. Вот и унесло меня куда в сторону законов Эрдаша.Теперь понятно.
Тогда можно так и не крутиться, пожалуй, просто сказать, что искомая величина равна сумме величин I_{i,j}^k — индикаторов того, что на i-ом и j-ом месте одинаковые буквы, причем буквы вида k, k\leq N, i\neq j \in \{1...n\}
EI_{i,j}^k очевидно равно p_k^2
Всего наборов (i,j) при каждом k C^2_n, отсюда получаем ваш ответ.
И дисперсию посчитать несложно.
cov(I_{i,j}^k, I_{m,n}^l)=-p_k^2 p_l^2, если k\neq l и {i,j}, {m,n} пересекаются.
p_k^3 — p_k^4, если k=l и {i,j}, {m,n} пересекаются по 1 числу
p_k^2-p_k^4, если k=l и {i,j}={m,n}
В остальных случаях величины независимы и ковариация 0.
Отсюда имеем формулу
C^2_n \sum\limits_{k=1}^{N} (p_k^2-p_k^4) + 3 C^3_n \sum\limits_{k=1}^{N} (p_k^3-p_k^4)-3 С^3_n \sum\limits_{1\leq k\neq l \leq N} p_k^2 p_l^2
Или это можно переписать в виде
C^2_n \sum\limits_{k=1}^{N} (p_k^2-p_k^4) + 3 C^3_n \sum\limits_{k=1}^{N} p_k^3-3 С^3_n (\sum\limits_{k=1}^{N} p_k^2)^2

P.S. Файл ваш не открылся, потому что docx мой древний офис не читает.

Надо тег [m]писать, я так понял?
Тогда можно так и не крутиться, пожалуй, просто сказать, что искомая величина равна сумме величин [math]I_{i,j}^k[/m] — индикаторов того, что на i-ом и j-ом месте одинаковые буквы, причем буквы вида [m]k, k\leq N, i\neq j \in \{1...n\}[/m]
[m]EI_{i,j}^k[/m]очевидно равно [m]p_k^2[/m]
Всего наборов (i,j) при каждом k C^2_n, отсюда получаем ваш ответ.
И дисперсию посчитать несложно.
[m]cov(I_{i,j}^k, I_{m,n}^l)=-p_k^2 p_l^2[/m], если [m]k\neq l[/m] и {i,j}, {m,n} пересекаются.
[m]p_k^3 — p_k^4[/m], если k=l и {i,j}, {m,n} пересекаются по 1 числу
[m]p_k^2-p_k^4[/m], если k=l и {i,j}={m,n}
В остальных случаях величины независимы и ковариация 0.
Отсюда имеем формулу
[m]C^2_n \sum\limits_{k=1}^{N} (p_k^2-p_k^4) + 3 C^3_n \sum\limits_{k=1}^{N} (p_k^3-p_k^4)-3 С^3_n \sum\limits_{1\leq k\neq l \leq N} p_k^2 p_l^2[/m]
Или это можно переписать в виде
[m]C^2_n \sum\limits_{k=1}^{N} (p_k^2-p_k^4) + 3 C^3_n \sum\limits_{k=1}^{N} p_k^3-3 С^3_n (\sum\limits_{k=1}^{N} p_k^2)^2[/m]

А что такое N с волной? Это может быть число сочетаний?

Если навести, то видно что там C. Видимо, я раскладку не переключил, а распозналась русская С как N с волной :)
Да, число сочетаний.

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

Я думаю, что все же Ваш результат имеет ошибку. Из физических соображения ясно, что в случае равновероятной полиномиальной схемы дисперсия должна иметь биномиальный вид [m]C_{n}^{2}\frac{1}{N}(1-\frac{1}{N})[/m].
Проверьте, пожалуйста.
Ваш подход вполне подходит для моментов второго порядка. А если надо моменты высших порядков.?

Либо вам надо поделиться со мной соображениями, либо мне останется непонятно, что же не так, если что-то не так.
Моменты 3-ьего порядка считаются по тому же принципу, только там уже будет многовато случаев взаимного расположения пар.
Вместо ковариаций будут тройные произведения, это мало что меняет.
А вот 4ого я бы уже не взялся, да.
Но, с другой стороны, производящими функциями тут не очень подберешься, а других универсальных методов подсчета всех моментов в голову не приходит.

Вот моя дисперсия. Я это получал двумя способами:1) как ВЫ, 2) через нахождение мат ожидания квадрата статистики повторений
D=[m]C_{n}^{2}{{a}_{2}}(1-{{a}_{2}})+6C_{n}^{3}({{a}_{3}}-a_{2}^{2})[/m],
где [m]{{a}_{2}}=\sum\limits_{k=1}^{N}{p_{k}^{2}}[/m], [m]{{a}_{3}}=\sum\limits_{k=1}^{N}{p_{k}^{3}}[/m]

Ага, нашел ошибку.
Я не учел случай (i,j)=(m,n), k<>l
Он даст нам еще член
[m]-С^2_n\sum\limits_{k\neq l} p_k^2 p_l^2[/m]
Он-то и позволит нам получить вклад случая (i,j)=(m,n) в виде
[m]С^2_n a_2(1-a_2)[/m]
в вашей терминологии.
Ну а остаток у меня такой же как у вас с точностью до того, что у меня 3, а у вас 6. Правильно у вас, потому что чтобы выбрать 2 пары, в которых одно общее число, надо выбрать три числа, затем выбрать одно из них, которое повторится (3 способа) и выбрать, какая из пар на первом месте, какая на втором (2 способа). Последний множитель я потерял :(

Я хотел бы Вам (Александр Викторович) предложить продолжить эту тематику, у меня есть некоторые предложения. Если не будет возражений. Только это надо делать уже не здесь.

Спасибо, конечно, но у меня немножко другая специализация — случайные среды, большие уклонения, пока я в ней завяз по уши.
А предложения присылайте, может быть предложу их в качестве вариантов для курсовиков :)
ashklyaev@gmail.com

Было обсуждение сна семинаре. Рекомендовали ввести следующее определение повторения букв: будем называть j-повторением букв событие, состоящее в том, что на некоторых j местах текста стоят одинаковые буквы. Ранее было j=2. Теперь надо такой общий случай. С мат. ожиданием разобралась по аналогии. А с дисперсией теперь совсем сложно. А еще есть вопрос о том, каково же распределение и тогда моменты любого порядка.

В дисперсии то же самое. Вводим [m]I^i_{k,l,m}[/m] по тем же принципам и считаем ковариации
[m]cov(I^i_{k,l,m}, I^s_{r,p,q})[/m]
Если наборы не пересекаются, то величины не коррелируют.
Если пересекаются, а i и s разные, то это просто произведение матожиданий I со знаком минус.
Если пересекаются, а i, s одинаковые, то разбираются три случая — пересечение по 1, по 2 или по 3.
Перебор предоставляю вам.
Наверное, можно и для общих j среднее и дисперсию получить из этих соображений, только формула будет противная.

А вот с распределением, думаю, плохо дело.
Если, конечно, вас не устроит ответ
[m]P(X=k)=\sum\limits_{i_1,...,i_n\in \{1....N\}: \sum_{0< m < l< r\leq n: i_r=i_l=i_m} 1 =k} \prod\limits_{j=1}^{n} p_{i_j}[/m]

Видимо, мои вопросы слишком сложны для данного сайта или ....

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

Фактически мне нужен научный руководитель. Я живу в Штуттгарте, а учусь в российском ВУЗе. В Германии трудно найти математика с квалификацией. Российский 3-ий курс по вероятности, статистике, комбинаторике- это их аспирантура.

В том ВУЗе, в котором вы учитесь, вам и надо искать себе научного руководителя, готового общаться по интернету, скайпу или вроде того.

В моем направлении теории вероятностей и случайных процессов в Германии работают одни из лучших ученых в мире (более того, они немцы).

Найти математическое ожидание М(x) и дисперсию D(x) дескретной случайно величины x, имеющей следующий закон распределения:
x 1 4
p 0,4 0,6

Против течения паром двигается со скоростью х км/час, а по течению в 2 раза больше. Запишите на математическом языке.

Составить закон распределения вероятностей д.с.в. X. Построить многоугольник распределения. Найти числовые характеристики распределения (моду распределения, математическое ожидание M(X), дисперсию D(X), среднее квадратическое отклонение Б(X)).

Два стрелка поражают мишень с вероятностями, соответственно, 0,8 и 0,9 (при одном выстреле), причем первый стрелок выстрелил один раз, а второй – два раза. Д.с.в. X – общее число попаданий в мишень.

Время падения камня t с горы измерено приближенно, причем t (9;11) . Рассматривая время как случайную величину t равномерно распределенную на интервале (9,11), найти математическое ожидание и дисперсию высоты горы h (считать падение камня равноускоренным: h=gt^2/2, g –const.)

Помогите, пож-та, решить:

Случайная величина х в интервале [0;2] задана плотностью распределения f(х) = aх2 (в квадрате). Вне этого интервала f(х) = 0. Найти моду, медиану, математическое ожидание и дисперсию случайной величины х, коэффициента а

Заранее спасибо за помощь!