Sojourn time in subset of states for Markov process?

Click For Summary

Discussion Overview

The discussion revolves around estimating the sojourn time of a state within a subset of nodes in a Markov process. Participants explore various methods to characterize the network and calculate exit times, focusing on theoretical approaches and potential simplifications in calculations.

Discussion Character

  • Exploratory
  • Technical explanation
  • Conceptual clarification
  • Debate/contested

Main Points Raised

  • One participant suggests estimating how long a state will remain within a subset of nodes and proposes characterizing the network with parameters for specific subsets.
  • Another participant mentions that calculating the "exit time" distribution for a fixed subset can be approached by merging outside states into an absorbing state, leading to a matrix formula based on transition probabilities.
  • A different participant inquires about defining a distance for subset nodes to facilitate hitting time calculations and seeks techniques to avoid full matrix calculations.
  • There is a suggestion that if the network has a large number of locally connected states, a diffusion model might be applicable, although details on the relationship between exit times and PDEs are not fully explored.
  • Concerns are raised about the comparability of graph topology to normal space, with a desire to derive a distance measure or parameters that indicate the appropriateness of distances.
  • Jump-diffusion is mentioned as a potential model, with a note that the matrix solution might be the simplest approach if transition probabilities can vary.
  • One participant expresses confidence in applying diffusion processes in continuous space and questions how to calculate exit times based on starting points and the shape of the region, as well as how to characterize the state space topology.

Areas of Agreement / Disagreement

Participants express a range of ideas and approaches, with no clear consensus on the best method for calculating sojourn times or characterizing the network. Multiple competing views and uncertainties remain regarding the appropriate models and techniques.

Contextual Notes

Participants mention limitations related to the need for specific knowledge about the network structure and the potential complexity of calculations. There is also an acknowledgment of the challenges in defining metrics for graph networks.

Who May Find This Useful

This discussion may be of interest to researchers and practitioners in fields related to stochastic processes, network theory, and mathematical modeling, particularly those exploring Markov processes and their applications in physical systems.

Gerenuk
Messages
1,027
Reaction score
5
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?
 
Physics news on Phys.org
Gerenuk said:
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!
 
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.
 
Gerenuk said:
The question is: Is there a way to avoid the full matrix calculation?

Depends - what else is known about the network structure?
 
It's not a specific problem. I'm rather trying to think about theory of physical processes. So I could know whatever you wish :smile:. 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.
 
Gerenuk said:
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.
 
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?
 
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.
 
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?
 

Similar threads

  • · Replies 9 ·
Replies
9
Views
5K
  • · Replies 3 ·
Replies
3
Views
2K
  • · Replies 4 ·
Replies
4
Views
3K
  • · Replies 4 ·
Replies
4
Views
2K
  • · Replies 12 ·
Replies
12
Views
5K
Replies
5
Views
3K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 93 ·
4
Replies
93
Views
8K
  • · Replies 5 ·
Replies
5
Views
2K
  • · Replies 2 ·
Replies
2
Views
2K