The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
0answers
85 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
1answer
50 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 ...
6
votes
0answers
63 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 ...
3
votes
0answers
99 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. ...
12
votes
5answers
345 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 ...
5
votes
1answer
128 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 ...
5
votes
2answers
149 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
181 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
150 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 = ...
6
votes
0answers
132 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
82 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
201 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
104 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
67 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
128 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
165 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
217 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 ...
27
votes
2answers
730 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
678 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 ...
16
votes
2answers
685 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 ...
16
votes
2answers
472 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
460 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 ...
17
votes
1answer
535 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
218 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 ...