Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [markov-chains]

The tag has no usage guidance.

0
votes
1answer
2k views

Algorithm for finding best combination of elements

Say I have a very large, arbitrary number of variables, each of which I can assign to be type A, B, or C. The types come with expenses: Type A's are the least expensive, and C's are the most ...
7
votes
0answers
228 views

Can the solution to a POMDP be found using linear programming?

It is known that Markov decision processes (MDPs) can be solved using linear programming (see page 24 of Carlos Guestrin's PhD dissertation). The linear program is: $$min_{V(x)} \sum_x \alpha(x)V(x)\\...
3
votes
0answers
36 views

Card Shuffling, Bounding Mixing time using Paths and Flows

I've been struggling with a problem that is very similar to a 2014 question posted here. The question in particular is 3(1) and 3(2). To paraphrase, we are supposed to use paths and an encoding ...
3
votes
0answers
48 views

Calssifying the Partitions of the problem Cycle Decomposition of Markov Chains

The book Cycle Representations of Markov Processes solves the problem of Mapping Stochastic Matrices induced from a Markov Chain into Partitions using a $\lambda$-preserving ($\lambda$ is a Lebesgue ...
3
votes
0answers
147 views

Cheeger constant of a graph versus conductance of a Markov chain

Given some graph $G$ with vertices $V$ and edges $E$, its Cheeger constant $h(G)$ is well defined as $$ h(G) = \min_{S\subset V,0<|S|\leq|V|}\frac{|\partial S|}{|S|}. $$ Given some doubly-...
3
votes
0answers
147 views

Multicommodity flows with minimum congestion: NP-hard?

I have a question related to a paper of Chen, Lovasz and Pak [1]. The paper concerns the construction of the Markov chain with optimal mixing time on an arbitrary graph. They prove the optimal bound (...
2
votes
0answers
73 views

Solving the following recurrence relation derived from a Markov chain

I have the following system of recursive relations on $y_{i,j}$ that are derived from a Markov chain and that I am having difficulty in solving. For $i\ge 1$ and $j \ge 1$, we have $$y_{i,j} \times (...
2
votes
0answers
35 views

Calibrating a Markov Chain with little data

I am trying to calibrate a Markov Chain. Usually you would have the amount that "moves" from one state to the other and then the resulting value, with data at any given time with the following ...
2
votes
0answers
72 views

What is the meaning of the output weights of a Conditional Random Field (CRF) model?

Problem When train my linear chain CRF with annotated observations, I feed it with a number of sequences containing observation values and a "ground-truth" label for each observation. I'm currently ...
1
vote
0answers
52 views

Game with Random Digits (Markov Chain / Coupling)

I've been self-studying Markov Chains and came across a problem online here: http://websites.math.leidenuniv.nl/probability/lecturenotes/CouplingLectures.pdf I'm not asking for anything too formal (I'...
1
vote
0answers
103 views

Second-order Markov text generation?

Looking at this video starting at 1:45, the author claims to be using a second-order approximation for a Markov text generation. He has one letter which he outputs followed by another letter which ...
1
vote
0answers
52 views

Form of conditional observation probabilities in a POMDP

Consider a partially observable Markov decision process (POMDP), see here for a complete definition. My question is in relation to the conditional observation probabilities (denoted by $O(o|s',a)$ in ...
1
vote
0answers
86 views

Calculate expected values of “Craps Game” with the help of Prism Model Checker

I have modelled the craps game (https://en.wikipedia.org/wiki/Craps#Rules_of_play) as a dtmc with the prism model checker: ...
1
vote
0answers
30 views

Mixing time of three particle systems

Is there anything known about mixing time of Markov chains for three particle systems? It is proved here http://www.ams.org/journals/tran/2005-357-08/S0002-9947-05-03610-X/S0002-9947-05-03610-X.pdf ...
1
vote
0answers
362 views

PageRank and EigenTrust: How small should epsilon be?

For probabilistic algorithms such as PageRank and EigenTrust, the stopping case is given as $|R_{t+1} - R_{t}| < \epsilon$ (i.e. convergence is assumed). Neither the papers on EigenTrust or ...
0
votes
0answers
15 views

Name for this type of mixture of Markov chain?

Based on this paper, a mixture of Markov chains on a set $U$ is a $2$-tuple $(M,s)$ such that: $M$ is a set of $L$ Markov chains $\{M^1,\ldots,M^L\}$ on $U$(stochastic matrices such that $\sum_{y}M^i(...
0
votes
0answers
48 views

The relationship between MDP's end component and its induced MC recurrent class

Let's assume that I have an MDP $M$ which has a number of maximal end components. I also have a random policy (scheduler) $\pi$ that can convert the MDP $M$ into a Markov chain $m$. Can I argue that ...
0
votes
0answers
142 views

probability matrix from digraph adjacency matrix

All I have in hand is a adjacency matrix of a digraph with equal weight on every edge, is there a very simple way to convert this to a state change probability matrix?
0
votes
0answers
155 views

What's the relationship of max-flow-min-cut and Markov Random Fields?

I am trying to follow this paper [1]. There is a relationship between Markov Random Fields (MRF) to max-flow-min-cut. An MRF can be represented as an undirected graph, and you can find flow through it,...
0
votes
0answers
49 views

Graph Centrality: spectral techniques

What is the difference between: normalizing the row of an adjacency matrix and taking the right eigenvector normalizing the row of an adjacency matrix and taking the left eigenvector normalizing the ...