Портал функционирует при финансовой поддержке Министерства цифрового развития, связи и массовых коммуникаций.

Выбрать дату в календареВыбрать дату в календаре

Страницы: Пред. 1 2 3
число"Пи", почему отношение пл круга к пл сферы 1\4?
[QUOTE]BETEP IIEPEMEH пишет:
Цитата dr.Watson пишет: Отсюда рекуррентность: Q(n)=d*Q(n-1)+(d-1)*(d^(n-q)-Q(n-q)) Поясните ее, пожалуйста, этот результат не так уж и очевиден. [/QUOTE]
Если Q(n) – количество q-угодных n-членных последовательностей, то d^n-Q(n) – количество q-неугодных.
При n>q рассмотрим n-членную q-угодную последовательность A. После удаления последней буквы получим последовательность A’. Эта последовательность либо q-угодна либо нет. В первом случае мы получаем, что A получена из q-угодной A’ приписыванием любой из d букв, что дает первое слагаемое в первое слагаемое d*Q(n-1) в рекуррентности. Во втором случае [B]q-неугодная[/B] A’ приписыванием [B]одной[/B] буквы становится q-угодной. Это означает, что A оканчивается на q одинаковых букв - в точности, то есть (q+1)-я буква с конца уже другая, иначе q-угодна A’. То есть A - результат приписывания q одинаковых букв к обрезанной с конца на q членов. Для приписывания имеем d-1 возможностей. Отсюда второе слагаемое (d-1)*(d^(n-q)-Q(n-q)).

Начальные условия для линейной рекуррентности очевидны: P’(1)= … =P’(q-1)=1, P’(q)=1-d^(1-q)
число"Пи", почему отношение пл круга к пл сферы 1\4?
[QUOTE]BETEP IIEPEMEH пишет:
Кстати, на эту тему предлагаю все-таки решить подобную задачу по комбинаторике, чтобы все было корректно и не было разночтений. Пусть у нас есть последовательность из 1000 цифр (от 0 до 9, естественно). Для каждой цифры 0..9 вероятность того, что она стоит в позиции n - одинакова (для каждого n от 1 до 1000). Какова вероятность того, что в этой длинной последовательности встретится короткая последовательность из 10 одинаковых цифр? А из 11-ти цифр 0?
Какие будут варианты решения?[/QUOTE]
Последовательность, состоящую из n букв в d-буквенном алфавите будем называть q-угодной, если хотя бы одна из букв содержится в последовательности не менее q раз подряд.
Пусть Q(n) – число всех n-членных q-угодных последовательностей.
При n>q любую из них можно получить одним из двух взаимно исключающих способов:
1) К q-угодной (n-1)-членной дописываем любую из d букв.
2) К q-неугодной (n-q)-членной последовательности дописываем q раз любую букву, отличную от последней буквы этой последовательности

Отсюда рекуррентность:

Q(n)=d*Q(n-1)+(d-1)*(d^(n-q)-Q(n-q))

Поделив на d^n (число всех n-членных последовательностей) получим рекуррентность для вероятностей q-угодности:

P(n)=P(n-1)+(d-1)*d^(-q)*(1-P(n-q))

Ясно что P(n) монотонно возрастающая и ограничена сверху единицей. Переходя к пределу при n -> oo, отсюда получим lim P(n)=1.
В принципе нет сложностей, кроме вычислительных, для нахождения P(n). Если перейти от P(n) к дополнительной вероятности q-неугодности P’(n)=1-P(n), то рекуррентность примет вид линейной:

P’(n)=P’(n-1) )-(d-1)*d^(-q)*P’(n-q)

И проблема только лишь в нахождении корней характеристического многочлена степени q.

Для q=2, к примеру, есть только одна проблема – отсутствие удобств для написания простейших формул, типа корней квадратного уравнения.
Страницы: Пред. 1 2 3
Портал журнала «Наука и жизнь» использует файлы cookie. Продолжая пользоваться порталом, вы соглашаетесь с хранением и использованием порталом и партнёрскими сайтами файлов cookie на вашем устройстве. Подробнее