Problem 1 (10 Points)

Solving a linear system. Monte Carlo method can be used to investigate not only stochastic systems but also deterministic system, such as boundary value problems of partial differential equations, general high dimensional linear equations. In this problem, we abstractly explores this method. Suppose such system assumes the following recursive form

$$q(x) = \sum_{y \in \mathcal{A}}r(x,y)q(y)+ \sum_{z \in \mathcal{B}}r(x,z)q(z) \,\, x \in \mathcal{B}$$ (1)

where $\mathcal{A}$ and $\mathcal{B}$ are index sets and $q(x)$ is known for $x \in \mathcal{A}$ and unknown for $x \in \mathcal{B}$. This kind of recursive form often arises in solving a difference equation with given boundary condition. Prove that, for $x \in \mathcal{B}$,

$$q(x) = \sum_{k=0}^{\infty}\left\{ \sum_{y_1 \in \mathcal{B}} \dot... ...y \in \mathcal{A}} r(x,y_1)r(y_1,y_2) \dotsi r(y_{k-1},y_k)r(y_k,y)q(y)\right\}$$ (2)

Now suppose we construct a Markov chain $\{X_n\}_{n \geq 0}$ in the state space $\mathcal{E}=\mathcal{A} \cup \mathcal{B}$ with transition probability $P(x,y)$ such that

Define stopping time $\tau$ as the first time when the chain hits $\mathcal{A}$, i.e. $\tau = \inf \{n \geq 0 \vert X_n \in \mathcal{A}\}$. Now let us start the chain from $x_0 \in \mathcal{B}$, i.e., $X_0=x_0$. Prove that

$$q(x_0) = \mathbb{E}_{x_0} \left\{ q(X_{\tau}) \prod_{k=1}^{\tau} \frac{r(X_{k-1},X_k)}{P(X_{k-1},X_k)}\right\}$$ (3)

According to the above equation, propose a Monte Carlo method to solve for $q(x) \in \mathcal{B}$(You do not need to write any code, just state the algorithm). However, this method is usually much inferior to its deterministic counterpart except for a few cases, one of which is demonstrated as follows.

We apply this method to a high-dimensional linear system and are only interested in several components of the solution. Precisely, we want to solve $Ax=b$ where $A$ is a $n$-by-$n$ nonsingular matrix and $b$ is a $n$-dimensional vector. By applying eqn.3, we can solve only for several components of the solution $x \in \mathbb{R}^n$ without solving all of them as we do in Gaussian elimination or iterative methods. Identify $\mathcal{A}$, $\mathcal{B}$ and $r(x,y)$ in this particular case. (Hints: you can assume $\rho(I-A)<1$, where $\rho$ is the largest magnitude of the eigenvalues. You do not need to show whyy this method is working.)