Questions tagged [markov-process]

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

7
votes
0answers
302 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 ...
5
votes
0answers
89 views

How does the celebrated result about the diffusion limit of the Random Walk Metroplis-Hastings algorithm help us to find the optimal scaling

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^...
5
votes
0answers
1k views

Laplace smoothing parameter choice for Markov chain transitions

Let $Y_{t}$ be the state of the process at time $t$, ${\bf P}$ be the transition matrix then: $$ {\bf P}_{ij} = P(Y_{t} = j | Y_{t-1} = i) $$ Since this is a Markov chain, this probability depends ...
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) ...
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 ...
4
votes
0answers
58 views

Analogue of spectral gap but for *smallest* eigenvalues/singular values

The difference between the largest eigenvalue and the next-largest of a graph Laplacian (equivalently, of the random walk Markov chain on the graph) is the spectral gap, related to the Cheeger ...
4
votes
0answers
94 views

Clustering Markov Chains

Assume I have a finite set of elements $$A={X_0,X_1,...,X_{n_1}}$$ where every element is itself a finite Markov sequence (i.e. $S_{i+1} \sim P(S_i)$) $$X_i={S_0,S_1,...,S_{n_2}}$$ Suppose I also ...
4
votes
0answers
260 views

Find the invariant measure $\pi=(\pi_{1},\pi_{2},\pi_{3})$ for a Markov Chain with transition matrix given

Let $(X_{n})_{n\in\mathbb{N}_{0}}$ be a Markov Chain with state space $M=\left\{x_{1},x_{2},x_{3}\right\}$ and transtition matrix $$ \Pi=\left(\begin{array}{ccc}p_{1} & p_{2} & 1-p_{1}-p_{2}\\ ...
4
votes
0answers
91 views

Markov Chain Monte Carlo (MCMC): How many samples are needed to get a uniform sample?

I am interested in a general answer although my question is rooted in a specific document. I am using the R package "hitandrun": https://cran.r-project.org/web/packages/hitandrun/hitandrun.pdf On ...
4
votes
0answers
199 views

What is the density of a markov chain when its transition probabilities have densities with respect to different measures?

I have a homogenous, discrete time Markov process, $(X_n)_{n\geq 0}$, with state space $\mathbb R_+$. Its transition probabilities have a density, $f(x_n\mid x_{n-1})$, with respect to the measure $\...
4
votes
0answers
440 views

Decomposing the non-deterministic transition functions in non-Markov decision processes into several deterministic transition functions

Problems in reinforcement learning are commonly modeled as Markov decision processes (MDPs). One essential part of MDPs is the transition function $T: S \times A \times S \rightarrow [0, 1] \in \...
4
votes
0answers
291 views

Dynamics of birth-death process with discouraged arrivals (alternatively, M/M/1 queue with balking customers)

Take a continuous-time birth-death process, where $k \in \{0,1,\ldots\}$ is the count and the arrival rate of death is $\mu \geq 0$ for $k = 1, 2, \ldots$ the arrival rate of births is $\alpha_k > ...
4
votes
0answers
75 views

Calculating the first time a particle hits a state

Let $(X_{n})$ be a Markov chain with state space $D=(a,b,c)$ and transition matrix $$P= \pmatrix{ 0.4 & 0.6 & 0 \\ 0.5 & 0 & 0.5 \\1 & 0 & 0 \\}$$ A) Find the lim$_{n-> \...
4
votes
0answers
376 views

How Should I Find Statistically Significant Differences Between Two Markov Models?

Suppose I have N Markov Models of M states representing the behaviour patterns of 2 different groups (note: fully observable models, no hidden states), and have stored each model as a matrix of ...
4
votes
0answers
734 views

Easy to follow tutorial on using Markov Random Fields for classifying pixels in gray-scale images

I am trying to learn how to use Markov Random Fields for classifying pixels in an image. Could someone please direct me to a simple tutorial demonstrating how this is done. The tutorial needs to ...
4
votes
0answers
342 views

Application of likelihood ratio test to test the Markov property

Do you know a reference (freely available on the web) where the likelihood ratio test is applied in order to test for the Markov property? The setting is a directly observable discrete Markov-chain ...
4
votes
0answers
281 views

Convergence theorem for Gibbs sampling

The convergence theorem for Gibbs sampling states: Given a random vector $X$ with components $X_1,X_2,...X_K$ and the knowledge about the conditional distribution of $X_k$ we can find the actual ...
3
votes
0answers
59 views

Estimating a MS-ARMA(p,q)-GARCH(r,s) parameters via MCMC

I am currently working on a MS-ARMA-GARCH model proposed by Dhiman das on this paper, and trying to fit it on simulated data. So far I understand the model and its construction, but I'm having a hard ...
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
0answers
55 views

Deriving Autocorrelation Structure for Binary Markov Chain

I'm trying to derive the autocorrelation structure of a Binary Markov Chain with \begin{align} Pr(s_t=1 | s_{t-1}=1) &= q \\ Pr(s_t=0 | s_{t-1}=1) &= 1-q \\ Pr(s_t=0 | s_{t-1}=0) &= p \\ ...
3
votes
0answers
58 views

Stationary density of $\{X_t\}$ as a solution of integral equation

For the model, $X_t = \alpha X_{t-1} + \epsilon_t$, we find the integral equation related to stationary distribution in the following way: Let $X_{t-1}\thicksim f$ and $X_t|X_{t-1}=x \thicksim q(y|x)$...
3
votes
0answers
38 views

How to approach Basketball “Beat the Pro” drill with Markov Chain

Suppose, similarly to Gambler's ruin problem a Basketball player is doing "Beat the Pro" drill. That is, for every shot made, he scores one point, and for those missed, two points are to be deducted. ...
3
votes
0answers
270 views

Convergence of approximate Gibbs sampling

We have a bivariate random variable $(X,Y)$ for which sampling is challenging. If we were to know how to sample from the conditionals $(X|Y)$ and $(Y|X)$, we could get samples from the joint using ...
3
votes
0answers
36 views

Using Monte Carlo to find a posterior probability distirbution (distirbution propagation)

Using Monte Carlo to propagate error is a well known technique. To do that, one usually uses the Markov equation to find the posterior distribution $$ P(y|\mathbf{a})= \int \delta(y-F(\zeta))P(\zeta ...
3
votes
0answers
336 views

How to use MCMC / gibbs sampling instead of an optimization algorithm ?

I've tried and implementend Factorization Machines with different loss functions and optimization algorithms (SGD , coordinate descent, adagrad, adadelta ...) and I've seen that it's possible to use ...
3
votes
0answers
59 views

Confusion on three “types” of Markov Chain Monte Carlo for the same inference

This is a long question but I would be very grateful if someone can help or provide some reference! And I believe this is a common confusion among beginners of MCMC. Background Given a directed ...
3
votes
0answers
91 views

Parallel tempering mcmc and space transformation

In parallel tempering mcmc you want to sample a probability density $p$ and to do this you sample $p$ and $p_i = p^{1/T_i}$ for a sequence of temperatures $T_i$. When $T_i$ is big the distribution is ...
3
votes
0answers
95 views

Calculating the probability to die in a card game using Markov chains

I saw this interesting question on reddit and couldn't figure it out. Situation There is a special card in the game seen below: Once this card gets played, there are 6 options that can happen. Only ...
3
votes
0answers
97 views

Markov model parameter concentration and Fisher Information Matrix

For iid data, the posterior on the parameter $$ p(\theta \mid x_{0:T}) = \prod_{t=0}^T p(x_t \mid \theta) p(\theta) $$ is known to become independent of the prior which is the Bernstein-von Mises ...
3
votes
0answers
193 views

how to write down dynamical state space models with deterministic variables in PyMC?

is it possible to write down this simple dynamical system in pymc? $R_0 \sim Normal(\mu_r, \sigma_r)$ $Z_0 \sim Normal(\mu_z, \sigma_z)$ $R_t \sim Normal(R_{t-1}, \sigma_r)$ $Z_t = Z_{t-1} + R_{t-...
3
votes
0answers
113 views

How can I determine the expected value / risk of ruin of game where probability changes dependent on state?

Consider the following game: You are given a random number generator which you can use to play a game. The object of the game is to reach the final tier after which you collect prize tokens. In ...
3
votes
0answers
2k views

How to understand Gibbs distribution

I have a graph model such as Following the Hammersley–Clifford theorem describes that Markov random fields exhibit a Gibbs distribution with an energy function as follows: $$P(x)=\frac {exp(-U(x))}{...
3
votes
0answers
944 views

simulating birth death process with random numbers from negative binomial

I am trying to generate random deviates for the population size at time $t$ for a birth-death process with constant birth and death rates per individual and initial size $N_0 \gt 0$. For the simple ...
3
votes
0answers
73 views

Refining “good” mixing time estimate

Fix a Markov chain $\{ X_{t} \}_{t \in \mathbb{N}}$ with mixing time $\tau_{\mathrm{mix}}$. Assume that I know some finite bound on the mixing time $\tau_{\mathrm{mix}} < \tau < \infty$, and ...
3
votes
0answers
153 views

Markov Chain exercise in an exam

Suppose that $X_1, X_2, X_3... $ is a Markov chain with the following transition matrix: State: | 1 2 3 --+----------- 1 |0.2 0.4 0.4 2 |0.5 0.0 0.5 3 |0.6 0.3 0.1 (forgive my attempt at a ...
3
votes
0answers
64 views

Convergence time of a Markov chain

We know that a regular Markov chains converges to a unique matrix. The convergence time maybe finite or infinite. My interest is in the case where the convergence time is finite. How can we accurately ...
3
votes
0answers
154 views

Autoregressive Markov chain simulation and the likelihood ratio test for Markov property

I am trying to estimate a Markov chain of second order (Markov chain that fulfills $P[X_t|X_{t-1},X_{t-2}]=P[X_t|X_{t-1},X_{t-2},...,X_{t-p}]$) using an AR(2) process. Once I have simulated the ...
3
votes
0answers
492 views

How to find a conditional probability using copula-based Markov process?

I have a monthly time series of a water quality parameter. I used copula-based Markov process of C(Y(t), Y(t-1) and I forecasted the mean behavior of Yt by following equation: Now, I need to find ...
3
votes
0answers
167 views

Continuous time Markov chain forward equation

This is a homework question and I need suggestion how to approach it. We have given the transitions $\ i\rightarrow i+1$ with rate $\lambda(i)$ where $\ i \ge 1$ $\ i\rightarrow i-1$ with rate $\...
3
votes
0answers
199 views

What is the expected number of steps before the spider exits? Markov Chain

A little spider lives in a rectangular box of which the sides are 3 and 4 cm long. It can only sit in one of the four corners marked with the numbers 1,2,3,4 (clockwise). Assume in Corner 2 there is a ...
3
votes
0answers
406 views

Estimating non-stationary Markov chain transition probabilities from data

I have some call centre outcome data: each person is called several times, and the result of the call is recorded as one of a few discrete outcomes ("no answer", "wrong number", "third party", "...
3
votes
0answers
440 views

How do sudden spikes affect hidden Markov models

I have some data that has two sudden spikes (almost like extreme masses or Dirac delta functions) within my time series data and I was wondering if that is a problem when building hidden Markov models....
3
votes
0answers
528 views

Are running mean plots good indicators for time series convergence?

I want to know whether a time series has converged. I looked around the MCMC literature (which requires doing something similar -- knowing whether a chain has converged) and found the following: http:...
3
votes
0answers
1k views

How to compare two matrices?

I am working on Markov transition matrices. I would like to find a statistical test to compare them. The first matrix is considered the population transition matrix and the second one is obtained by ...
3
votes
0answers
663 views

Baum-welch algorithm: probabilities after each step

In an effort to understand machine learning, at least to some degree, I've been implementing the various algorithms to solve the three problems in a Hidden Markov Model. I've been using Rabiner's ...
3
votes
0answers
88 views

Is there any way to define a distance metric given a Hidden Markov Model?

Let's say I've gotten a HMM that describes user search strings for my e-commerce website. Let's also say that I've just received a search string from a customer that doesn't have any search results. ...
3
votes
0answers
245 views

Summing values of state transitions accumulated in an absorbing Markov chain

I am trying to simulate a process as an absorbing Markov chain model, but I haven't been able to find the scenario that I am interested in looking at in the typical discussions of Markov chains online....
3
votes
0answers
388 views

CDF of first passage time for Poisson dam/shot noise with constant amplitude jumps and exponential decay

I'm looking for a CDF (either exact or approximation) of the first passage time, $T$, of a storage process $\{X(t); 0 \leq t < \infty \},$ with constant (unit) input jumps occurring in a Poisson ...
2
votes
0answers
19 views

What is the relation between expected average reward and single step mean reward for a non-stationary MDP policy?

The expected average reward for a policy $\pi$ is: $$ \rho_\pi = \lim_{T \rightarrow \infty } \frac{1}{T} \sum_{t=1}^{T} r_t$$ where $r_t$ is the reward obtained at time $t$ following policy $\pi$. ...
2
votes
0answers
29 views

Understanding Approximate Dynamic Programming

I am trying to write a paper for my optimization class about Approximate Dynamic Programming. I found a few good papers but they all seem to dive straight into the material without talking about the ...