Questions tagged [markov-process]

A stochastic process with the property that the future is conditionally independent of the past, given the present.

0
votes
1answer
26 views

Markov chain inference confusion

I have a Markov chain where: A->B->C->D I am told that P(A,C,D|B) = P(A|B)P(C,D|B) I am unable to prove why this is the case. Why is this as such?
0
votes
0answers
47 views

MDP value iteration implemenation not yielding proper results?

I am attempting to find optimal policies and state value functions for the following MDP using my implementation in Python, however, I am not quite sure where my code is going wrong or what exactly it ...
0
votes
0answers
61 views

Finite irreducible Markov Chain are recurrent

Question: Show that all state in a finite irreducible Markov chain are recurrent. Attempt: First I considered that a finite irreducible Markov chain is transient. since there are only a finite ...
0
votes
0answers
186 views

expected time to enter a state in birth-death process

I have a question regrading the expected time of entering a state in a birth-death process. Specifically I don't quite understand Page 378 Equation 6.3 of the book here. It is about birth-death ...
0
votes
0answers
46 views

Estimation of infinitesimal generator/transition rate matrix from proportion data

Suppose I have a collection of data $\{\boldsymbol x_t \in \mathbb S^d\}_{t = 1,\dots,T}$ where $\mathbb S^d$ is the $d$-dimensional unit simplex, i.e. the elements of $\boldsymbol x_t$ sum to $1$. ...
2
votes
0answers
82 views

Markov Chain order 1 vs. AR(1) … Difference and Implication for Parameter Estimation

As other posts on this site indicate, the difference between a time-homogeneous Markov Chain of order 1 and an AR(1) model is merely the assumption of i.i.d. errors, an assumption that we make in AR(1)...
5
votes
1answer
160 views

Memoryless Property of a Markov Chain of Order 1. Is AR(1) memoryless or of infinite memory?

A stochastic process constitutes a discrete Markov Chain of order 1 if it has the memoryless property, in the sense that the probability that the chain will be in a particular state i, of a finite set ...
2
votes
1answer
49 views

Test statistic for lopsidedness of transition matrix

I'm trying to figure out how to estimate, given a transition matrix for a stream of distinct things, what the p-value is that the underlying stream is memoryless. In order to simplify the problem, I'm ...
0
votes
0answers
65 views

How to identify irreducible states by looking at a markov transition matrix?

I'm trying to find a simple way to look at a markov transition matrix and determine the subset of the states which form a closed, irreducible set of states. I came up with the following: If a set of ...
1
vote
1answer
41 views

Markov property definition

The definition of the Markov property is typically that the next state depends only on the present state and no past states. However, the mathematical definition I usually see (e.g. https://stats....
0
votes
1answer
28 views

Decision making in different intervals in MDPs

I want to model a problem as an MDP model where every day is divided into small time slots (for example minutes) and two decisions A and ...
3
votes
1answer
109 views

If the Markov assumption is wrong, will a learner still converge to a stable policy?

I'm trying to figure out what guarantees can be made if a learner wrongly assumes a problem obeys the Markov transition property. Assume I have a problem defined by a partially observable Markov ...
1
vote
1answer
49 views

Can some one explain me what is difference between Markov process and Markov Decision Process

Markov Process : A stochastic process has Markov property if conditional probability distribution of future states of process depends only upon present state and not on the sequence of events that ...
2
votes
0answers
24 views

Bound for the bias of ergodic averages for non-stationary Markov chains

Let $(\Omega,\mathcal A,\operatorname P)$ be a probability space $(\mathcal F_n)_{n\in\mathbb N_0}$ be a filtration on $(\Omega,\mathcal A)$ $(E,\mathcal E)$ be a measurable space $X$ be a $(E,\...
1
vote
1answer
54 views

Trouble understanding value iteration

I have trouble understanding how the value iteration algorithm for MDP:s work. I'm trying to follow the canonical grid world example (slide 17), but I don't get the correct results. Here's my work: ...
0
votes
0answers
51 views

Sensitivity analysis of transition probabilities in a Markov chain

Does anyone know of a method of sensitivity analysis for investigating the effect of perturbing transition probabilities $p_{ij}$ from a Markov transition matrix? I have a series of n=400 sequences ...
1
vote
0answers
22 views

Reinforcement learning for segmenting robot's path to reflect the true distances

I've a grid of rectangles acting as blocks. The robot traverses through the inter-spaces between these consecutive blocks. Now I have sensor data streaming in representing Right and left wheel speeds. ...
1
vote
1answer
43 views

What is an Expectation Maximisation Algorithm for Markov chains?

I'm looking for an algorithm for Expectation Maximisation of a Markov chain. I am aware of the Baum-Welch algorithm for Hidden Markov Models, but I can't find an algorithm for Markov Models that are ...
2
votes
1answer
79 views

POMDP books/lecture notes/tutorials

I'm looking for good references to learn more about POMDPs, preferably from a more mathematical stand point. The only good reference I've been able to find so far is: http://www.cs.toronto.edu/~...
0
votes
1answer
51 views

Generate PDF from CTMC

I have an irreducible continuous-time Markov chain (CTMC) with a finite state space. The CTMC also does not have any one-step transitions from any state to itself. I have the transition rate matrix $Q$...
1
vote
0answers
24 views

Can additional iterations of backward induction as described affect optimal policy?

Consider a game with the following properties: Single player Finite number of game states (after the player arrives at a terminal state, he or she can begin again from the start state; the player can ...
1
vote
0answers
39 views

Probability a transition is taken in a Markov Chain within a certain number of steps

Given a Markov Chain ${\{X_t\}}_{t \in T}$ which has a transition matrix $P$, and a random variable $N$ of possible transitions. The probability that a transition $n = (i, j)$ from $i$ to $j$ is ...
2
votes
1answer
322 views

Proof that an epsilon greedy policy w.r.t. $q$ values is better than the original policy $\pi$?

I was trying to understand the proof why policy improvement theorem can be applied on epsilon-greedy policy. The proof starts with the mathematical definition - I am confused on the very first line ...
1
vote
0answers
328 views

Irreducible Markov chain and transition matrix

We know that a matrix is irreducible if it is not similar via a permutation to a block upper triangular matrix. Is the transition matrix of a irreducible Markov chain irreducible?
1
vote
0answers
90 views

In a finite unichain average-reward MDP, how does optimal bias vector depend on stage reward

Consider a finite unichain MDP with stage reward $r$, state space $S=\{1, \dots, n\}$, action space A, and transition probability $p$. The Bellman equation is $$ h(i) + g= \max_{a \in A} ( r(i,a ) + \...
0
votes
0answers
101 views

Solve for value function in an infinite state space markov decision process?

If we have a finite state space, then we can write the value function $V^\pi(s)$ equation as: $$V^\pi(s)=R(s)+\gamma \sum_{s'\in \mathcal S} T(s'|\pi(s),s)V^\pi(s)$$ Where $\mathcal S$ is the state ...
2
votes
0answers
87 views

Predicting probability of next event happening

My Data is: TimeStamp <- time stamp of the event occurring Length <- length is the duration of the event ID <- identifier where the event is occurring ( 25 IDs) TimeStamp | Length | ID The ...
1
vote
1answer
23 views

How restrictive is the markov assumption?

Forgive me if this is a basic question. The markov assumption is generally taken to be restrictive in the texts that I've read. But intuitively it seems to me that we can turn any dynamic process ...
0
votes
1answer
22 views

Finding chain of observations using homogeneous Markov chain

I am reading about Markov chain and I understand how to find stationary distribution of a Markov chain and the transition probability matrix at some time t. But what I fail to understand how can one ...
9
votes
4answers
147 views

Worm and Apple Expected Value

An apple is located at vertex $A$ of pentagon $ABCDE$, and a worm is located two vertices away, at $C$. Every day the worm crawls with equal probability to one of the two adjacent vertices. Thus ...
3
votes
0answers
148 views

What is the relation between stationary distribution, limiting distribution, ergodicity and detailed balance equation in a markov chain?

I have studied them from various sources and I am not able to make a strong conclusion with respect to their relation with each other. This is what I understand by these terms Ergodic : If all ...
3
votes
1answer
139 views

How do the Atari games constitute a finite MDP?

I am still new to Deep-RL. I was reading DeepMind's paper "Playing Atari with Deep Reinforcement learning" and am having trouble understanding how these games can be represented as a finite markov ...
4
votes
0answers
52 views

Inferring a Markov chain from its invariant measure

Given a probability measure $p$ on $\{1,\dots,n\}$ assumed to be the invariant measure of some irreducible ergodic Markov chain with unknown transition matrix $P$, i.e., $p = pP$, what (if any) ...
0
votes
1answer
86 views

How can I find the expected value of these dependent values?

Okay so there's a game, where you have 1 percent chance of winning an alpha pack and if you fail you your chance goes up by 3 percent. How would you calculate the expected value? I've only taken an AP ...
2
votes
1answer
83 views

In Ian Goodfellow et al's paper “Generative Adversarial Networks”, why do they specify that they do not need a Markov chain or inference network?

In Ian Goodfellow et al's paper Generative Adversarial Networks, they state, "There is no need for any Markov chains or unrolled approximate inference networks during either training or generation of ...
3
votes
1answer
74 views

Interpretation of “scale function” in Foster-Lyapunov drift condition

I'm reading about Markov chains and I'm starting to bump into these drift conditions, and their relationship with a chain's ergodic properties. The drift condition is that there exists a "scale ...
0
votes
0answers
323 views

Computing Steady Probabilities for Markov Process

I hope I am asking this question on the correct SE, if not, please redirect it. I am trying to compute steady state probabilities for a Markov process using python. Knowing the transition rate values ...
0
votes
1answer
54 views

How to understand the term $\sum_{s', r}p(s', r|s,a)$ in Bellman's equation

One part from the bellman's equation in Sutton's "Reinforcement Learning: An introduction" confuses me: the third line contains the term $\sum_{s'}\sum_r{p(s', r|s, a)}$. The fact that it involves $\...
1
vote
1answer
46 views

how to solve this markov chain problem?

This is a problem in the book of "introduction to stochastic process ". Any help to solve this problem ??
2
votes
2answers
98 views

How to understand the $\pi(a|s)$ in Bellman's equation

I was reading "Reinforcement Learning, An Introduction" by Sutton and one of the variations of Bellman's Equation in the book confuses me: Equation (3.14) has the term $\sum_a{\pi(a|s)}$ in it. ...
1
vote
1answer
38 views

How can the support of proposal distribution impact convergence of RH-MH algorithm?

In the book Introducing Monte Carlo Methods by Casella and Robert, there's a sentence with which I'm having some trouble to understand. «If the domain explored in $q$ [proposal] is too small, ...
0
votes
1answer
58 views

Example of a Markov Process with observable states?

I have a pretty good handle on Hidden Markov Models, but I can't think of any examples of a Markov process with a directly observable state. Any examples?
0
votes
0answers
7 views

Defining state variables in negotiating agent

I am creating a negotiating agent using RL. For the states should I keep a state variable to keep in track which person is talking at the current time. Or should it just be the agent. as in ...
1
vote
0answers
23 views

Conditions on stationary distribution for continuous cases

Above is from my Bayesian notes, I have questions as: I know for discrete case, the stationary distribution $p(\theta)$ is defined as $$p(\theta) = A p(\theta)$$ where $A$ is the Markov Chain. But ...
0
votes
1answer
37 views

A sufficient condition $p(\theta)$ to be the stationary distribution is the reversibility

I was reading my notes, it says that: ''A sufficient condition $p(\theta)$ to be the stationary distribution is the reversibility: $$\sum_{\theta}p(\theta)p(\theta^*|\theta)=\sum_{\theta}p(\theta^*)...
0
votes
0answers
31 views

What is the correct terminology for simulating markov chains with state transitions observed from data

I'm struggling to find literature for a process I'm working on because I'm lacking the correct technical language to describe it. I have a markov chain with finite states which members of my ...
4
votes
0answers
88 views

How to estimate passengers destinations from flightradar data?

We have a graph with vertices corresponding to airports and edges corresponding to flights between those airports. On edge between airports A and B we have and number of passengers transferred from A ...
2
votes
1answer
73 views

How to estimate the kernel of a Markov process with continuous state-space, from a finite sample?

With a discrete state-space discrete time markov chain, given a sequence of sample data $X_{1} \dots X_{n}$, I might estimate the transition probabilities $P_{ij}$ using relative frequencies. From our ...
7
votes
1answer
131 views

The distribution of the initial point of an AR process

Consider a stochastic process $\{X_t, t = 1, 2, \ldots\}$ following the model $$X_t = \alpha X_{t-1} + e_t,$$ where $e_t \thicksim f$. Can I say that the distribution of the initial point, $X_1$, ...
0
votes
1answer
39 views

Sample conditional distribution from a Markov Chain

Suppose I have a Markov chain (initial distribution and transition matrix). Using this Markov chain I can generate an arbitrary length sequences. How can I effective sample (other than rejection ...