# Questions tagged [markov-chains]

The tag has no usage guidance.

55 questions
Filter by
Sorted by
Tagged with
3k views

### What are Markov chains?

I'm currently reading some papers about Markov chain lumping and I'm failing to see the difference between a Markov chain and a plain directed weighted graph. For example in the article Optimal state-...
222 views

### Why are HMMs appropriate for speech recognition when the problem doesn't seem to satisfy the Markov property

I'm learning about HMMs and their applications and trying to understand their usages. My knowledge is a bit spotty, so please correct any incorrect assumptions I'm making. The specific example I'm ...
256 views

44 views

### Understanding simulated annealing information theoretically

So I recently rediscovered simulated annealing though a path that others seem to be well aware of. I was aware of Metropolis-Hastings as a sampling algorithm that creates a Markov-Chain who's ...
438 views

### The transition function in a Markov decision process

A Markov decision process is typically described as a tuple $\langle A,U,T,R \rangle$ where $A$ is the state space $U$ is the action space $T: A \times U \times A \mapsto [0,\infty)$ is the state ...
58 views

### Perturbing a Markov chain to be closer to a target stationary distribution

Suppose we are a given a Markov chain $A_0 \in \mathbb{R}^{n \times n}$ and a desired stationary probability vector $\pi_0 \in \mathbb{R}^n$. I would like to find a Markov chain that is as close as ...
679 views

### How many possible policies in a Markov Decision Process?

If a policy yields an action for a state, how come a 3-state MDP with 2 possible actions, i.e. $S = \{Hot, Mild, Cold\}$, $A = \{East, West\}$, has 8 possible policies? Isn't it 6 if there are 2 ...
110 views

### Seemingly non sequitur in proof

I'm trying to understand a small proof in an article about computing lumpability on Markov chains. There is a small detail that I cannot understand, i.e. I don't think it follows from the argument. ...
168 views

### Improve Markov Chain results

Apologies for another Markov Chain question but this one is best given its own question to avoid confusion. I am using a Markov Chain to get the 10 best search results from the union of 3 different ...
35 views

59 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'...
119 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 ...
124 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: ...
182 views

### How the conditional random fields algorithm work? [closed]

Im searching about conditional random fields for a long time and cant understand the concepts of this algorithm. I understood markov chains, and understood that conditional random field is a more ...
32 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 ...
380 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 ...
35 views

### Sampling Multiple Times From a Markov Chain

In probability theory, the mixing time of a Markov chain is the time until the Markov chain is "close" to its steady state distribution. Lets fix some $\varepsilon\in (0,1]$ as our closeness parameter....
27 views

### Find consensus trajectory of how a genetic algorithm solves an optimization

I have implemented a genetic algorithm to find the evolutionary outcomes of a biological scenario. I simulate the evolution (i.e. optimization) of five traits in my model. I ran my code 100 times and ...
13 views

### Monopoly Matrix Coding

I am an IB student doing SL math. For my math IA i picked the topic of monopoly and the optimal way to play. However, in this IA there is a massive matrix that needs to be built to see how the long ...
There is an information source on the information source alphabet $A = \{a, b, c\}$ represented by the state transition diagram below: a) The random variable representing the $i$-th output from this ...