Questions tagged [markov-process]

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

372 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
7
votes
0answers
306 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 ...
7
votes
1answer
385 views

Markov Switching Forecast. How can I derive this?

Consider the autoregressive model, $\left[ \begin{array}{l} y^{\ast}_t\\ x_t^{\ast} \end{array} \right] = \left[ \begin{array}{l} a_{11}\\ a_{21} \end{array} \begin{array}{l} a_{12}\\ a_{...
5
votes
0answers
96 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
1answer
308 views

Getting ROC curve from markov chain in r

I've been working on some attribution modeling in R, following the markov chain-based methodology described here. In order to compare the sensitivity and specificity trade-offs of using models of ...
5
votes
0answers
295 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 > ...
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
54 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
60 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
105 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
265 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
95 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
208 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
443 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
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
385 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
742 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
354 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
292 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
68 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
155 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
56 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
41 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
277 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
353 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
93 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
1answer
203 views

Markov process with future knowledge

Let's say we have a discrete-time Markov chain with a transition matrix $P$. If we know the initial state $x_0$, we can predict the probabilities of future states by iterating the chain as $x_{t+1}$ = ...
3
votes
0answers
96 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
1answer
71 views

Regret Minimization with Hidden Markov Processes

Consider a hidden Markov process with two states $\{0, 1\}$ represented with $Z_t$. The transition matrix is unknown, although we can assume it's strongly diagonal (i.e. slow-switching). At any time, ...
3
votes
1answer
1k views

From Markov Decision Process (MDP) to Semi-MDP: What is it in a nutshell?

Markov Decision Process (MDP) is a mathematical formulation of decision making. An agent is the decision maker. In the reinforcement learning framework, he is the learner or the decision maker. We ...
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
201 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
114 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
553 views

How to estimate Markov chain transition probabilities with partially observed data?

Suppose that we have a time-homogeneous discrete-time Markov chain $(X_n)$. We want to estimate the transition probabilities $p_{ij} = \mathbb{P}[X_{n+1} = j \mid X_n = i]$. In the case when we have ...
3
votes
0answers
954 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
74 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
161 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
168 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
202 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
418 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
441 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
534 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 ...