liczba podciągów w rzucie monetą

[teusiek]

Nie mogę poradzić sobie z jednym wydawałoby się nietrudnym zadaniem
Rozpatrzmy ciąg \(\displaystyle{ n}\) niezależnych rzutów monetą, na których orzeł wypada z prawdopodobieństwem równym \(\displaystyle{ p \in (0,1)}\). Niech \(\displaystyle{ X}\) oznacza liczbę maksymalnych podciągów złożonych z samych orłów lub z samych reszek. Dla przykładu:
Jeśli \(\displaystyle{ n=9}\) i w wyniku tych 9 rzutów wypadło \(\displaystyle{ OORORROOO}\) to \(\displaystyle{ X=5}\)
Jak znaleźć \(\displaystyle{ \mathbb{E}X}\) oraz \(\displaystyle{ Var(X)}\)?

Jedyne co mi przychodzi do głowy to coś takiego
\(\displaystyle{ X= \sum_{i=1}^{n} X_i}\) gdzie \(\displaystyle{ X_i= \left\{ \begin{array}{ll}
1 & \textrm{jeśli w i-tym rzucie wypadło coś innego niż w (i-1) rzucie}\\
0 & \textrm{jeśli wypadło to samo}
\end{array} \right}\) dla \(\displaystyle{ i=2,3,..,n}\) oraz \(\displaystyle{ X_1=1}\)

ale to chyba nie najlepsza próba bo nie wiem co dalej z tym robić. Jakaś wskazóweczka?

[Premislav]

Oznaczmy
\(\displaystyle{ X_n}\) – liczba podciągów w \(\displaystyle{ n}\) niezależnych rzutach monetą (prawdopodobieństwo wypadnięcia orła \(\displaystyle{ p\in (0,1)}\)).
Wówczas możemy spróbować uzależnić \(\displaystyle{ \mathbf{P}(X_{n+1}=k)}\) od \(\displaystyle{ \mathbf{P}(X_n=k)}\) czy coś w tym stylu. Niech \(\displaystyle{ k\ge 1}\), wówczas
\(\displaystyle{ \mathbf{P}(X_{n+1}=k+1)=A \mathbf{P}(X_n=k+1)+B \mathbf{P}(X_n=k)}\),
gdzie \(\displaystyle{ A}\) to prawdopodobieństwo zdarzenia polegającego na tym, że w \(\displaystyle{ n+1}\). rzucie wypadnie to samo, co w \(\displaystyle{ n}\). rzucie, zaś \(\displaystyle{ B}\) to prawdopodobieństwo, że w \(\displaystyle{ n+1}\). rzucie wypadnie coś innego.
Zdaje się, że z prawdopodobieństwa warunkowego mamy
\(\displaystyle{ A=p^2+(1-p)^2}\) oraz \(\displaystyle{ B=2p(1-p)}\), ale mogę się mylić.
Ponadto oczywiście przydadzą się jakieś warunki początkowe, które łatwo wyliczyć,
\(\displaystyle{ \mathbf{P}(X_1=1)=1, \ \mathbf{P}(X_2=1)=p^2+(1-p)^2, \mathbf{P}(X_2=2)=2p(1-p)}\)

Teraz chyba
\(\displaystyle{ \mathbf{E}(X_n|X_{n-1}=k)=k(p^2+(1-p)^2)+(k+1)\left( 2p-2p^2\right)}\)
oraz
\(\displaystyle{ \mathbf{E}(X_n)= \sum_{k=1}^{n-1}\mathbf{E}(X_n|X_{n-1}=k)\mathbf{P}(X_{n-1}=k)=\\=\ldots}\)
i z tego powinna wyjść po banalnych spostrzeżeniach dość prosta zależność rekurencyjna \(\displaystyle{ \mathbf{E}(X_n)}\) od \(\displaystyle{ \mathbf{E}(X_{n-1})}\).

Pewnie istnieje ładniejsze podejście, ale coś takiego przyszło mi na myśl.
Wątpliwości mam co do tej wartości \(\displaystyle{ A}\) i \(\displaystyle{ B}\).

[teusiek]

Sprytne podejście i bardzo mi się podoba aż do momentu gdzie pojawia się warunkowa wartość oczekiwana, której jeszcze nie poznałem. Da się to jakoś obejść?

[leg14]

Przestaw się Teusiek na myślenie kombinatoryczne i (wykorzystując podejście Premislava i.e. rekurencyjne obliczanie) wyznacz \(\displaystyle{ p_{n}(k)}\) czyli ilość ciągów n-elementowych złożonych z \(\displaystyle{ 0,1}\), w kótrych maksymalnych podciągów jest \(\displaystyle{ k}\).
Cały argument Przemka streszcza się w następującej obserwacji:

jeśli ciąg \(\displaystyle{ X}\) należy do \(\displaystyle{ p_{n}(k)}\) to mamy dwie możliwości:
1) ostatnie dwie cyfry ciągu są różne i wówczas X obcięte do \(\displaystyle{ n-1}\) pierwszych wyrazów należy do \(\displaystyle{ p_{n-1}(k-1)}\)
2) ostatnie dwie cyfry ciągu są takie same i wówczas X obcięte do \(\displaystyle{ n-1}\) pierwszych wyrazów należy do \(\displaystyle{ p_{n-1}(k)}\)