Questions tagged [markov-chains]

The tag has no usage guidance.

15 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
11
votes
0answers
375 views

Cheeger's inequality for directed graphs?

Cheeger's inequality can be used to relate the size of the worst cut in the graph to the eigenvalue gap of a simple random walk on that graph. I am wondering if it possible to extend this result to ...
7
votes
0answers
254 views

Complexity of reachability in Markov Chains

Is anything known about the complexity of the following problem beyond membership in PTIME: Given a finite Markov chain $M$, an initial state $q_0$ and a set $F$ of (absorbing) states, is the ...
6
votes
0answers
71 views

Fast convergence of a contagion process in special graphs

The process: Given is a clique $C_n$ of size $n$. Consider the following synchronous process, also known as the (synchronous) voter model (e.g., Even-Dar and Shapira): Define an indicator variable $...
6
votes
0answers
139 views

Complexity of DTMC subsystems

A discrete-time Markov chain (DTMC) is a tuple $M=(S,s_{init},P)$ where $S$ is a finite set of states, $s_{init}\in S$ the initial state, and $P:S\times S\to[0,1]$ the one-step transition probability ...
6
votes
1answer
207 views

A random walk that moves to less-visited nodes

Consider a random walk on an undirected graph that keeps track of how many times it has visited every node. At each step, it moves to the node among its neighbors which has been visited the least ...
5
votes
0answers
165 views

The regularity of Markov chains with a threshold

(This question has been asked on math.se, with no response.) I am studying Paz's "Introduction to Probabilistic Automata" and there is an exercise I cannot solve: Ex. 11, p. 170: Let $\Sigma = \{a\...
3
votes
0answers
115 views

Concentration of Stationary Distribution on Random Directed Graphs

We consider a random directed graph with fixed out-degree $d$. Each vertex chooses $d$ neighbors with replacement, uniformly and independently. Self-loops and multiple arcs are allowed in this model. ...
2
votes
0answers
132 views

Crime prevention using graph theory and machine learning

I am looking for a way to the model the incidence of crime among a network of individuals. Part of it will use machine learning, and part of it will have to resort to some graph theoretic ...
2
votes
0answers
54 views

Probabilistic linebreaking algorithm

I'm currently trying to implement this paper: Bouckaert, Remco R., A probabilistic line breaking algorithm, Gedeon, Tamás D. (ed.) et al., AI 2003: Advances in Artificial Intelligence. 16th ...
1
vote
0answers
67 views

What is the computational complexity of determining the mixing time of a Cayley graph?

Bayer and Diaconis famously proved that a deck of fifty-two cards will be mixed after only seven dovetail shuffles. Numberphile has a nice series of videos of Diaconis explaining the proof. I ...
1
vote
0answers
99 views

Off-policy Monte Carlo Control

The off-policy Monte Carlo control algorithm to learn the optimal state-value function $V^*$ is given as follows, which is obtained from Sutton's book. I have three questions concerning this ...
1
vote
0answers
716 views

Time-inhomogeneous Markov Chains

I'm trying to find out what is known about time-inhomogeneous ergodic Markov Chains where the transition matrix can vary over time. All textbooks and lecture notes I could find initially introduce ...
1
vote
0answers
109 views

Techniques to get nodes in the best Markov Cluster?

I was using Markov Clustering to cluster nodes in my bidirectional graph, and overall the results were great. However, there were a couple instances where a weakly connected node would attract a node ...
1
vote
0answers
93 views

Belief Propagation on MRF with complex cliques

Is there a belief propagation algorithm for exact inference on a MRF with complex clique structures (i.e. ones involving more than 2 neighbours)? For MRF's with cliques that only involve pairwise ...
1
vote
0answers
382 views

Implementation of a Logical Hierarchical Hidden Markov Model

Is anyone aware of any implementations of algorithms for learning and/or processing a Logical Hierarchical Hidden Markov Model, as described in this paper? I've found dozens of papers about Logical ...