# Questions tagged [markov-chains]

The tag has no usage guidance.

43 questions
Filter by
Sorted by
Tagged with
32 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 ...
1 vote
176 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
39 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? ...
• 21
133 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 ...
• 133
1 vote
1k 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
111 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 ...
84 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 ...
• 822
163 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
62 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 ...
86 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 ...
• 822
245 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 ...
1 vote
207 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 ...
1 vote
168 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
147 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 ...
• 389
1 vote
249 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 ...
400 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
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
78 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 ...
1 vote
925 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
220 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 ...
77 views

• 3,816
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
112 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
444 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
118 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 ...
• 295
1 vote
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
173 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 ...
265 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 ...
1 vote
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 ...
• 127
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 ...
• 31.7k
765 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.2k
317 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
1k 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.5k
541 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,638
647 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,270
708 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.2k