gwiazda i żuczek

[darek20]

Gwiazda ma środek i r ramion. Na k-tym ramieniu jest \(\displaystyle{ n_k}\) punktów. Żuczek znajduje się początkowo w punkcie środkowym gwiazdy. Gdy jest w tym punkcie losowo wybiera ramię na które przechodzi, a będąc na ramieniu losowo wybiera jeden z sąsiednich punktów na który może przejść. Gdy dojdzie do końca gwiazdy jego wędrówka się kończy. Żuczek jest nieśmiertelny więc może wędrować dowolnie długo. Oblicz prawdopodobieństwo że dojdzie do końca i-tego ramienia.

[Errichto]

Punkty na ramionach gwiazdy mają po 2 sąsiadów (nie licząc ostatniego punktu)? Tzn. czy (upraszczając) są współliniowe?
Jeśli nie, to co oznacza koniec gwiazdy? Punkt odwiedzony po raz pierwszy jako ostatni?

[xiikzodz]

Wybierzmy \(\displaystyle{ i}\)-te ramię i ponumerujmy na nim punkty, wraz z zerem liczbami \(\displaystyle{ 0,1,2,\ldots,n_i}\).

Rozważając łańcuch Markowa odpowiadający błądzeniu losowemu ograniczonemu do tego ramienia z dwoma stanami pochłaniającymi:

\(\displaystyle{ 0, n_i}\)

wyznaczamy prawdopodobieństwo pochłonięcia spaceru rozpoczętego w \(\displaystyle{ 1}\) przez stan pochłaniający \(\displaystyle{ 0}\). O ile nie mam błędu w rachunkach (a nie znam się na łańcuchach Markowa) wychodzi:

\(\displaystyle{ \frac{n_i-1}{n_i}}\).

Wystarczy więc zastąpić każde z ramion gwiazdy jej końcem \(\displaystyle{ e_i}\) i jednym punktem pośrednim \(\displaystyle{ m_i}\) z prawdopodobieństwami przejść:

\(\displaystyle{ p_i=P(p_i,k_i)=\frac{1}{n_i}}\)

\(\displaystyle{ q_i=P(p_i,0)=\frac{n_i-1}{n_i}=1-p_i}\)

dla \(\displaystyle{ i=1,2,\ldots r}\)

końce ramion czynimy stanami pochłaniającymi, a dla pozostałych prawdopodobieństw przejść kładziemy zero.

Otrzymujemy macierz \(\displaystyle{ (2r+1)\times(2r+1)}\), która po redukcji stanów pochłaniających staje się macierzą \(\displaystyle{ (r+1)\times(r+1)}\) co widać poniżej:

\(\displaystyle{ \begin{array}{c|cccc|ccc}
*&0&m_1&\ldots&m_r&e_1&\ldots&e_r\\
\hline
0&0&1/r&\ldots&1/r&0&\ldots&0\\
m_1&p_1&0&\ldots&0&q_1&\ldots&0\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\ddots&\vdots\\
m_r&p_r&0&\ldots&0&0&\ldots&q_r\\
\hline
e_1&0&0&\ldots&0&1&\ldots&0\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\ddots&\vdots\\
e_r&0&0&\ldots&0&0&\ldots&1
\end{array}}\)

w skrócie:

\(\displaystyle{ \begin{array}{c|c|c}
*&0,m_i&e_i\\
\hline
0,m_i&Q&N\\
\hline
e_i&0&I
\end{array}}\).

Teoria powiada, że szukana wartość prawdopodobieństwa dla i-tego ramienia stoi na pozycji \(\displaystyle{ (1,i)}\) macierzy \(\displaystyle{ (I-Q)^{-1}\cdot N}\), czyli,

\(\displaystyle{ \frac{1-p_i}{r-\displaystyle{\sum p_i}}=\frac{q_i}{\sum q_i}}\).

O ile więc \(\displaystyle{ p_i}\) były wcześniej poprawnie wyznaczone mamy odpowiedź:

\(\displaystyle{ \displaystyle{\frac{\frac{1}{n_i}}{\sum\frac{1}{n_i}}}}\).

Sporo liczenia, żeby otrzymać coś, co się narzuca.