I'm doing my thesis where I'm required to compute the numerical value in the following problem:
Let $(X_t)$ be a continuous-time Markov chain such that
-
$X_0 = a$ almost surely.
-
The state space $V$ is finite and endowed with discrete topology.
-
The infintesimal generator is $L: V^2 \to \mathbb R$.
Let $D \subseteq V$ and consider the stopping time $$\tau = \inf \{ t \ge 0 \mid X_t \in D\}$$ Then I'm interested in computing $$\alpha = \mathbb E [X_\tau] \tag{1}$$
Update: I've found the algorithm to simulate $(X_t)$ as follows:
-
Initialize the state of the system $x_0 = a$.
-
For the given state $x$ of the system, calculate the transition rate $\lambda = -L(x,x)$.
-
Simulate holding time at $x$ by drawing from an exponential distribution with mean $1/ \lambda$.
-
Simulate the next state by drawing from the discrete distribution with probability $\mathbb P[\text{transition} = i] = L(x,i) / \lambda$ for all $i \neq x$.
-
Iterate steps 2-4.
I would like to ask how can we modify this algorithm to simulate the stopped process $X_\tau$. Thank you so much!
Best Answer
Given the algorithm you have, and a condition defining $\tau$, i.e. the nature of $D$, simulate $X_t$ in small steps checking if $x_t \in D$ or not. Once $X_t \in D$ for the first time, you have found $\tau = t$.
Doing this for a large number of trials will get you the approximated pdf of $\tau$.
UPDATE
(Q1) When to stop a particular trial: One approach is to set a reasonable number of steps, and if you have not achieved it, record that. You will eventually have to make a call between calling this unreachable, or insufficient number of steps, but analysis of the transition matrix should tell you the point clusters.
(Q2) Determining a reasonable number of trials: This also is more of an art form that a science. When you see a clear pattern of convergence of the average, you can stop.