Stack Exchange Network

Stack Exchange network consists of 174 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

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

0
votes
0answers
7 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$. ...
1
vote
0answers
8 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)...
4
votes
1answer
58 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
45 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
10 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
22 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
0answers
55 views

Markov chain: Show that states 0, . . N are essential and communicating with each other. What is the difference between essential and communicating?

Markov chain: Show that all states 0, 1, . . . , N are essential and communicating with each other. What is the difference between being essential and communicating in this case? By the definition ...
0
votes
1answer
25 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 ...
0
votes
0answers
13 views

Easy way to sample a Bayes posterior distribution of stable distributions?

I have a markov chain $P(x_{i+1}|x_i)=\rho(x_{i+1} ; \alpha,\beta,c, x_i)$, where $\rho$ is the stable distribution with mean $x_i$. I'm interested in fixing $x_1$ and $x_3$, and sampling an $x_2$ ...
2
votes
0answers
17 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 ...
0
votes
0answers
9 views

Initial state in multi-state model

I'm new on the topic of survival analysis and currently I have to build a multi-state model. I've read the articles of the msm and mstate R packages in the Journal of Statistical Software (msm, mstate)...
1
vote
1answer
28 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 ...
1
vote
0answers
19 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,\...
0
votes
0answers
5 views

Prove that value function is unique fixed point of bellman operator?

Given an MDP $(S,A,P,\gamma,R)$, the bellman operator is as follows: $$V(s)\mapsto R(s)+\gamma\cdot P_{\pi,s} V$$ Where $P_{\pi,s} V= \sum _{s'\in S}P(s'|s,\pi(s))\cdot V(s)$. Apparently, the value ...
0
votes
0answers
16 views

Multiple Imputation of time series data

I have many groups with a different number of members (learners). The members of each group came together in different time intervals whereupon not all members took part in each of their group ...
1
vote
1answer
36 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
8 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
20 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
30 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 ...
-1
votes
0answers
19 views

Is there a good text book on serial tempering?

I've read that serial tempering is an approach for "MCMC sampling from a sum of parametrized distributions". I've only found two papers (Marinari and Parisi and Geyer and Thompson) introducing this ...
0
votes
0answers
24 views

Relation between v(s) and q(s,a) in a Markov Decision Process?

I was solving questions related to backup diagrams from Reinforcement Learning: An Introduction by Barto and Sutton. Are these 4 equations mathematically correct ? Are there any shortcomings in terms ...
2
votes
0answers
22 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
18 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
21 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 ...
0
votes
0answers
12 views

MDP State Value Prediction

I'm wondering how probability works with MDP given policies. For example there are two state, [A] -> [B] -> Terminate. If there is 25% probability of not moving from state A and getting a reward of +...
0
votes
0answers
10 views

Efficient computation of joint distribution of state and previous state in absorbing Markov Chain

I have an absorbing discrete time Markov Chain with current state represented by the random variable $S_t$, previous state represented by the random variable $S_{t-1}$, with a known transition ...
1
vote
0answers
38 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
99 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
108 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
21 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
15 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
35 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
17 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
19 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
139 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 ...
2
votes
0answers
37 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
66 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 ...
3
votes
0answers
47 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
55 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 ...
0
votes
0answers
25 views

Right techniques to cluster/segment categorical data?

I am new to this forum and to data science. I might be naive in asking my question. I am working on customer transactions data. I have got data of ~143k customers; for each customer I have monetary ...
1
vote
0answers
32 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
59 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
75 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
32 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
37 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
59 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
28 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
19 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 ...
0
votes
0answers
9 views

Time Homogenous or Time Inhomogeneous Markov Model

Are there any tests to determine if one should incorporate a time homogeneous or time inhomogeneous markov model? Given a set of data are there any formal tests that can aid in the choice of Markov ...