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
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 ...