Sia \(X = (X_k)_{k} \) una simple random walk su \(G = \{ 1 ,\ldots, N-1\} \) con bordo \( \partial G = \{0,N\} \) che parte da \(x_0 \in G \).
Dimostra il seguente teorema:
Per ogni \(y \in G \) abbiamo
\[ \mathbb{P}_{x_0}[X_{\min\{n,T_{\partial G}\}} = y] = \frac{2}{N}
\sum_{j=1}^{N-1} \Phi_j(x) \cos^n \left( \frac{j \pi}{N} \right) \Phi_j(y) \]
con \( \Phi_j(x) = \sin \left( \frac{\pi j x}{N} \right) \). E dove \(T_{\partial G} \) indica la prima volta che \(X\) visita il bordo.
Dimostrazione:
Step 1: Consideriamo \( f(n,y) = \mathbb{P}_{x_0}[X_{\min\{n,T_{\partial G}\}} = y] \) per \(y \in G \) e \( f(n,y) = 0 \) per \( y \in \partial G \). Dimostriamo che \( f(n,y)\) soddisfa l'equazione de calore discreta
Testo nascosto, fai click qui per vederlo
Questo è vero poiché la probabilità che \(X\) si trova in \(y\) al tempo \(n+1\) è uguale alla somma sui nodi \(z\) adiacenti a \(y \) della probabilità che \(X\) si trovi al tempo \(n\) in \(z\) e che poi salta da \(z\) a \(y\). Ottenendo quindi
\[ f(n+1,y) = \frac{1}{2d} \sum_{z \sim y} f(n,z) \]
oppure
\[ \partial_n f(n,y) = \Delta f(n,y) \]
\[ f(n+1,y) = \frac{1}{2d} \sum_{z \sim y} f(n,z) \]
oppure
\[ \partial_n f(n,y) = \Delta f(n,y) \]
Non capisco perché è equivalente a dire \(\partial_n f(n,y) = \Delta f(n,y) \).
Step 2: Dimostriamo che l'algoritmo consiste nel moltiplicare il vettore \(f(n,\cdot)\) ad ogni passo per una matrice simmetrica \(Q\) fissata, quindi che \( f(n,\cdot) = Q^n f(0,\cdot) \).
Testo nascosto, fai click qui per vederlo
L'equazione del calore discreta può essere scritta come \( f(n+1,y)= \frac{1}{2d} \sum_{z \sim y} f(n,z) \) quindi possiamo vedere che moltiplichiamo \( (f(n,z))_{z \in G} \) per la matrice \(Q=\Delta^0 + Id\) per ottenere \( (f(n+1,z))_{z \in G} \) pertanto per induzione abbiamo
\[ f(n,y) = ( Q^n f(0,\cdot))_y \]
\[ f(n,y) = ( Q^n f(0,\cdot))_y \]
Step 3: Diagonalizziamo \(Q\) e troviamo gli autovalori \( \lambda_i \) e gli autovettori \( \Phi_i \) e dimostriamo che gli autovettori sono ortogonali.
Testo nascosto, fai click qui per vederlo
Consideriamo \( \Psi_{\theta}(x)=\sin(\theta x) \) in modo da ottenere la condizione nulla al bordo, \( \sin(\theta N) = 0 \) e quindi \( \theta N = \pi k \) da cui \( \theta_k = \frac{k \pi}{N} \). Definiamo \( \Phi_k(x) = \sin(\theta_k x) \) e denotiamo \( \Im\) la parte immaginaria. Allora
\[ \Phi_k(x \pm 1 ) = \Im(e^{i \theta_k (x\pm 1)} ) = \Im( e^{i \theta_kx } e^{\pm i \theta_k} ) = \sin(\theta_k x) \cos ( \theta_k) \pm \cos( \theta_k x) \sin(\theta_k ) \]
per cui \( \Phi_k(x+1)+\Phi_k(x-1) = 2 \cos(\theta_k ) \Phi_k(x) \). Per ogni \(k \) abbiamo trovato un autovettore \( \Phi_k (x) = \sin \left( \frac{k \pi x}{N} \right) \) associato al autovalore \( \cos \left( \frac{k \pi}{N} \right) \).
Lo spazio delle funzioni che consideriamo è uno spazio vettoriale \(N-1\)-dimensionale. Dovremmo trovare quindi \(N-1\) autovettori. Infatti abbiamo che \( \Phi_{k+N}(\cdot) = - \Phi_k(\cdot) \) per cui possiamo considerare \(k \in \{0,\ldots, N-1\} \). Inoltre \( \Phi_0(\cdot) = 0 \) per cui possiamo considerare solo \( k \in \{1,\ldots, N-1\). Abbiamo quindi \(N-1\) autovettori. Gli autovalori sono distinti e poiché \(Q\) è simmetrica, sono ortogonali.
\[ \Phi_k(x \pm 1 ) = \Im(e^{i \theta_k (x\pm 1)} ) = \Im( e^{i \theta_kx } e^{\pm i \theta_k} ) = \sin(\theta_k x) \cos ( \theta_k) \pm \cos( \theta_k x) \sin(\theta_k ) \]
per cui \( \Phi_k(x+1)+\Phi_k(x-1) = 2 \cos(\theta_k ) \Phi_k(x) \). Per ogni \(k \) abbiamo trovato un autovettore \( \Phi_k (x) = \sin \left( \frac{k \pi x}{N} \right) \) associato al autovalore \( \cos \left( \frac{k \pi}{N} \right) \).
Lo spazio delle funzioni che consideriamo è uno spazio vettoriale \(N-1\)-dimensionale. Dovremmo trovare quindi \(N-1\) autovettori. Infatti abbiamo che \( \Phi_{k+N}(\cdot) = - \Phi_k(\cdot) \) per cui possiamo considerare \(k \in \{0,\ldots, N-1\} \). Inoltre \( \Phi_0(\cdot) = 0 \) per cui possiamo considerare solo \( k \in \{1,\ldots, N-1\). Abbiamo quindi \(N-1\) autovettori. Gli autovalori sono distinti e poiché \(Q\) è simmetrica, sono ortogonali.
Non capisco troppo perché mi dice che è un autovettore... non dovrei dimostrare che
\[ Q \Phi_k(x) = \cos \left( \frac{ k \pi}{N} \right) \Phi_j(x) \] ?
Step 4: Decomponiamo la densità \( \delta_{y=x_0} \) con autovettori \( \delta_{y=x_0} = \sum a_i \Phi_i \). Considerando il prodotto scalare e quindi
\[ \left< \delta_{y=x_0}, \Phi_j \right> = \left< \sum a_i \Phi_i, \Phi_j \right> = a_j \left \| \Phi_j \right \|^2 \]
poi concludiamo
Testo nascosto, fai click qui per vederlo
Iniziamo a calcolare \( \left< \delta_{y=x_0}, \Phi_j \right> \) questo è semplicemente \( \Phi_j(x_0) \).
Ci rimane a calcolare \(\left \| \Phi_j \right \|^2 \). Abbiamo che
\[ \sum_{x=1}^{N-1} \Phi_j(x)^2 = \sum_{x=1}^{N-1} \sin^2 \left( \frac{j \pi x}{N} \right) \]
usando \( \sin^2(\theta) = \frac{1}{2} - \frac{1}{2} \cos(2\theta) \) otteniamo
\[ \sum_{x=1}^{N-1} \Phi_j^2(x) = \frac{N-1}{2} - \frac{1}{2} \sum_{y}^{N-1} \cos \left( \frac{2\pi j y}{N} \right) \]
e poiché \( \cos x = \Re(e^{ix} ) \) otteniamo
\[ \frac{1}{2} \sum_{y}^{N-1} \cos \left( \frac{2\pi j y}{N} \right) = \frac{1}{2} \Re \left( \sum_{y=1}^{N-1} e^{ i \frac{2 j \pi y}{N} } \right) - \frac{1}{2} \]
Pertanto
\[ \left \| \Phi_j \right \|^2 = \sum_{x=1}^{N-1} \Phi_j^2(x) = \frac{N}{2} \]
Dunque \( a_i = \frac{2}{N} \Phi_j(x_0) \). Dunque la decomposizione di \( \delta_{y=x_0} \) è uguale a
\[ \delta_{y=x_0}= \sum a_i \Phi_i \]
e la soluzione
\[ \mathbb{P}_{x_0} [ X_{ \min \{ n, T_{\partial G} \} } = y ] = ( Q^n \delta_{\cdot = x_0} )_y = \frac{2}{N} \sum_{j=1}^{N-1} \Phi_j(x_0) \cos^n \left( \frac{ j \pi}{N} \right) \Phi_j(y) \]
Ci rimane a calcolare \(\left \| \Phi_j \right \|^2 \). Abbiamo che
\[ \sum_{x=1}^{N-1} \Phi_j(x)^2 = \sum_{x=1}^{N-1} \sin^2 \left( \frac{j \pi x}{N} \right) \]
usando \( \sin^2(\theta) = \frac{1}{2} - \frac{1}{2} \cos(2\theta) \) otteniamo
\[ \sum_{x=1}^{N-1} \Phi_j^2(x) = \frac{N-1}{2} - \frac{1}{2} \sum_{y}^{N-1} \cos \left( \frac{2\pi j y}{N} \right) \]
e poiché \( \cos x = \Re(e^{ix} ) \) otteniamo
\[ \frac{1}{2} \sum_{y}^{N-1} \cos \left( \frac{2\pi j y}{N} \right) = \frac{1}{2} \Re \left( \sum_{y=1}^{N-1} e^{ i \frac{2 j \pi y}{N} } \right) - \frac{1}{2} \]
Pertanto
\[ \left \| \Phi_j \right \|^2 = \sum_{x=1}^{N-1} \Phi_j^2(x) = \frac{N}{2} \]
Dunque \( a_i = \frac{2}{N} \Phi_j(x_0) \). Dunque la decomposizione di \( \delta_{y=x_0} \) è uguale a
\[ \delta_{y=x_0}= \sum a_i \Phi_i \]
e la soluzione
\[ \mathbb{P}_{x_0} [ X_{ \min \{ n, T_{\partial G} \} } = y ] = ( Q^n \delta_{\cdot = x_0} )_y = \frac{2}{N} \sum_{j=1}^{N-1} \Phi_j(x_0) \cos^n \left( \frac{ j \pi}{N} \right) \Phi_j(y) \]
Non capisco come fa a concludere sinceramente
