The tag has no usage guidance.

learn more… | top users | synonyms

0
votes
0answers
31 views

Structural properties of Markov decision processes

My question is about structural properties of Markov decision processes (MDPs). In particular, I am interested in partially observable MDPs, or POMDPs, and what can be said about their optimal ...
0
votes
1answer
86 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 ...
7
votes
1answer
92 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 ...
1
vote
1answer
42 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 ...
-4
votes
1answer
54 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 ...
2
votes
0answers
275 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
79 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
68 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
109 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
369 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
135 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
161 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
190 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
156 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
136 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
94 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
248 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
110 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
75 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
134 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 ...
8
votes
0answers
176 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
292 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 ...
29
votes
2answers
961 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 ...
25
votes
1answer
705 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
918 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
481 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
480 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
549 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
227 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 ...