Questions tagged [markov-process]
A stochastic process with the property that the future is conditionally independent of the past, given the present.
376
questions with no upvoted or accepted answers
7
votes
0answers
307 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
389 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
317 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
299 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
66 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
120 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
273 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
96 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
217 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
450 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
388 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
743 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
358 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
301 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
74 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
166 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
57 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
59 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
43 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
286 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
361 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
0answers
99 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
73 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
99 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
208 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
562 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
974 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
156 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
163 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
494 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
211 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
422 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
442 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
547 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
686 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 ...
