Finding distribution of nodes conditioned on time in a random-walk style model with waiting times

Question

I have a process which is similar to a discrete binary random walk, with the modifications that 1) each node $k$ has a waiting time $w_k$ which is exponentially distributed with a disctinct rate $\lambda_k$, and 2) each transition probability is distinct. I.e. it looks something like this:

with $w_k \sim \text{exponential}(\lambda_k)$. It is assumed that the process moves instantaneously between nodes. What I would like to find is the probability mass function over the nodes, conditioned on a time interval. i.e. if $X$ is a node in the graph, finding

$$ P(X \mid a \leq t \leq b) $$ where $t$ is time (i.e. so that I can see the distribution of positions at certain times, as opposed to discrete steps). This is a "home-made" model, so I'm completely without references on this one.

What I have reasoned so far: Using Bayes' rule I have that $$ P(X \mid a \leq t \leq b) \propto P(a \leq t \leq b \mid X)P(X) $$ Here I assume that using law of total probability, the probability $P(a \leq t \leq b \mid X)$ is the weighted sum of all paths to node $X$: $$ P(a \leq t \leq b \mid X) = \sum_{s \in \mathcal P(X)} P(a \leq t \leq b \mid s) P(s) $$ where $s$ is a sequence of nodes and $\mathcal P(X)$ is the set of paths leading to $X$. Calculating $P(s)$ is obviously just multiplying the probabilities along the path, whereas I understand $P(a \leq t \leq b \mid s)$ to have the hypoexponential distribution with rates corresponding to rates along path $s$, because $t$ will be the sum of exponential variables, all with distinct rates.

What I have a slight problem wrapping my head around is the notion of $P(X)$ back in the Bayes' part. Is this simply the probabilities of each path to $X$ summed up? This feels a bit strange because $P(X)$ will not sum to 1 for all probabilities in the graph. Do I then simply normalize it so that it sums to 1, or is this line of thinking wrong to begin with? If I'm re-inventing the wheel here and someone knows about existing references on this type of model, that would be great as well.

Answer 1

This is an example of a Continuous-time Markov chain. In general, the distribution of Xt (that is, the position of the walk at time t) satisfies a version of the Kolmogorov-Forward equation, and the full distribution of Xt can be expressed in terms of a matrix exponential. Here is a good starting point: https://galton.uchicago.edu/~lalley/Courses/312/ContinuousTime.pdf

By the way, the expression $P(X| a<t<b)$ is ambiguous. Do you mean the probability that the node X is visited at some point in [a,b], or that the walk stays at X for the entirety of the interval [a,b]?

Answer 2

The process you're working with is a Continuous Time Markov Chain (CTMC) and can be completely characterized by a transition rate matrix (in your case sparse, with elements $\omega_k p_k$ and $\omega_k (1-p_k)$). I haven't spent much time on the continuous time case, but in discrete time there are lots of methods for calculating state residence probabilities. Hopefully that gives you a place to start from.