Smutny ciąg liczbowy

[nivwusquorum]

Witam,

Zadanie
Mamy ciąg \(\displaystyle{ n}\) bitów. Prawdopodobieństwo, że dany wyraz ciągu jest smutny to \(\displaystyle{ b}\). Obliczyć prawdopodobieństwo że istnieje spójny podciąg co najmniej \(\displaystyle{ k}\) wyrazów, które nie są smutne.

Co wymyśliłem
Pomyślałem sobie, żeby rozważyć problem odwrotny. Czyli prawdopodobniestwo, że podana własność nie zachodzi.
Wymyśliłem, że ten problem to to samo co prawdopodobieństwo, że w czasie \(\displaystyle{ n}\)-krokowego spaceru losowego 1D nigdy nie wyjdziemy na pozycje \(\displaystyle{ \geq k}\). W tym spacerze krok w prawo wykonujemy z prawdopodobieństwem \(\displaystyle{ (1-b)}\) i w lewo \(\displaystyle{ b}\). Potem probowalem wykombinowac, jak policzyć to prawdopodobieństwo korzystając z kombinacji kroków w lewo i w prawo, ale do niczego nie doszedłem.

Pomoże ktoś? Z góry dzięki!

[octahedron]

To ma być dokładnie \(\displaystyle{ k}\) wyrazów, czy może być więcej?

[nivwusquorum]

Już uściśliłem w oryginalnym poście. Chodzi o co najmniej k. Ale jeżeli masz rozwiązanie dla =k, to też chętnie posłucham

[octahedron]

Dla dokładnie \(\displaystyle{ k}\) pomysł mam taki: pierwsze \(\displaystyle{ k}\) wyrazów nie smutnych i potem \(\displaystyle{ n-k}\) smutnych, prawdopodobieństwo \(\displaystyle{ P_k=(1-b)^kb^{n-k}}\), potem pierwszy wyraz smutny, \(\displaystyle{ k}\) nie smutnych i dalej smutne, prawdopodobieństwo również \(\displaystyle{ P_k}\), itd., takich ciągów jest \(\displaystyle{ n-k}\), więc łączna szansa wynosi \(\displaystyle{ (n-k)P_k}\). Dla co najmniej \(\displaystyle{ k}\) to by była suma \(\displaystyle{ P'_k=(n-k)P_k+(n-k-1)P_{k+1}+...+2P_{n-1}+P_n}\). Innego pomysłu, przynajmniej w tej chwili, nie mam.

[nivwusquorum]

Hmm... na moje to rozwiązanie wygląda na błędne, ale może czegoś nie rozumiem. Czy uwzględniasz np. że dla n=10, k=2 ciąg

0111010110 (0 - smutny)

jest ok? bo mi się wydaje że Ty masz tylko ciągi w formie:
(x zer)(y jedynek)(z zer).

[octahedron]

Faktycznie, coś mi się pomieszało