Sojourn time in subset of states for Markov process?

[Gerenuk]

I have a graph where from each node the state can change randomly from one node to some of the other nodes. My task is to estimate how long the state will stay within a subset of all these nodes.
Is there a way to characterize the network with some parameters to find the answer (maybe for a specific subset)?
Maybe averaging over node going out of this set or determining some fractal stuff or so?

 

[bpet]

My task is to estimate how long the state will stay within a subset of all these nodes.

To work out the "exit time" (or equivalently "hitting time") distribution for a fixed finite subset is no problem. One strategy is to merge all the outside states into a single absorbing state z so that P(T<=t) = P(X(t)=z) holds. This reduces to a neat matrix formula in terms of the state transition probabilities and starting state probabilities.

Not sure how to parameterize as a function of subsets though. Hope this helps!

 

[Gerenuk]

Oh true.
I haven't dealt with this mathematically, but I vaguely know the concepts.

Is it possible to define some sort of distance for all of the subset nodes so that I can find the hitting time easier?
Basically I'm looking for techniques to define in advance parameters for each node, so that later I could calculate these exit probabilities easy (maybe a summation or so).

The question is: Is there a way to avoid the full matrix calculation?
Maybe to get at least approximate results.

 

[bpet]

The question is: Is there a way to avoid the full matrix calculation?

Depends - what else is known about the network structure?

 

[Gerenuk]

It's not a specific problem. I'm rather trying to think about theory of physical processes. So I could know whatever you wish . Once I have these reduced parameters for the network (maybe one for each node) I'd like to find exit times for arbitrary regions. Or maybe for a fixed region but arbitrary starting point at least.
Or at least get to the solution of that problem as close as possible. I think I'd like to do local calculations only if that is possible.

 

[bpet]

It's not a specific problem. I'm rather trying to think about theory of physical processes.

Ok if it's a physical system with a large number of locally connected states then perhaps a diffusion model could be used? There are some results relating exit times with PDEs though I'm not familiar with the details.

 

[Gerenuk]

A solution similar to a diffusion model would be good.

I just suspect that the topology in graphs isn't comparable to normal space. So it would be nice to know how to derive some distance measure or a parameter that tells if distances are appropriate at all. Maybe also some fractal stuff?

 

[bpet]

Maybe jump-diffusion then?

You might well find that the original matrix solution is the simplest, if the transition probs can take on arbitrary values. The matrix solution effectively gives the exit probabilities as a function of the starting state.

 

[Gerenuk]

I think it's a good assumption to say that the processes are in a continuous space and some sort of diffusion can be applied. Now the questions are
How do I calculate the exit time given a starting point and the "shape" of the region.
What sort of topology describes the state space? With all sorts of connections I could imagine that there are weird metrics? Or how else can one characterise a graph network?