[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, к примеру, есть только одна проблема – отсутствие удобств для написания простейших формул, типа корней квадратного уравнения.