Questions tagged [markov-process]

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

Filter by
Sorted by
Tagged with
8
votes
1answer
8k views

Explain Backward algorithm for Hidden Markov Model

I have implemented Viterbi and Forward algorithm, alas strangely I can't understand how does Backward algorithm work. Intuitively I feel like I need to do the same thing as in Forward only backwards, ...
8
votes
1answer
122 views

Probability of a consecutive pair of values

Lets $X=(x_1, x_2,...x_{20})$ where $x_i\sim N(0,1)$ and $x_i, x_j$ are independent $\forall i\neq j$. What is the probability to obtain a sample $X$ where there are at least two consecutive values $...
8
votes
1answer
1k views

test if a markov chain is equal to a theoretical one

I have got an empirical transitions count matrix Q. I have a theoretical first order Markov chain P. Say N is the number of transitions. I would like to test if Q is compatible with P. Is it correct ...
8
votes
1answer
915 views

Gibbs Sampler transition kernel

Let $\pi$ be the target distribution on $(\mathbb{R}^d,\mathcal{B}(\mathbb{R^d}))$ which is absolutely continuously wrt to the $d$-dimensional Lebesgue measure, i.e : $\pi$ admits a density $\pi(x_1,....
8
votes
1answer
9k views

Why does a finite, irreducible and aperiodic Markov chain with a doubly-stochastic matrix P have a uniform limiting distribution?

The theorem is "If a transition matrix for an irreducible Markov chain with a finite state space S is doubly stochastic, its (unique) invariant measure is uniform over S." If a Markov Chain has a ...
8
votes
2answers
2k views

Policy and value iteration algorithm convergence conditions

Policy and value iteration algorithms can be used to solve Markov decision process problems. I have a hard time understanding to necessary conditions for convergence. If the optimal policy does not ...
8
votes
1answer
200 views

Optimal scaling of the Random Walk Metroplis-Hastings algorithm and the speed measure of the limiting diffusion

Let $d\in\mathbb N$ with $d>1$ $\ell>0$ $\sigma_d^2:=\frac{\ell^2}{d-1}$ $f\in C^2(\mathbb R)$ be positive with $$\int f(x)\:{\rm d}x=1$$ and $g:=\ln f$ $Q_d$ be a Markov kernel on $(\mathbb R^...
8
votes
1answer
576 views

Intuitive explanation/motivation of stationary distribution of a process

Often, in literature, authors have been interested in finding the stationary distribution of a time-series process. For example, consider the following simple AR($1$) process $\{X_t\}$: $$X_t = \alpha ...
7
votes
7answers
3k views

Average time ant needs to get out to the woods

An ant has three passages to choose from: Passage A takes 7 minutes to get ant out of the ant house to the woods. Passage B takes 8 minutes to get ant back to the starting point where he is. Passage ...
7
votes
2answers
16k views

How to define initial probabilities for HMM?

HI This is first time I was reading about HMM, however I have read so many articles on web, but two things where I am confused are: How to decide number of Hidden States (although HMM says we don't ...
7
votes
2answers
1k views

What if Markov chain does not converge in a reasonable amount of time?

I'm doing data analysis using Hamiltonian Monte Carlo for sampling from the posterior distribution of weights of a neural network. I'm using the Gelman-Rubin diagnostic estimated potential scale ...
7
votes
1answer
582 views

Markov chain,transition matrix and jordan form

If i have a transition matrix $$P= \begin{bmatrix} \frac12 & \frac14 & \frac14 \\ 0 & \frac12 & \frac12 \\ 0 & 0 & 1 \end{bmatrix}$$ i know that it's not diagonalizable,so if ...
7
votes
2answers
2k views

Markov Switching and Hidden Markov Models

Are the two interchangeable terms? I have been reading about markov-switching models and am struggling to see the difference with HMM models.
7
votes
2answers
8k views

Converting 2nd order Markov chain to the 1st order equivalent

Given a 2nd order Markov chain where each state takes values in the set $\mathcal{X}=\{A,C,G,T\}$, such that all transition probabilities $p(x_t|x_{t-1},x_{t-2})$ are larger than zero, How to convert ...
7
votes
1answer
1k views

Using $\chi^2$ to compare two Markov transition matrices

I have a set of observed Markov sequences for which I have calculated first and second order transition matrices: $$M={P}(X_i=x_i|X_{i-1}=x_j)$$ and $$M^2=P(X_i=x_i|X_{i-1}=x_j,\,X_{i-2}=x_i )$$. I ...
7
votes
1answer
610 views

Independent Bernoulli trials vs markov chain

Original Question Suppose we have a sequence of Bernoulli trials $X_1, X_2, \cdots X_T$ which are ordered in time and may or may not be independent. I am interested in understanding the probability of ...
7
votes
3answers
15k views

Determine the communication classes for this Markov Chain

Say we have a Markov Chain with probability matrix $$ P = \begin{pmatrix} 0.25 & 0.25 & 0.5 & 0 & 0 \\ 0 & 0.66 & 0 & 0.33 & 0 \\ 0 & 0.25 & 0.25 & 0.25 &...
7
votes
1answer
176 views

MDP and Sate Value Finding?

I have a complex MDP (I think) as follows. anyone can describe me simply how the value for state $V(A)^*$ is find? First Update: really for this solved question I need a canonical answer, step by ...
7
votes
1answer
828 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$, is ...
7
votes
1answer
755 views

Expected number of times you spent in a state of an absorbing markov chain, given the eventual absorbing state

It's well known that, if $Q$ is the matrix of transient state transition probabilities, and $$ N = \sum_{n=0}^{\infty} Q^n = (I - Q)^{-1}$$ then $N_{ij}$ describes the expected number of times the ...
7
votes
3answers
2k views

Markov decision process in R for a song suggestion software?

We have a music player that has different playlists and automatically suggests songs from the current playlist I'm in. What I want the program to learn is, that if I skip the song, it should decrease ...
7
votes
1answer
218 views

Gibbs Sampler output: how many Markov chains?

When running a Gibbs sampler (for $n=200$ Iterations) with two full conditionals, I get the output $\mathbf{x} = (x_1^{(n)},x_2^{(n)})_{n =1,...,200}$. So $\mathbf{x}$ is the realizations of a Gibbs ...
7
votes
2answers
12k views

Hidden Markov Model to predict the next state

I am learning to use HMM and I am trying to solve the following problem. There is a robot moving around the nodes in graph. The robot can move to adjacent nodes with certain probabilities. Each time ...
7
votes
1answer
137 views

How can we verify the intuition that in the RW-Metropolis-Hastings algorithm with Gaussian proposal too small and too large variances are bad choices

Let $d\in\mathbb N$ and consider the Random Walk Metropolis-Hastings algorithm with a Gaussian proposal kernel $Q$ such that $Q(x,\;\cdot\;)=\mathcal N_d(x,\sigma^2_dI_d)$ for all $x\in\mathbb R^d$. ...
7
votes
1answer
182 views

Finite state machine with gamma distributed waiting times

I have a state machine with positive and negative inputs. The time between positive inputs follows a gamma distribution ($X_+ \sim \Gamma(k_+, \theta_+)$), and the time between negative inputs follows ...
7
votes
1answer
3k views

Difficulty in understanding Hidden Markov Model for syntax parsing using Viterbi algorithm

I intend to apply Kevin Murphy's Hidden markov model (HMM) toolbox. I have a set of production rules(arbitrary) $A_0 \to AB [p=1]$, $A\to aC [p=1]$, $B\to bbC [p=0.5]$, $B\to b [p=0.5]$ where $A_0$ is ...
7
votes
2answers
162 views

Is there a measure of how well a Markov chain allows movement between states?

Define $$ A = \left( \begin{matrix} .5 & .5 \\ .5 & .5 \end{matrix} \right),\; \; B = \left( \begin{matrix} .99 & .01 \\ .01 & .99 \end{matrix} \right), \; \; C = \left( \begin{matrix}...
7
votes
2answers
2k views

Are two empirically estimated Markov chains statistically different?

I am constructing Markov chains (with 100 to 200 states) and inferring transition probabilities empirically by simply counting how many times I saw each transition in my raw data (about 20k to 60k ...
7
votes
1answer
2k views

Using autocorrelation to find commonly occurring signal fragments

I have a sensor which is capturing accelerometer data as a person walks. What I'm interested in extracting is each signal fragment when a step is taken. The Z-axis is what is used since only one axis ...
7
votes
0answers
318 views

Reinforcement *Model* Learning

Classical reinforcement learning (Q- or Sarsa-Learning) can be extended with models of the environment. These models are usually transition tables that contain the probability of arriving at a ...
6
votes
3answers
417 views

Probability after n steps

I have been studying markov chains for my Introductory Stochastic Processes exam, but i am struggling with the following problem: Question: Consider a matrix with state space $S=\{1,2,3\}$ and the ...
6
votes
3answers
642 views

Does “Markov Chain Monte Carlo” method really need “Markov Chain”? [duplicate]

I am studying MCMC with "Pattern Recognition and Machine Learning" Book by Christopher Bishop. In the chapter of MCMC, this book introduces Markov Chain also a little bit. However, while reading the ...
6
votes
4answers
4k views

Identify different periods of variance in a time series

I have a time series $x_t$ which may go through different phases of volatility. One example might be some stock that has high variance from 9 AM to 11 AM, low variance from 11 AM to 2 PM, and then ...
6
votes
1answer
3k views

What is the probability of rolling all faces of a die after n number of rolls

It is fairly easy to figure out what is the average number of rolls it would take to roll all faces of a die [$1 + 6/4 + 6/4 + 6/3 + 6/2 + 6/1 = 14.7$], but that got me thinking of a seemingly more ...
6
votes
1answer
3k views

Role of delays in LSTM networks

LSTM network is assumed to be about memory, keeping the important information for predictions. If it is the case, why do we need to consider delayed inputs as well? My assumption would be that the ...
6
votes
1answer
989 views

Confusion in Gibbs sampling

I am self-studying Gibbs sampling from a book. The book introduces metropolis hastings algortihm to generate representative values from a posterior distribution. So we know $p(D | \theta) p(\theta)$ ...
6
votes
2answers
858 views

Discrepancy measures for transition matrices

I'm doing some work on modelling transition matrices, and for this I need a measure of discrepancy or lack of fit: that is, if I have a matrix $T$ and a target matrix $T_0$, I want to be able to ...
6
votes
2answers
299 views

Comparing noisy data sequences to estimate the likelihood of them being produced by different instances of an identical Markov process

(Prompted to some extent by the answers already given by Shane and Srikant, I've rewritten this to try to clarify what I'm getting at, if only to myself.) Suppose we have several similar systems, ...
6
votes
2answers
179 views

Why does Judea Pearl call his causal graphs Markovian?

In his texts on causality, Judea Pearl always refers to the simplest graphs he uses, i.e. the acyclic graphs with independent confounders, as Markovian. I don't see why these graphs contain anything ...
6
votes
3answers
886 views

Probability of n-bit sequence appearing at least twice in m-bit sequence

Lets assume that we have a pattern $\alpha$ of bits of length $n$. Then I wish to know what the probability is of $\alpha$ appearing on a string of bits of length $m$ at least twice (where $m > n$),...
6
votes
1answer
7k views

What are the potential functions of the cliques in Markov random field?

I have been trying to understand the representation of the joint probability density of Markov random fields in the form of factors of the potential functions. I am finding it difficult to grasp the ...
6
votes
1answer
2k views

Maximum likelihood estimation procedures for state-space linear models

State-space models are represented by a state equation and an observation equation (or system of equations to be more precise). These equations are parametarized by components including a transition ...
6
votes
1answer
245 views

Trying to Estimate Disease Prevalence from Fragmentary Test Results

In response to the spread of COVID-19 disease, all Californians were ordered on 19 March 2020 to stay at home, except for such necessary errands as trips to grocery stores, pharmacies, etc. On 21 ...
6
votes
2answers
71 views

Markov chain ( Absorption)

I have just started learning Markov chain and I am clueless about how to solve this problem A man rolls a boulder up a 40 meter-high hill. Each minute, with probability 1/3 he manages to roll the ...
6
votes
1answer
371 views

Gibbs Sampler contradiction proof

I want to prove that the systematic scan Gibbs sampler yields an aperiodic chain $X$ on a general state space. Let $\pi$ be the stationary distribution for the resulting chain. Suppose to get a ...
6
votes
1answer
153 views

ergodic theory for markov processes

For an ergodic Markov Chain $$ \frac{1}{N}\sum_{i=1}^n f(X_i) \rightarrow E_\pi[f] $$ where $\pi$ is the invariant distribution. I am also dealing with a Markovian process (a state space model to ...
6
votes
1answer
125 views

In reinforcement learning, what is the correct definition of “value function”?

This is a follow up to: In reinforcement learning, what is the correct mathematical definition of the discounted reward? I discovered that there seems to exist an extremely large and disparate ...
6
votes
1answer
553 views

Markov chain as sum of iid random variables

Suppose I have a sequence of iid random variable, $Z_i$ for $i=0,1,2,3...$ such that $$\Bbb P(Z_i=z)= \begin{cases} p, &\text{if } z=1 \\ 1-p, & \text{if } z=0. \end{cases}$$ Define $S_k=\...
6
votes
2answers
478 views

Why do we need to use the Markov property in solving this PDE?

Given the PDE $$\frac{\partial G}{\partial t} + 0.5\sigma^2 \frac{\partial^2 G}{\partial x^2} = 0$$ with condition $G(T,x) = x^2$, one can use the Feynman-Kac formula to arrive at $$G(t,x) = E[X_T^...
6
votes
1answer
553 views

Can we get confidence intervals for entries in stationary vector for an absorbing, time-independent Markov chain?

I have a finite-state, time-independent Markov chain with two absorbing states which models educational outcomes (the absorbing states are completing and not completing). The transition probabilities ...

1
2
3 4 5
24