Questions tagged [markov-process]

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

459 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
9
votes
1answer
427 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_{...
7
votes
0answers
316 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
91 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 ...
5
votes
0answers
262 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 $\...
5
votes
0answers
133 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 ...
5
votes
0answers
327 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
405 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 ...
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
63 views

Markov chain with stopping times

I have a Markov chain with transition matrix $P$, with transition probabilities: $$p_{i,j}= \begin{cases} 1-d, & \text{if $i=j \gt 0$} \\[2ex] d , & \text{ if $j=i-1 \gt 0$} \\[2ex] (1- \...
4
votes
0answers
1k views

Detailed Balance for Hamiltonian Monte Carlo

I am trying to understand the detailed balance proof present in this paper: https://arxiv.org/abs/hep-lat/9208011v2 (page 4). My question: Why do we consider the volume of a neighborhood of points ...
4
votes
0answers
72 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 \\ ...
4
votes
0answers
389 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 ...
4
votes
0answers
82 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
191 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
340 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
100 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
506 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
78 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
760 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
403 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
373 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 ...
4
votes
0answers
98 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
53 views

Reduce the asymptotic variance for a class of Metropolis-Hasting estimates

I'm running the Metropolis-Hastings algorithm with state space $E$, target distribution $\mu=p\lambda$ and proposal kernel $Q$ to estimate $\mu(hf)$ for a fixed function $f:E\to[0,\infty)^3$ and a ...
3
votes
1answer
124 views

Point process model diagnostic: Nearest-Neighbor Distance Distribution or Pair Correlation Function?

I have a point pattern which is clearly inhomogeneous. Furthermore, the inhomogeneity has two components: a large scale effect and a local scale effect. I have constructed a Markov point process model ...
3
votes
0answers
32 views

Model or State Uncertainty in Queueing Model due to uncertain arrival rate

$\textbf{Introduction}$ I am currently modelling a scenario where two queues need to be served by a single server in a non preemptive discipline. I am quite sorted on generating the optimal policy ...
3
votes
0answers
169 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
668 views

Justification of acceptance probability in simulated annealing

In simulated annealing the acceptance probability for a new state in step $k$ is traditionally defined as $$ P(\text{accept new})= \begin{cases} \exp(-\frac{\Delta}{T_k}), & \text{ if } \Delta \...
3
votes
0answers
319 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
82 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
63 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
1answer
186 views

Markov Chain - “Expected Time”

The Megasoft company gives each of its employees the title of programmer (P) or project manager (M). In any given year 70 % of programmers remain in that position 20 % are promoted to project manager ...
3
votes
1answer
2k views

Why is the optimal policy non-stationary in the case finite-horizon problems, whereas it is stationary in the case of infinite-horizon problems?

I have difficulty understanding the meaning of stationary policy in the RL (MDP) setting. Specifically, let's assume stationary dynamics $$P(s_{t+1}=j|s_t=i,a) = P (s_{k+1}=j|s_k=i,a) \ \forall t,k,i,...
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
385 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
63 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 graph $...
3
votes
0answers
111 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
102 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
92 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
0answers
120 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
166 views

Is there a survey that explores all the available Markov chain Monte Carlo methods?

I am interested in exploring the efficacy of various Monte Carlo methods. I am aware of the Metropolis acceptance criterion, Hamiltonian Markov chains, Gibbs sampling, importance sampling, slice ...
3
votes
0answers
270 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
62 views

How can we say that $B_n$ is a Markov process (or something)?

From Probability with Martingales: I chose $\mathscr F_n = \sigma(B_1, B_2, ..., B_n)$. My argument assumes that $E[M_n | \mathscr F_{n-1}] = E[M_n | B_{n-1}]$. I was able to show that $M_{n-1} = E[...
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
640 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
1k 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
75 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
164 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
67 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
194 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
503 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 ...

1
2 3 4 5
10