Questions tagged [markov-chains]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
0answers
20 views

Conditional dependence of Markov models

When studying Markov models, I see this equation but I don't understand where does it come from: $$ P(x,y,z) = P(x) P(y|x) P(z|y) = \frac{P(x) P(x,y) P(z,y)}{P(x) P(y)} $$ Can anyone explain to me?
1
vote
0answers
14 views

Degree of regularity of a Markov chain

A Markov chain with transition matrix $P$ is termed regular if for some $n$, all entries of $P^n$ are positive. Is there a known notion of degree of regularity quantified in terms of how soon all ...
0
votes
0answers
15 views

implementing a 802.15.4 math model based on a paper. How to verify it

I am implementing a mathematic model for predicting the congestion of 802.15.4 network based on the paper: Performance analysis of IEEE 802.15.4 non-beacon mode with the unslotted CSMA/CA Based on the ...
0
votes
1answer
64 views

Transition Function in MDP

I got a question about who and how sets the transation function values in markov decision processes? I mean when some says that an agent, in real world grid, is going to step up by %80 and left/right ...
2
votes
1answer
27 views

Policy dependent on initial state distribution in finite horizon MDPs

Consider an MDP defined as the tuple $\langle S,A,R,P,\mu,\lambda\rangle$ where $S$ is the state space, $A$ the action space, $R:S\times A\times S\to\mathbb{R}$ the reward function, $P$ the transition ...
0
votes
1answer
17 views

Asymmetric Transition Probability Matrix with uniform stationary distribution

I am solving a discrete Markov chain problem. For this I need a Markov chain whose stationary distribution is uniform(or near to uniform distribution) and transition probability matrix is asymmetric. ...
0
votes
0answers
32 views

Is there any toolbox for Markov Random Field Structure Learning?

I need a toolbox or software that takes a dataset as input, detect independencies among its random variables and produces the relative Markov Random Field graphical structure from that. Can anyone ...
1
vote
0answers
15 views

Concrete practical examples for discrete time markov chain with transition rewards

Can anyone show examples for discrete-time markov chains with associated transition rewards? I am searching for examples of industrial usage of markov chains where their expect and variance or ...
2
votes
1answer
55 views

Probability of terminating in a state in a probabilistic algorithm

Suppose i have a circular array of $n$ elements. At time $t=0$ i am in position 0 of the array. The algorithm moves left or right with probability $p=1/2$ (since the array is circular when it moves ...
0
votes
0answers
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 ...
0
votes
0answers
55 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 ...
4
votes
1answer
62 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
50 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
45 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
236 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
1answer
61 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
97 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 ...
1
vote
1answer
57 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
26 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
70 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
44 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
40 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
71 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
64 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
1k 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
344 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
483 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
134 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
60 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
88 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 (...
4
votes
1answer
990 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 ...
3
votes
0answers
90 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
144 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
193 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
317 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
61 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
190 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
263 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
467 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
99 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
600 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/...
6
votes
1answer
114 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
179 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
1answer
301 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
188 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
81 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
97 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
71 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
33 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
147 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} = \...