Некомбинаторная комбинаторика

[AV_77]

Посмотрите NISP SP 800-22. Test for the Longest Run of Ones in a Block (section 3.4).
Ну и ссылки на литературу оттуда.

[DeBill]

wrest в сообщении #1158693 писал(а):

N=10 и L=3 должен получиться ответ 166/252 :)

А разве не 168/252 ?

[upgrade]

Сделал так:
Десять случайных чисел от $0$ до $1$.
Если меньше одной второй с.в. принимает значение ноль, если больше - единица.
Затем ищем в этом ряде из десяти случайных нулей и единиц кластер из трех единиц - суммируем идущие подряд три числа и если сумма равна трем, то ставим один.
Затем суммируем последние единицы и нули, если сумма не ноль, значит в ряде есть кластер из трех единиц.
Так вот из $1048575$ таких рядов кластер из трех единиц встречается в $532449$ раз т.о. вероятность существования кластера из трех единиц в десяти - $0,51$.
Для кластера $2$ единицы, вероятность существования в $10$-разрядном ряде - $0,86$
Где-то ошибся?

[wrest]

DeBill в сообщении #1158713 писал(а):

А разве не 168/252 ?

Вы правы, 168/252, что в свою очередь равно 2/3
Заодно уж, для N=10 приведу и остальные вероятности.
L=1, p=252/252=1
L=2, p=250/252=125/126
L=3, p=168/252=2/3
L=4, p=058/252=29/126
L=5, p=010/252=5/126

-- 11.10.2016, 12:32 --

upgrade в сообщении #1158836 писал(а):

Затем ищем в этом ряде из десяти случайных нулей и единиц кластер из трех единиц - суммируем идущие подряд три числа и если сумма равна трем, то ставим один.

upgrade в сообщении #1158836 писал(а):

Где-то ошибся?

Да, ошиблись.
1-е условие: количество нулей и единиц равно и равно N/2
2-е условие: в последовательности есть или не менее трех нулей подряд или не менее трех единиц подряд
У вас не выполнены оба условия.

Для десяти цифр, количество перестановок из 5 единиц и 5 нулей -- 252 (равновероятные варианты)
Из этих 252, в 168 случаях в перестановке есть или три нуля подряд или три единицы подряд.

[upgrade]

Исправленное:
Формируем ряд из десяти чисел так же как выше. Всего миллион рядов.
Затем напротив рядов с суммой членов ряда $5$ ставим $1$
И Напротив рядов, у которых сумма членов ряда $5$ и сумма последовательных трех чисел равна $3$ или $0$ ставим $1$.
делим сумму всех единиц с условием "и" на сумму всех единиц для рядов, у которых сумма $5$ без "и", получается $0,726852153$

[grizzly]

upgrade в сообщении #1158872 писал(а):

Формируем ряд из десяти чисел так же как выше. Всего миллион рядов.

$10^3<2^{10}=1024<10^6.$ Вы уверены, что решаете ту же задачу?

[upgrade]

Миллион это я переборщил. Да, можно сформировать $1024$ ряда и найти в них те, которые удовлетворяют двум условиям.
...
И получилось $168$ на $252$ /

[wrest]

upgrade в сообщении #1158876 писал(а):

Да, можно сформировать $1024$ ряда и найти в них те, которые удовлетворяют двум условиям.

Ну вот именно это я, например, и сделал, получив вероятность для L=3 равную 2/3. Только я считал в общий котел не только три единицы подряд, но и три нуля подряд тоже.

[DeBill]

Hayka-ckyka в сообщении #1158666 писал(а):

Согласен, пользы нет.

Ну, на самом деле, польза все-таки есть...
Варьируя радиусы полидисков, из оценок Коши на к-ты ряда Тейлора можно получить астмптотику Ваших "количеств $C_{nn}$ наборов из $n+n$, в которых не боле $m$ подряд". Получится: $C_{nn} \sim \operatorname{const} \cdot \lambda ^{-2n}$, где $\lambda$ - положительный корень ур-я $\lambda +... +\lambda^m =1$ - что согласуется с замечанием про $m-$Фибоначчи.

[Hayka-ckyka]

DeBill в сообщении #1158618 писал(а):

Поскольку задача, мне кажется, тяжеловата, привожу набросок "технического" решения.
Пусть $A_{i,j}$ - количество наборов из $i$ белых и $j$ черных, в которых подряд встречается не более $m = L-1$ одинаковых, $A_{00} = 1$, $A(x,y) = \sum\limits_{i\geqslant 0, j \geqslant 0}^{} A_{ij} x^i y^j$ - производящая функция, $F = x+... +x^m$.
Аналогично определим $B(x,y)$ и $G=y+ ...+ y^m$.
Поскольку $A_{ij} = B_{i-1,j} +.... + B_{i-m,j}$, то имеем
$A=BF +1$. Аналогично получим $B=AG+1$. Решая систему, найдем
$A= \frac{1+F}{1-FG}, B=\frac{1+G}{1-FG}$, и $A+B = \frac{2+F+G}{1-FG}$.
Вот коэффициент при $x^ny^n$ этой дроби и есть кол-во наборов из $n+n$ шаров, в которых не более $m$ повторов...
Можно еще разложить дробь $\frac{1}{1-FG}$ как геом. прогрессию, а потом пооткрывать скобки... И придем, видимо, к комбинаторному перебору...
А еще можно $A+B$ разделить на $x^{n+1} y^{n+1}$, и найти вычет в нуле (по $x$ и $y$). Вот только при $m>2$ хрен его сосчитаешь... НО - можно приближенно сосчитать определенные интегралы по малым окружностям, ха-ха....
Ну, и да, $m-$Фиббоначчи тут проглядывает (в рек. формулах).
И последнее: я сосчитал ЭТО для $m=1$... Получилось: если черных-белых поровну, то 2 способа, да.А если черных на один меньше - то один

DeBill, поясните, пожалуйста, Ваше решение.
Какого размера формы A и B? Почему они обладают свойством $A_{ij} = B_{i-1,j} +.... + B_{i-m,j}$?
Как понять выражение $A+B = \frac{2+F+G}{1-FG}$, если $A+B$ имеет слагаемые $x^ny^n$, а правая часть таковых не имеет?

[DeBill]

Hayka-ckyka в сообщении #1159899 писал(а):

Какого размера формы A и B?

$A$ и $B$ - формальные ряды по переменным $x,y$

Hayka-ckyka в сообщении #1159899 писал(а):

Почему они обладают свойством $A_{ij} = B_{i-1,j} +.... + B_{i-m,j}$?

$A_{i,j} $ - количество наборов из $i$ белых и $j$ черных, в которых нет длинных одноцветных блоков, и которые заканчиваются БЕЛЫМИ шарами (нда, это я при наборе пропустил. $B_{i,j}$ - аналогично, но заканчиваются ЧЕРНЫМИ). Этих белых в конце может быть от 1 до $m$. Отбросим их - и получим нашу формулу.
Умножая полученное равенство на $x^iy^j,$, и складывая по всем $i,j, i+j \geqslant 1$ , получим равенство $A(x,y)= B(x,y)\cdot F(x) +1$ (единичку надо добавить, ибо ее не было в наших равенствах).
Аргументы я ленился писать, что и привело к непонятке:

Hayka-ckyka в сообщении #1159899 писал(а):

правая часть таковых не имеет?

Как же не имеет: в этом равенстве $F=F(x), G=G(y)$, и на дробь надо смотреть как на формальный ряд, полученный делением формальных рядов...

[Hayka-ckyka]

DeBill, почему Вы считаете только состояния, где одноцветный кластер длины не более m встречается только в конце?
Ведь нас интересуют все возможные расположения такого кластера, т.е. в любом месте длинного ряда.

[DeBill]

Hayka-ckyka

Hayka-ckyka в сообщении #1160032 писал(а):

одноцветный кластер длины не более m встречается только в конце?

Не понял вопрос... Просто: в конце кто-то есть.

Hayka-ckyka в сообщении #1160032 писал(а):

Ведь нас интересуют все возможные расположения такого кластера, т.е. в любом месте длинного ряда.

Такого - это какого? Максимальной допустимой длины $m$? Нет же, я вовсе не предполагаю, что такой - есть, и тем боле не предполагаю, что он - в конце. Я использую следующее - безусловно верное утв-е: в конце нашего длинного ряда имеется несколько (возможно, только одна - но не более $m$) одноцветных фишек.