Questions tagged [markov-chains]
The markov-chains tag has no usage guidance.
47
questions
0
votes
0
answers
25
views
Understanding the transition rule for the Markov chain in the JSV algorithm for approximating the permanent
I was making my way through the paper by Jerrum, Sinclair, and Vigoda on developing a randomized polynomial time procedure (FRPAS) for approximating the permanent of a matrix $A$ with non-negative ...
- 111
5
votes
0
answers
84
views
(Where) is determining the mixing time of an implicitly defined graph in the polynomial hierarchy?
Consider an implicitly defined graph; for example, let $G$ be a finite group generated with $n$ generators as $\langle g_1,g_2,\ldots g_n\rangle$ and let $\Gamma$ be the Cayley graph of $G$ under ...
- 1,063
3
votes
0
answers
74
views
Solving MDPs with polytope action spaces
A (finite) Markov Decision Process (MDP) consists of a finite set of states $S$, a finite set of actions $A_s$ which we will allow to depend on the state $s\in S$, an initial state $s_0\in S$ (the ...
- 2,151
3
votes
1
answer
135
views
Approximative counting of matchings in a graph
The work by Jerrum & Sinclair (1989) describes an approximative approach to determining the number of matchings $|M_\ast(G)|$ in a graph $G=(V,E)$. The fundamental ingredient of the approximation ...
- 139
2
votes
0
answers
33
views
Pagerank update upon vertex removal
Assume we have computed the Pagerank of the vertices of a given graph. Then, remove a vertex from this graph, with all its edges.
How to efficiently compute the Pagerank of remaining vertices in the ...
- 693
1
vote
1
answer
215
views
Effect of self loops on mixing time?
Consider 2 graphs G1 and G2.
G1: Any non-regular graph.
G2: Same graph but with added self-loops such that degree of each node is the same (either some $\Delta$, or maximum '$n$', where $n$ is the ...
- 33
1
vote
0
answers
44
views
Two Questions on the paper Near-optimal Regret Bounds for Reinforcement Learning
I am reading the classic paper Near-optimal Regret Bounds for Reinforcement Learning. I have two questions:
How to combine all MDPs in $ \mathcal{M} $ to get a single MDP with extended action space?
...
- 31
3
votes
1
answer
190
views
Why Asymptotic Equipartition Property theorem proofs assume the source is memoryless?
I do not understand the assumption $X_1, X_2, \cdots$ are i.i.d. ~p(x) in the AEP proofs I have seen. I have read some different sources for understanding the Asymptotic Equipartition Property. Using ...
- 143
1
vote
1
answer
2k
views
Difference between CTMC, DTMC, and MDP
I've been reading the Handbook of Model Checking recently; I'm especially interested in probabilistic model checking, so have been led to the PRISM model checker. For background, I am very familiar ...
- 151
5
votes
1
answer
147
views
Reconstruction of a sequence generated by a Markov chain - reference request
Let S be a finite sequence of symbols from a finite alphabet, with gaps - that is on some known locations an unknown number of symbols are missing. Assuming that the sequence , including the symbols ...
- 201
2
votes
0
answers
97
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,063
2
votes
0
answers
180
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 ...
- 149
2
votes
0
answers
65
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 ...
lprndn
3
votes
1
answer
90
views
Reference Request: soundness in a ZKP achieved by walking along a doubly-stochastic Markov chain?
Consider the following variant of a zero-knowledge proof that two graphs, $G_1$ and $G_2$, given by adjacency matrices $M_1$ and $M_2$, respectively, are not isomorphic.
Here Peggy the prover wants ...
- 1,063
6
votes
1
answer
270
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 ...
- 61
1
vote
1
answer
208
views
Simulate a process of state change with transition probability dependent on proportion in state in previous time
I was thinking about a reverse single transferable vote type situation (i.e. most votes is eliminated) where the process continues until there is only on state left and at each new round there really ...
Vonvorv
1
vote
0
answers
199
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 ...
- 451
4
votes
1
answer
159
views
What automorphisms on a Markov Chain imply a uniform limiting distribution?
Consider an irreducible aperiodic Markov chain $M$, modeled as a connected directed graph with weighted edges. The existence of certain (graph) automorphisms on this Markov chain imply various ...
- 429
1
vote
1
answer
265
views
How can I rank paths through an HMM? [closed]
I have a profile hidden Markov model that I use to identify all instances of a user-defined pattern of symbols in a long sequence of symbols. I use the Viterbi algorithm to find the most probable path ...
- 121
6
votes
1
answer
405
views
How much larger than the relaxation time can the mixing time be?
The notation is mostly taken from the book "Markov chains and mixing times" by Levin, Peres, and Wilmer.
Consider an irreducible, aperiodic, time-reversible, discrete-time Markov chain on a finite ...
- 453
4
votes
1
answer
90
views
Data Mining of self-replicators
My current (very limited) understanding of the creative process that leads to the design of self-replicators is that any particular self-replicator, like Universal Constructor, Langton's loop or ...
- 185
-4
votes
1
answer
82
views
Probabilistic protocols [closed]
I want to model a probabilistic protocol using a model checker, but a lot of protocols are already implemented (e.g. Randomised Dining Philosophers, Dining cryptographers, Synchronous leader election ...
- 95
1
vote
0
answers
1k
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
1
answer
233
views
Policy Adjustment in Markov Decision Process
I was using MDP on my work to make optimal decision. I used discrete time, finite state MDP. I assumed that I will have an initial parameters, like the Reward/Cost, state transition probabilities and ...
- 13
6
votes
0
answers
77
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 $...
- 531
3
votes
0
answers
119
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. ...
- 103
12
votes
5
answers
451
views
Motivation for volume estimation
What are some concrete and compelling applications for estimating the volume of convex polyhedra of the sort considered in the more recent papers on random walk methods?
These papers on volume ...
user17100
5
votes
1
answer
149
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 ...
- 407
5
votes
2
answers
182
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 ...
- 407
4
votes
1
answer
237
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 i}...
- 351
5
votes
0
answers
169
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,946
6
votes
0
answers
143
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 ...
- 81
1
vote
0
answers
114
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 ...
- 111
11
votes
0
answers
474
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 ...
- 775
1
vote
1
answer
121
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 ...
- 305
1
vote
0
answers
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 ...
- 11
-2
votes
1
answer
180
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 ...
- 1
7
votes
0
answers
271
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 ...
- 171
1
vote
0
answers
383
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 ...
- 127
30
votes
2
answers
1k
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 ...
- 32k
25
votes
1
answer
776
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 ...
- 50.9k
-1
votes
1
answer
318
views
Duration Viterbi Algorithm
I am searching for some good resources to understand the Duration Viterbi algorithm.
Does anyone knows a good resource to understand and learn how to model a Duration Viterbi Hidden Markov Chain ...
- 127
17
votes
2
answers
2k
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 ...
- 10.6k
16
votes
2
answers
546
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 the balls ...
- 1,658
13
votes
2
answers
681
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 ...
- 3,280
19
votes
1
answer
727
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 ...
- 50.9k
11
votes
1
answer
267
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 ...
- 6,994