Learning the Influence Graph of a Markov Process that Randomly Resets to the Past
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918293222195200 |
|---|---|
| author | Senthil, Sudharsan Chatterjee, Avhishek |
| author_facet | Senthil, Sudharsan Chatterjee, Avhishek |
| contents | Learning the influence graph G of a high-dimensional Markov process is central to many application domains, including social networks, neuroscience, and financial risk analysis. However, in many of these applications, future states of the process are occasionally and unpredictably influenced by a distant past state, thus destroying the Markovianity. To study this practical issue, we propose the past influence model (PIM), which captures the occasional "random resets to past" by modifying the Markovian dynamics in [1], which, in turn, is a non-linear generalization of the dynamics studied in [2], [3]. The recursive greedy algorithm proposed in this paper recovers any bounded degree $G$ when the number of ``jumps back in time" is order-wise smaller than the total number of samples, and the algorithm does not require memory. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_16129 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Learning the Influence Graph of a Markov Process that Randomly Resets to the Past Senthil, Sudharsan Chatterjee, Avhishek Information Theory Learning the influence graph G of a high-dimensional Markov process is central to many application domains, including social networks, neuroscience, and financial risk analysis. However, in many of these applications, future states of the process are occasionally and unpredictably influenced by a distant past state, thus destroying the Markovianity. To study this practical issue, we propose the past influence model (PIM), which captures the occasional "random resets to past" by modifying the Markovian dynamics in [1], which, in turn, is a non-linear generalization of the dynamics studied in [2], [3]. The recursive greedy algorithm proposed in this paper recovers any bounded degree $G$ when the number of ``jumps back in time" is order-wise smaller than the total number of samples, and the algorithm does not require memory. |
| title | Learning the Influence Graph of a Markov Process that Randomly Resets to the Past |
| topic | Information Theory |
| url | https://arxiv.org/abs/2509.16129 |