XXVII OM - I - Zadanie 11

Zawody matematyczne:

XXVII OM, 1975-1976

Etap:

Stacje nadawczo-odbiorcze są kolejno ze sobą połączone: $S_0$ z $S_1$ , $S_1$ z $S_2$ , ..., $S_n$ z $S_{n+1}$ , ... Stacja $S_0$ nadaje sygnał 1 lub -1, stacja $S_1$ odbiera z prawdopodobieństwem $1 - \varepsilon$ ten sam sygnał, a z prawdopodobieństwem $\varepsilon$ sygnał przeciwny. Stacja $S_1$ nadaje odebrany sygnał do stacji $S_2$ na tych samych zasadach, następnie stacja $S_2$ nadaje odebrany sygnał do stacji $S_3$ , itd. Niech $p^n(i|j)$ oznacza prawdopodobieństwo, że stacja $S_n$ odbiera sygnał $i$ pod warunkiem, że stacja $S_0$ nadała sygnał $j$ . Oblicz $\lim_{n\to \infty} p^n(i|j)$ .

Rozwiązanie

Mamy oczywiście $p^n(1 \mid 1) =p^n(-1 \mid -1)$ , $p^n(1 \mid 1) + p^n(1 \mid -1) = 1$ i $p^n(-1 \mid 1) + p^n(- 1\mid -1 ) = 1$ . Wobec tego $p^n(1 \mid -1) = p^n(-1 \mid 1)$ .

Z powyższych równości wynika, że granice ciągów $(p^n(1 \mid 1))$ i $(p^n (-1 \mid - 1))$ są równe i podobnie granice ciągów $(p^n (1 \mid - 1))$ i $(p^n(-1 \mid 1))$ są równe, a granice ciągów $(p^n(1 \mid -1))$ i $(p^n(1 \mid 1))$ w sumie dają $1$ . Jeżeli zaś ciąg $(p^n(1 \mid 1))$ nie ma granicy, to i żaden z ciągów $(p^n(- 1 \mid -1))$ , $(p^n(1 \mid -1))$ i $(p^n(-1 \mid 1))$ nie ma granicy. Wystarczy więc znaleźć granicę ciągu $(p^n(1 \mid 1))$ .

Jeżeli stacja $S_0$ nadała sygnał $1$ i stacja $S_{n+1}$ odebrała sygnał $1$ , to są dwie możliwości:

(a) albo stacja $S_n$ odebrała sygnał $1$ i wtedy stacja $S_{n+1}$ odebrała ten sam sygnał; prawdopodobieństwo tego zdarzenia jest równe $p^n(1 \mid 1) \cdot (1- \varepsilon)$ ,

(b) albo stacja $S_n$ odebrała sygnał $- 1$ i wtedy stacja $S_{n+1}$ odebrała sygnał przeciwny; prawdopodobieństwo tego zdarzenia jest równe $p^n(1 \mid -1) \cdot \varepsilon= (1- p^n(1 \mid 1)) \cdot \varepsilon$ .

Wobec tego

$ p^{n+1}(1 \mid 1) =p^n(1 \mid 1) \cdot (1 - \varepsilon)+ (1-p^n(1 \mid 1)) \cdot \varepsilon = p^n(1 \mid 1) \cdot (1 - \varepsilon)+ \varepsilon. $

Oznaczając $p^k(1 \mid 1)$ krócej przez $p_k$ dla $k = 1, 2, \ldots$ możemy powyższą równość zapisać w postaci

$ (1) \qquad p_{n+1} - \frac{1}{2} = (p_n - \frac{1}{2})(1- 2\varepsilon). $

Z (1) wynika, że $\displaystyle \left( p_n - \frac{1}{2} \right)$ jest ciągiem geometrycznym o ilorazie $1 - 2\varepsilon$ . Pierwszym wyrazem tego ciągu jest $\displaystyle p_1 - \frac{1}{2} = p^1(1 \mid 1) - \frac{1}{2} =(1 - \varepsilon)-\frac{1}{2} = \frac{1}{2} - \varepsilon$ . Wobec tego ze wzoru na $n$ -ty wyraz ciągu geometrycznego otrzymujemy

$ p_n - \frac{1}{2} = \left(\frac{1}{2} - \varepsilon \right) (1 - 2\varepsilon)^{n-1} = \frac{1}{2} (1 - 2 \varepsilon)^n,\ \textrm{tzn.} $

$ (2) \qquad p_n = \frac{1}{2} + \frac{1}{2}(1-2 \varepsilon)^n. $

Z warunków zadania wynika, że $0 \leq \varepsilon \leq 1$ . Z (2) otrzymujemy, że jeżeli $\varepsilon = 0$ , to $\displaystyle p^n = \frac{1}{2} + \frac{1}{2} = 1$ i wobec tego $\displaystyle \lim_{n \to \infty} p_n = 1$ .

Jeżeli zaś $\varepsilon = 1$ , to $\displaystyle p_n = \frac{1}{2} + \frac{1}{2} (-1)^n$ . Wyrazy ciągu $(p_n)$ są więc na przemian równe $0$ i $1$ . Ciąg ten nie ma granicy. Jeżeli zaś $0 < \varepsilon < 1$ , to $- 1 < 1 - 2\varepsilon < 1$ i wobec tego $\displaystyle \lim_{n \to \infty}(1 - 2 \varepsilon)^n = 0$ . Wynika stąd i z (2), że w tym przypadku $\displaystyle \lim_{n \to \infty} p^n = \frac{1}{2}$ .