The markov-chains tag has no wiki summary.
1
vote
0answers
44 views
Markov chain getting stuck due to insufficient data samples [migrated]
There is a lot of theory on Markov models and output generation out there, but I cannot locate any information on models getting stuck.
I'm trying to create a model of a data set using a Markov ...
2
votes
0answers
58 views
$\omega$-regular properties of a 2-state Markov Chain
Let $X$ be a Markov Chain on a state space $\{0,1\}$ with a transition matrix
$$
P = \left(
\begin{align}
1-p & &p
\\
q & &1-q
\end{align}
\right)
$$
with both $p,q \in (0,1)$ so in ...
4
votes
2answers
130 views
Behaviour of Labelled Markov Processes
Labelled Markov Processes (LMP) seem to be a generalization of Probabilistic Automata (PA) studied by Segala to the case of the general state space. Namely, any LMP is given by a be a finite set of ...
3
votes
1answer
170 views
Boundedness of expected reward Markov chain
This is a repost of a question I asked on math.SE.
The problem:
I have an infinite Markov chain $M$ over the natural numbers, with transition probabilities $$P(n,m)=\sum_{i=0}^{min(m,n)} {n\choose ...
5
votes
0answers
134 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 = ...
5
votes
0answers
120 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 ...
1
vote
0answers
75 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 ...
10
votes
0answers
169 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 ...
1
vote
1answer
86 views
Inferring optimal utility values from a decision process
I've been able to model a particular decision problem as a
Markov Decision Process, where the optimal policy (i.e. what decision should be taken at each step) is defined in order to optimize a given ...
1
vote
0answers
59 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 ...
-2
votes
1answer
114 views
Dual of a Reversible Markov Chain [closed]
Let a reversible Markov process $m_{t+1}=m_t P$, where $t$ is time that has a stationary distribution $\pi$. I saw in a paper that the dual system was defined as $x_{t+1}=P x_t$. Can anyone give me ...
7
votes
0answers
141 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 ...
0
votes
0answers
146 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 ...
25
votes
2answers
662 views
Drunken birds vs drunken ants: random walks between two and three dimensions
It's well known that a random walk in the two dimensional grid will return to the origin with probability 1. It's also known that the same random walk in THREE dimensions has a probability strictly ...
24
votes
1answer
654 views
Random self-avoiding lattice cycle within a given bounding box
In connection with the Slither Link puzzle, I've been wondering: Suppose that I have an $n\times n$ grid of square cells, and I want to find a simple cycle of grid edges, uniformly at random among all ...
15
votes
2answers
542 views
Cover Time of Directed Graphs
Given a random walk on a graph the cover time is the first time (expected number of steps) that every vertex has been hit (covered) by the walk. For connected undirected graphs, the cover time is ...
15
votes
2answers
431 views
Avalanche like stochastic process
Consider the following process:
There are $n$ bins arranged from top to bottom. Initially, each bin contains one ball. In every step, we
pick a ball $b$ uniformly at random and
move all ...
13
votes
2answers
432 views
One-shot quantum hitting times
In the paper Quantum Random Walks Hit Exponentially Faster (arXiv:quant-ph/0205083) Kempe gives a notion of hitting time for quantum walks (in the hypercube) that is not very popular in the quantum ...
16
votes
1answer
513 views
Rapidly mixing Markov chains on 3-colorings of a cycle
The Glauber dynamics is a Markov chain on the colorings of a graph in which at each step one attempts to recolor a randomly chosen vertex with a random color. It does not mix for the 3-colorings of a ...
10
votes
1answer
208 views
Can someone suggest a recent survey on product form Markov chains?
I'm especially interested in their use in model checking applications. I have Open, Closed and Mixed Networks of Queues with Different Classes of Customers by Baskett et al. Any other suggestions ...
