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

[Hayka-ckyka]

Задача такова.
Есть N шаров, из которых N/2 белых и N/2 черных. Все шары перемешивают и выстраивают в один длинный ряд из N шаров.
Какова вероятность того, что в этом длинном ряду найдется последовательность из L шаров одного цвета, стоящих подряд?

Пробовал решать через комбинаторику, т.е. отношение количества удовлетворяющих условию перестановок к полному числу. Загвоздка в том, что спрашивается о поиске упорядоченной структуры шаров в ряде. Но в принципе, таких структур может быть несколько, поэтому одно и тоже состояние строки из N шаров может быть посчитано несколько раз при использовании комбинаторных методов.
Помогите разобраться, решаются ли задачи такого типа через комбинаторику вообще? Если нет, то подскажите пжл с какого бока к этой задаче подойти.

[upgrade]

Либо я чего-то не понял, либо это крайне легкая задача.
У вас же вероятность положить первым (вторым, третьим ...) белый (или черный) шар уже задана - $0,5$.
Рассчитать вероятность появления следующим шаром снова белого (или черного) не составляет труда.

[Hayka-ckyka]

Да нет, дело не в N. Если бы было так, то это вопрос лишь писанины.
Вы предлагаете выбор шаров с одного из концов, но спрашивается о существовании L одноцветных шаров, стоящих подряд не важно где - в середине, конце или начале большого ряда.

[upgrade]

А какая разница, если вероятность того, что ряд начнется с первого или с десятого шара одинаковая?

-- 10.10.2016, 14:35 --

Единственная сложность - что ближе к концу $N$ ряда длиной $L$ точно не будет. Т.е. вероятность встретить ряд зависит от соотношения длины ряда одинаковых шаров с общей длиной.

[Hayka-ckyka]

Как же она может быть одинаковой? Если ряд из одноцветных шаров расположен в середине, то вероятность его существования зависит от того, что было перед ним.

[upgrade]

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

Как же она может быть одинаковой? Если ряд из одноцветных шаров расположен в середине, то вероятность его существования зависит от того, что было перед ним.

Допустим у нас четыре шара - два черных и два белых.
Вероятность вытащить четвертым черный шар - $0,5$, даже если два черных уже вытащили.
А вот вероятность вытащить четвертым черный шар ЕСЛИ два черных уже вытащили - $0$.

[Hayka-ckyka]

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

Допустим у нас четыре шара - два черных и два белых.
Вероятность вытащить четвертым черный шар - $0,5$, даже если два черных уже вытащили.
А вот вероятность вытащить четвертым черный шар ЕСЛИ два черных уже вытащили - $0$.

И какое отношение этот тривиальный и очевидный пример имеет к моему вопросу, в котором спрашивается о существовании кластера из одноцветных шаров?

[wrest]

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

Есть N шаров, из которых N/2 белых и N/2 черных. Все шары перемешивают и выстраивают в один длинный ряд из N шаров.
Какова вероятность того, что в этом длинном ряду найдется последовательность из L шаров одного цвета, стоящих подряд?

Я встречал такую формулу:
Вероятность того, что в случайной последовательности из N нулей и единиц встретится последовательность из L единиц подряд, равна
$p=1-\dfrac{F_L(N+2)}{2^N}$
где $F_k(i)$ -- $i$-й член последовательности Фибоначчи с шагом $k$ (см. http://mathworld.wolfram.com/Fibonaccin-StepNumber.html)

[Hayka-ckyka]

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

Я встречал такую формулу:
Вероятность того, что в случайной последовательности из N нулей и единиц встретится последовательность из L единиц подряд, равна
$p=1-\dfrac{F_L(N+2)}{2^N}$
где $F_k(i)$ -- $i$-й член последовательности Фибоначчи с шагом $k$ (см. http://mathworld.wolfram.com/Fibonaccin-StepNumber.html)

Красиво.
Это, конечно, не совсем то, о чем я спрашивал, т.к. у меня фиксированное число нулей и единиц (по N/2 каждых), а в Вашем примере их соотношение произвольно. Но все же интересно как получена формула с членом посл-ти Фибоначчи из Вашего примера. Возможно, тогда я смогу найти ответ и на свой вопрос.

[wrest]

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

Но все же интересно как получена формула с членом посл-ти Фибоначчи из Вашего примера. Возможно, тогда я смогу найти ответ и на свой вопрос.

Я вычитал это здесь: http://www.drdobbs.com/architecture-and ... /229300217

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

[upgrade]

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

И какое отношение этот тривиальный и очевидный пример имеет к моему вопросу, в котором спрашивается о существовании кластера из одноцветных шаров?

Наверное, я все-же чего-то не понимаю.

[DeBill]

wrest
Видимо, это не совсем то, что надо: типа, генерируем $N$ случайных чисел 0-1, и тогда получим таку вер-ть.Hayka-ckyka
Ответ получить, видимо, можно, но пользы от него - никакой...
Поскольку задача, мне кажется, тяжеловата, привожу набросок "технического" решения.
Пусть $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 способа, да.А если черных на один меньше - то один

[Hayka-ckyka]

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

Ответ получить, видимо, можно, но пользы от него - никакой...

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

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

И последнее: я сосчитал ЭТО для $m=1$... Получилось: если черных-белых поровну, то 2 способа, да.А если черных на один меньше - то один

[Hayka-ckyka]

А можно ли как-нибудь сконструировать случайную величину, отвечающую за максимальную длину одноцветного кластера в общем ряде из всех шаров?

[wrest]

Если вдруг получите формулу, то вот для проверки: N=10 и L=3 должен получиться ответ 166/252 :)