Wykład 14: Epidemia na drzewie jednorodnym

30-01-2025

Piotr Dyszewski

W naturalny sposób pojawiła się zatem potrzeba dokładniejszej analizy górnego rozkładu stacjonarnego. Niech \[ \phi(A) = \mathbf{P}_A(A_t \neq \emptyset \text{ dla wszystkich } t > 0). \] Proces \(A_t\) jest nieredukowalny. Stąd jeżeli \(\phi(A)>0\) dla pewnego \(A\neq \emptyset\) wtedy i tylko wtedy, gdy \(\phi(B)>0\) dla każdego \(B\neq \emptyset\). Istotnie wystarczy zauważyć, że \[\begin{equation*} \phi(B) \geq \mathbf{P}_B[A_1=A]\phi(A). \end{equation*}\]

Korzystając z reprezentacji graficznej przeżycie dla jednej wartości \(\lambda\) implikuje przeżycie dla wszystkich większych wartości.

Fakt 6 Niech \(0<\lambda_1<\lambda_2\). Jeżeli proces przeżyje dla \(\lambda=\lambda_1\), to proces przeżyje dla \(\lambda=\lambda_2\).

Proof. Rozważmy jednorodny proces Poissona \(N^{(\lambda_1)} = (N^{(\lambda_1)}(t))_{t \in \mathbb{R}}\) z intensywnością \(\lambda_1\) oraz niezależny od niego \(N'=(N'(t))_{t \in \mathbb{R}}\) jednorodny proces Poissona z parametrem \(\lambda_2-\lambda_1\). Z własności rozkładu Poissona wynika, że \(N^{(\lambda_2)}(t) = N^{(\lambda_1)}(t) +N'(t)\) jest jednorodnym procesem Poissona z parametrem \(\lambda_2\). Zauważmy, że z konstrukcji wynika, że każdy skok procesu \(N^{(\lambda_1)}\) jest skokiem procesu \(N^{(\lambda_2)}\). Możemy teraz rozważyć reprezentacje graficzne dla procesów epidemii z parametrami odpowiednio \(\lambda_1\) oraz \(\lambda_2\). Dla każdego wierzchołka \(x \in V\) używamy tego samego procesu \(N_x\) do oznaczenia momentów regeneracji. Dla każdej pary wierzchołków wybieramy czasy zarażania \(N_{x,y}^{(\lambda_1)}\) oraz \(N^{(\lambda_2)}\) w obu procesach tak aby \[\begin{equation*} \left(N^{(\lambda_1)}_{x,y}, N^{(\lambda_2)}_{x,y} \right)\stackrel{d}{=} \left(N^{(\lambda_1)}, N^{(\lambda_2)} \right). \end{equation*}\] Uzyskane w ten sposób dwie reprezentacje graficzne \(A_t^{A,\lambda_1}\) i \(A_t^{A, \lambda_2}\) będą miały następującą cechę: jeżeli w chwili \(t>0\) w \(A_t^{A, \lambda_1}\) jest strzałka z \(x\) do \(y\), to widnieje ona również w reprezentacji graficznej \(A_{t}^{A, \lambda_2}\). Powyższa konstrukcja daje \[\begin{equation*} A_t^{A, \lambda_1} \subseteq A_t^{A, \lambda_2} \end{equation*}\] dla każdego \(t\). Wynika stąd, że jeżeli zbiór po lewej jest niepusty, to zbiór po prawej również jest niepusty.

Istnieje zatem wartość \(\lambda_c \in [0, \infty]\), zwana wartością krytyczną, taka że proces przeżywa, jeśli \(\lambda > \lambda_c\) i wymiera, jeśli \(\lambda < \lambda_c\). Na podstawie zadania z listy, \[\begin{equation} \lambda_c \geq \frac{1}{\max_x \deg(x)} > 0. \tag{52} \end{equation}\]

Funkcje nadharmoniczne

Aby otrzymać górne oszacowanie na \(\lambda_c\) posłużymy się następującym rezultatem wykorzystującym funkcje nadharmoniczne.

Definicja 15 Niech \((T_t)_{t \in \mathbb{R}_+}\). Powiemy, że funkcja \(f\in C_0(S)\) jest nadharmoniczna, jeżeli \[\begin{equation*} T_tf(x) \leq f(x) \end{equation*}\] dla każdego \(x\in S\) oraz każdego \(t\in \mathbb{R}_+\).

Zauważmy najpierw, że jeżeli \((\mathbf{P}, \mathbb{F})\) jest stowarzyszonym procesem Fellera, to dla każdego \(x \in S\) proces \(f(X_t)\) jest \(\mathbf{P}_x\)-nadmartyngałem. Rzeczywiście z własności Markowa mamy bowiem \[\begin{equation*} \mathbf{E}_x[f(X_{t+s})| \mathcal{F} _t] = T_sf(X_t)\leq f(X_t). \end{equation*}\] Zauważmy też, że jeżeli \((L, \mathcal{D}(L))\) jest generatorem infinitezymalnym rozważanej półgrupy, to \(f \in \mathcal{D}(L)\) jest nadharmoniczna wtedy i tylko wtedy, gdy \(Lf\leq 0\). Rzeczywiście dla nahdarmonicznej \(f \in \mathcal{D}(L)\), \[\begin{equation*} Lf(x) = \lim_{t \to 0^+} \frac{T_tf(x) - f(x)}{t} \leq 0. \end{equation*}\] Aby uzasadnić implikację w kierunku przeciwnym rozważmy \(f \in \mathcal{D}(L)\) taką, że \(Lf\leq 0\). Wówczas dla każdego \(s>0\) z monotoniczności \(T_s\) mamy \[\begin{equation*} \frac{\mathrm{d}}{\mathrm{d}s}T_s f = T_sLf \leq 0. \end{equation*}\] Całkując po \(s \in [0,t]\) otrzymujemy \[\begin{equation*} T_tf(x)-f(x) = \int_0^t \frac{\mathrm{d}}{\mathrm{d}s} T_sf(x) \mathrm{d}s \leq 0. \end{equation*}\] Wracając do zagadnienia wymarcia \(A_t\) uzasadnimy najpierw kryterium w terminach funkcji harmonicznych.

Fakt 7 Proces \((A_t)_{t \in \mathbb{R}_+}\) wymiera wtedy i tylko wtedy, gdy istnieje nietrywialna, ograniczona funkcja harmoniczna \(f\) taka, że \(f(\emptyset)\geq f(A)\) dla każdego skończonego \(A \subseteq V\).

Proof. Załóżmy najpierw, że proces przeżyje. Rozważmy \[\begin{equation*} f(A) = \mathbf{P}_A[A_t=\emptyset \mbox{ dla pewnego } t \geq 0]. \end{equation*}\] Skoro proces przeżyje, to dla dowolnego \(A \subseteq V\), \(f(A)<1\). Przy czym \(f(\emptyset)=1\). W szczególności \(f\) nie jest stała i spełnia \(f(A) \leq f(\emptyset)\) dla każdego \(A \subseteq V\). Wówczas, oznaczając przez \((T_t)_{t \in\mathbb{R}_+}\) stowarzyszoną półgrupę Fellera możemy napisać \[\begin{multline*} T_sf(A) = \mathbf{E}_A[f(A_s)] = \mathbf{E}_A[\mathbf{P}_{A_s}[A_t=\emptyset \mbox{ dla pewnego }t \geq 0 ]]\\ \mathbf{E}_A[\mathbf{E}_{A}[A_{t+s}=\emptyset \mbox{ dla pewnego }t \geq 0 | \mathcal{F}_t ]]= \mathbf{P}_A[A_t=\emptyset \mbox{ dla pewnego } t \geq s]\leq f(A). \end{multline*}\] Załóżmy teraz, że \(f\) spełnia założenia faktu. Rozważmy \[\begin{equation*} \tau = \inf\{ t \geq 0 \: : \: A_t=\emptyset\}. \end{equation*}\] Niech \(B_0\) będzie dowolnym ustalonym skończonym podzbiorem \(V\). Rozważmy łańcuch Markowa \(Y=(Y_t)_{t\in \mathbb{R}_+}\) taki, że \(Y_t = A_t\) dla \(t\leq \tau\). Gdy oba procesy osiągną stan \(\emptyset\) proces \(A_t\) już w nim zostaje. Natomiast \(Y_t\) czeka standardowy czas wykładniczy po czym przechodzi do stanu \(B_0\). Od tego momentu intensywności jego przejść są takie same jak dla \(A_t\) (aż do momentu, w którym ponownie odwiedzi \(\emptyset\) z którego wychodzi po czasie wykładniczym z parametrem jeden). Powyższa konstrukcja sprawia, że \(Y\) jest łańcuchem nieredukowalnym. Pokażemy teraz, że \(f\) jest nadharmoniczna również dla \(Y\). Mamy bowiem \[\begin{multline*} \mathbf{E}_A[f(Y_t)] = \mathbf{E}_A[f(Y_t ) \mathbf{1}_{\{ \tau \leq t \}}] + \mathbf{E}_A[f(Y_t)\mathbf{1}_{\{\tau>t \}}] \leq \\ \mathbf{E}_A[f(\emptyset) \mathbf{1}_{\{ \tau \leq t \}}] + \mathbf{E}_A[f(A_t)\mathbf{1}_{\{\tau>t \}}] = \mathbf{E}_A[f(A_t)] \leq f(A). \end{multline*}\] Oznacza to, że \(f(Y_t)\) jest nadmartyngałem, więc jest w szczególności zbieżny z prawdopodobieństwem jeden. Pokażemy teraz, że powyższe oznacza, że \(Y_t\) jest tranzytywny. Skoro \(f\) jest nietrywialna, to istnieje skończony \(B_1 \subseteq V\) taki, że \(f(B_1)<f(\emptyset)\). Gdyby \(Y_t\) był rekurencyjny, to nieskończenie wiele razy odwiedzałby \(B_1\) oraz \(\emptyset\). Stąd wśród wartości \(f(Y_t)\) pojawiłoby się nieskończenie wiele \(f(B_1)\) i nieskończenie wiele \(f(\emptyset)\). Taki ciąg nie mógłby być zbieżny. Sprzeczność ta uzasadnia tranzytywność \(Y_t\). Wobec tego \(\mathbf{P}_A[\tau=\infty]>0\) co jest równoważne z tym, że proces \(A_t\) przeżyje.

Epidemia na drzewie jednorodnym

Zaprezentujemy teraz oszacowania na wartość krytyczną \(\lambda_c\) w przypadku \(G\) będącego drzewem \(d\)-jednorodnym, gdzie \(d\in \mathbb{N}\). Jest to graf spójny bez cykli, w którym każdy wierzchołek ma stopień \(d+1\).

Twierdzenie 20 Wartość krytyczna dla procesu epidemii na drzewie \(d\)-jednorodnym spełnia \[ 1/(d + 1) \leq \lambda_c \leq 1/(d - 1). \]

Proof. Pierwsza nierówność to po prostu (52) w przypadku grafu \(d+1\) regularnego. Aby uzasadnić drugą nierówność wystarczy rozważyć \(\lambda >1/(d-1)\) i pokazać, że proces przeżyje. W tym celu wystarczy uzasadnić istnienie odpowiedniej funkcji nadharmonicznej. Dla \(\rho \in (0,1)\) rozważmy \[ f(A) = \rho^{|A|}. \] Pokażemy, że dla odpowiedniej wartości parametru \(\rho\) funkcja ta będzie nadharmoniczna. W tym celu sprawdzimy warunek na generator infinitezymalny. Mamy \[ Lf(A)=\frac{\mathrm{d}}{\mathrm{d}t} \mathbf{E}_A[ f(A_t)] \bigg|_{t=0} = [\rho^{-1}|A| - \lambda | \{(x, y) : x \in A, y \notin A, y \sim x \} | ](1 - \rho)f(A). \] Aby ograniczyć prawą stronę zauważmy, że \[ \sum_{x \in A, y \sim x} 1 = |A|(d + 1). \] Ponieważ \(A \neq \emptyset\) jest skończonym grafem acyklicznym, liczba krawędzi w \(A\) to \[|A| - (\text{liczba składowych spójności } A) \leq |A| - 1.\] Zatem \[ \sum_{x,y \in A, y \sim x} 1 \leq 2(|A| - 1). \] Użycie tej nierówności w wyrażeniu na \(Lf(A)\) daje \[ \frac{\mathrm{d}}{\mathrm{d}t} \mathbf{E}_A f(A_t) \bigg|_{t=0} \leq |A|(\rho^{-1} - \lambda(d - 1))(1 - \rho)f(A), \] co jest \(\leq 0\), jeśli \(\rho\lambda(d - 1) \geq 1\). Tak więc jeśli \(\lambda > 1/(d - 1)\), istnieje \(0 < \rho < 1\), dla którego \(f\) spełnia założenia poprzedniego faktu.