Questions tagged [markov-chains]
The markov-chains tag has no usage guidance.
51
questions
4
votes
0answers
40 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 ...
2
votes
2answers
45 views
Modeling a set of probabilistic concurrent processes
I'm looking into discrete-time Markov chains (DTMCs) for use in analyzing a probabilistic consensus protocol. One basic thing I haven't been able to figure out is how to model a set of independent ...
3
votes
1answer
31 views
Algorithm for computing $Pr[s \vDash C \bigcup^{\geq n} B]$ for probabilistic verification
I'm having some difficulty trying to come up with an algorithm for computing $Pr[s \vDash C ~\bigcup^{\geq n} B]$ given a finite Markov chain where $S$ is the set of states, $s \in S$, $B,C \subseteq ...
2
votes
1answer
121 views
Calculating probability of reaching state in DTMC
Consider a highly-connected graph of states & transitions where each transition is marked with a weight (representing probability of occurring) and the graph satisfies the Discrete Time Markov ...
1
vote
0answers
28 views
Vorticity Matrix for Markov chain
I have a markov chain with $Q(u,v)$ as transition probability matrix and $\pi(u)$ as stationary distribution defined on state space $\Omega$. The dimension of matrix $Q$ is $nxn$ and vector $\pi$ is $...
0
votes
1answer
48 views
information theory, find entropy given Markov chain
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 ...
0
votes
0answers
13 views
Logical inference as Markov decision process?
Are there efforts to consider forward or backward (theorem proving) logical inference process as Markov decision process in which the the action space is: 1) selection of the inference rule (e.g. from ...
1
vote
1answer
33 views
How to find optimal token set for compression?
By token I mean the smallest element of source data, that the compression algorithm works on. It may be a bit (like in DMC), a letter (like in Huffman or PPM), a word, or variable-length string (like ...
1
vote
1answer
24 views
Probabilisitc timed automaton
I am kind of new to timed automaton domain. I am trying to understand in which way they are different to Markov Decision Process. First I know there objectives is to solve the non-determinism of a MDP....
3
votes
1answer
50 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 ...
0
votes
1answer
34 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....
2
votes
0answers
37 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 ...
0
votes
0answers
59 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 ...
1
vote
0answers
58 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'...
3
votes
1answer
662 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 ...
1
vote
1answer
294 views
Why in simulated annealing, thermal equilibrium need to be meet for each temperature throughout the iterations?
I have read in this book, simulated annealing, on page 40-41, if temperature $t$ tend to $0$, then the stationary distribution will be distributed among optimal solutions. What i can not understand ...
2
votes
3answers
431 views
Why do we need Gibbs sampling (and MCMC)?
I just learned about Gibbs Sampling which is an MCMC method. Given a distribution $\pi$, we want to sample an item according to $\pi$.
Maybe my alternative suggestion would sound somewhat naive (even ...
1
vote
0answers
112 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
1answer
55 views
Maximize entrywise 1-norm of matrix product
I have $8$ sets $E_1, \ldots, E_8$, each one of size $256$, whose elements are $4\times 4$ matrices of (nonnegative) integers. I'd like to design an algorithm to find:
$$\underset{M_1 \in E_1, \...
2
votes
0answers
81 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
1answer
718 views
Absorbing Markov Chains: An efficient algorithmic approach
Following this procedure I have successfully written a program to calculate the probability of ending in a given absorbing state given the initial state. The procedure is as follows:
Given the ...
2
votes
0answers
67 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
122 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:
...
0
votes
0answers
184 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?
2
votes
1answer
288 views
Convergence of Markov model
I was learning Hidden Markov model, and encountered this theory about convergence of Markov model.
For example, consider a weather model, where on a first-day probability of weather being sunny was 0....
3
votes
0answers
53 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 ...
1
vote
0answers
181 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 ...
0
votes
0answers
189 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,...
3
votes
2answers
434 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 ...
2
votes
1answer
92 views
Orderability of Belief States in a POMDP?
Consider a POMDP with integer states $1,2,\ldots,N$, where $N$ is finite. We thus have a complete order over the states.
It seems reasonable to think that belief states for this POMDP may be ...
1
vote
1answer
448 views
Markov Chain Mixing Time of the Complete Graph
I'm having a hard time understanding mixing time for Markov Chains on Complete Graphs (Kn).
We can define the probability matrix for Kn where Pi,j=probability of going from i to j (technically 1/...
5
votes
1answer
102 views
Clarification of the definition of a POMDP
From what I understand, a $MDP=(G, A, P, R)$ (markov decision process) is represented as:
A complete directed graph $G=(V, E)$
A set of actions $A_u$ for each vertex $u \in V$
A reward function $R$ ...
2
votes
0answers
157 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-...
7
votes
0answers
252 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
158 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 (...
1
vote
1answer
79 views
Simulating continuous time semi-Markov state machine and changing transition probability on the fly
The problem that I'm trying to solve (well, I think that I almost did, but need a review from someone more experienced) is about changing probability of the transition for semi-Markov state machine ...
2
votes
2answers
92 views
How to sample random game input that looks similar to human control?
What I would like to do is improve upon projects like 'RNG plays pokemon'. There, a computer produces a random sequence of inputs that are transmitted to an emulator and played in-game. Though this ...
2
votes
0answers
53 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 ...
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
...
4
votes
1answer
136 views
Average vs Worst-Case Hitting Time
Consider a simple random walk on an undirected graph and let $H_{ij}$ be the hitting time from $i$ to $j$. How much bigger can
$$ H_{\rm max} = \max_{i,j} H_{ij}, $$ be compared to
$$ H_{\rm ave} = \...
3
votes
1answer
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.
...
2
votes
0answers
94 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 ...
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 ...
9
votes
2answers
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-...
1
vote
1answer
293 views
Markov Chain w/ non-stochastic matrix
I've come across a problem which at first appeared to be a markov process however the transition matrix of the graph is non-stochastic. That is, the probabilities among edges leaving a node do not sum ...
7
votes
2answers
215 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 ...
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 ...
1
vote
0answers
376 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 ...
1
vote
1answer
446 views
How are Bayesian Nets, Hidden Markov Chains, Conditional Random Fields and Neural Nets related?
I am having an AI exam in two weeks, and I am still figuring out certain concepts and ideas, related to Bayesian Nets, Hidden Markov Chains, Conditional Random Fields and Neural Nets (yes it is all ...
3
votes
1answer
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 ...
