The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [markov-process]

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

Filter by
Sorted by
Tagged with
0
votes
0answers
31 views

Sequence Prediction with noise / gap using markov models

I'm trying to understand if Markov models can account for a "noise event" when predicting the next item in a sequence. For instance, if i have very frequently occurring (noise) event "F", can a ...
0
votes
1answer
36 views

Long run proportion of transitions in a Markov chain

Let $S$ be a set of states for a Markov chain and let $S^C$ be the remaining states. Explain the identity $$\sum_{i\in S}\sum_{j\in S^C}\pi_iP_{ij}=\sum_{i\in S^C}\sum_{j\in S}\pi_iP_{ij}$$ I know ...
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^...
0
votes
1answer
78 views

Relation between Uniform distribution, Metropolis Algorithm, and Symmetric Proposal Distribution

I am having some confusion over the Metropolis algorithm. Let $g(x|y)$ be our proposal distribution for the algorithm. For the Metropolis, $g$ must be symmetric (from Wikipedia). In the discrete case, ...
4
votes
1answer
119 views

How can we numerically compute the autocorrelation of a sample from a Markov chain generated by the Metropolis-Hastings algorithm?

Let $(X_n)_{n\in\mathbb N_0}$ denote a $\mathbb R^d$-valued Markov chain generated by the Metropolis-Hastings algorithm. Suppose I've run the algorithm on a computer and obtained a sample $x_0,\ldots,...
2
votes
0answers
67 views

Numerical examples proving and disproving the optimal scaling heuristic by Roberts et al

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^...
0
votes
0answers
16 views

Calculate Transition Probabilities Interest rate data

I came across a paper by Rodda (2004), who simulates interest rates with a Markov sequence. To simulate changes in the interest rates, they used the historical transition probabilities. Their ...
1
vote
1answer
310 views

What is the relation and/or difference between Game Theory and Markov Chain Model? [closed]

I am doing some work regarding my master's thesis in networks security. I have decided to work with Game Theory, calculating the Nash Equilibrium for a two player zero sum game. However, I have also ...
0
votes
0answers
96 views

Transition probability in Markov chain using a decision tree model

I wish to find a way to calculate the transition probabilities in my Markov chain model. Let's say a customer has three products [A B C] and in this example I wish to know the transition probability ...
0
votes
0answers
12 views

How to calculate nth step in the binary sequence?

I have a dataset with 499 observations for a single binary variable. The objective is to predict the next observation in the series. Here is the dataset: 1 2 1 2 1 1 2 1 2 1 1 1 1 1 1 1 1 2 2 1 1 1 ...
0
votes
0answers
95 views

What is the difference between homogeneous Markov chains and unhomogeneous Markov chains?

I learned that a Markov chain is a graph that describes how the state changes over time, and a homogeneous Markov chain is such a graph that its system dynamic doesn't change. Here the system dynamic ...
3
votes
1answer
1k 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,...
1
vote
0answers
99 views

Markov Models for time series prediction

I am student conducting an experiment with different models for time series prediction. In my experiment, I am going to use ARIMA, a Recurrent Neural Network, a Long-Short Term Memory network, and a ...
2
votes
1answer
475 views

How to get P and R values for a Markov Decision Process grid world problem?

Take the canonical 3x4 grid world example below. What would the P and R matrices look like for this problem? I know that P would be AxSxS, and R would be AxS, but I'm having a lot of trouble ...
1
vote
2answers
454 views

Finding One Step Transition Matrix in Gambling?

I need help finding what a one step transition matrix would look like for the following gambling scenario: Using the bold strategy, say you have a certain amount of money x at any time and you're ...
2
votes
1answer
31 views

Distribution of Conditional Brownian Motion

Let $\ X(t),t \ge 0$ be a Brownian motion process. That is, $\ X(t)$ is a process with independent increments such that: $$\ X(t) - X(s) \sim N(0,t-s), 0\le s \lt t $$ and $\ X(0)= 0$. ...
1
vote
0answers
33 views

Finding Probability of a digit given a sequences?

I have a n sequences of numbers ranges from 1 to 4, say sequence s1 = [1,3, 1, 4] and s2 = [2,1,3,4] up to s(n). My question is how can i find probability of a number coming right after a sequence, ...
1
vote
1answer
44 views

Discrete-time Markov Chain; $n$-step transitions

Let $\{X_{n}\}_{n\geq0}$ be a discrete-time Markow chain on the state space $S=\{1,2,3\}$ with transition matrix \begin{pmatrix} 1/3 & 1/3 & 1/3 \\ 0 & 2/3 & 1/3 \\ 2/3 & 1/...
2
votes
2answers
169 views

Visualization of the number of transitions between states [closed]

I am currently developing a Markov model for ordinal data. In order to proceed with the modeling, I would like to check the distribution of the number of transitions per individual in my data set. ...
0
votes
0answers
31 views

Entropy/Measure of Knowledge for probability intervals

I have a system which outputs probability interval tuples over the decision set $\{d_1, d_2, d_3\}$, such that a tuple $([\min_1, \max_1], [\min_2, \max_2], [\min_3, \max_3])$ indicates that $\min_i$ ...
2
votes
0answers
25 views

Trouble understanding derivation of probability for continuous time markov chain

I'm working on exercise 6.10 from "Introduction to probability models" by Sheldon M. Ross. There's an expression for the probability $P_{00}(t)$ that I don't understand. Here's the relevant ...
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 ...
1
vote
0answers
59 views

How to use trial and error algorithm to predict the next number in a sequence?

I have a time series data. I want to use trial and error algorithms to predict the next number in a variation_sequence. I mean about Trial and error algorithm is using an online learning and where I ...
1
vote
1answer
69 views

Number of parameters in an Mth Order Markov Chain

For an $M^{th}$ order Markov chain, $P\left(X_n|X_{n-M}...X_{n-1}\right)$, what's the number of parameters required to know the conditionals? We have discrete variables each with $K$ states. I think ...
0
votes
0answers
27 views

Optimal strategies in a memoryless MDP

Consider the following theorem: Let $M$ be a finite MDP with state space $S$ and $B \subset S$. There exist a memoryless deterministic scheduler $\Theta^{min}, \Theta^{max}$ such that for any $s \...
0
votes
0answers
22 views

Bootstrap resulted in something that looks like a mixed distribution. What do?

TLDR Bootstrapping resulted in a crazy scatterplot. Totally clueless here. I have a dataset (not going to say much about it, it is a bit confidential), running a Markov chain-based algorithm on the ...
1
vote
0answers
84 views

States of Markov chain and stationary distribution

Let $X$ be a Markov chain with a state space $S={\{0,1,2,... \}}$ and a transition matrix $P$ with given $p_{i,0}=\frac{i}{i+1}$ and $p_{i,i+1}=\frac{1}{i+1}$, for $i=0,1,2,...$. Find out which states ...
1
vote
1answer
104 views

Irreducible (communicating) classes [closed]

The Markov chain $(Xn; n\geq)$ has state-space $S = (0, 1, 2, . . .)$, with $p_{i,0} = \frac{1}{4}$ and $p_{i,i+1} = \frac{3}{4}$ $\forall i \geq 0$, so that the transition matrix is P =$\...
0
votes
1answer
65 views

Biased coins and Markov processes

Good day, I am attempting an optional exercise and I am finding it hard to interpret the problem in terms of matrices and vectors. Coin 1 has probability 0.4 of coming up heads, and coin 2 has ...
0
votes
1answer
34 views

What does environment dynamic means in Reinforcement learning

From the book Reinforcement learning: an introduction, I have two questions: 1) there is the following sentence: "If the environment's dynamics are completely known, then finding the optimal policy ...
3
votes
1answer
163 views

Proving that given Markov chain is homogeneous. Find state space and transition matrix

Let $X_i$ be the results of a consecutive throws of a die. Let $Z_n=3(X_1^2+\cdots+X_n^2) \bmod 5$. Show that the sequence ${\{Z_n \mid n\geq1\}}$ is a homogeneous Markov Chain. Find a state space and ...
6
votes
1answer
173 views

Optimal scaling of the Random Walk Metroplis-Hastings algorithm and the speed measure of the limiting diffusion

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^...
0
votes
1answer
394 views

Determining the class of a new sequence using Markov chains

I want to use a Markov chain to classify a new given sequence as from model+ or model-. For that purpose first I trained two ...
1
vote
0answers
113 views

Expected number of steps in Gambler's ruin game with two players

Let's say we have two players A and B. Player A has 3 coins and player B has 5 coins. If player wins the other player gives one coin. During game second player probability of loosing is $2/3$, while ...
4
votes
2answers
3k views

When is the autocorrelation function of a stationary process decreasing/nonincreasing? Markovian?

When is the autocorrelation function of a stationary process strictly decreasing or nonincreasing? Can being Markovian make it true? When is the autocorrelation function of a stationary process (...
1
vote
1answer
138 views

Why is variational Bayesian mixture model an alternative to MCMC? What are the similarities?

Why do people say that a variational Bayesian mixture model could be an alternative to MCMC for clustering? For example see the details here: https://en.wikipedia.org/wiki/Variational_Bayesian_method. ...
2
votes
0answers
31 views

Importance of the right-continuity of filtration in definition of strong Markov Property

Taking the definition from wikipedia, With $X = (X_t : t \geq 0) $ as a stochastic process on a probability space $(\Omega, \mathcal{F}, \mathbb{P})$ with natural filtration $\{ \mathcal{F}(t) \}_{t \...
0
votes
1answer
45 views

Can a state have zero periodicity? [closed]

I am getting my concepts cleared in Stochastic process. I understand the concept of periodicity. Just to make it clear, suppose there is a finite Markov chain with states $1,2,3$. Let their ...
1
vote
1answer
71 views

Why is the probability of a random walk reaching 1 (in n steps) squared greater than the probability of it reaching 2 (in n steps)?

Let $S_n$ be a simple random walk. i.e. $$ S_n = \sum_{t=1}^n X_t, $$ where ${X_t}$ are i.i.d random variables with $$ X_t = \begin{cases} +1, & \textrm{w/ probability } p \\ -1, & \...
5
votes
3answers
10k views

Determine the communication classes for this Markov Chain

Say we have a Markov Chain with probability matrix $$ P = \begin{pmatrix} 0.25 & 0.25 & 0.5 & 0 & 0 \\ 0 & 0.66 & 0 & 0.33 & 0 \\ 0 & 0.25 & 0.25 & 0.25 &...
1
vote
0answers
32 views

Convergence in total distribution distance in the Random Walk Metropolis-Hastings algorithm

I'm searching for a proof of the convergence in total distribution distance of the transition probabilities of a Markov chain generated by the Random Walk Metropolis-Hastings algorithm to its ...
2
votes
0answers
60 views

Almost-Binomial Distribution (Different Success Chances per Trial)

Let's say I have received complaints that my coin is not random enough after some people got 10 heads. My coin was truly random, but I want it to feel random, not be random. This is a pretty common ...
0
votes
1answer
57 views

Generating very few samples from a probability distribution using MCMC?

Since MCMC converges to target only after taking very large number of steps, what if I want to have just say 10 samples from target distribution? Do I still have to generate lots of samples, and then ...
2
votes
0answers
102 views

Estimation of transition probability matrix (TPM) for a discrete time, continuous state markov chain from uniformly-spaced samples

I have uniformly spaced samples from a three-component (i.e. three nodes) Markov chain: $s^{(0)}=\begin{bmatrix}0.99\\ 0.01\\ 0.00\end{bmatrix}$, $s^{(1)}=\begin{bmatrix}0.98\\ 0.01\\ 0.01\end{...
28
votes
5answers
27k views

Difference between Bayesian networks and Markov process?

What is the difference between a Bayesian Network and a Markov process? I believed I understood the principles of both, but now when I need to compare the two I feel lost. They mean almost the same ...
0
votes
0answers
19 views

Residence times of the telegraph process ?

The telegraph process is a two state stochastic process defined by the master equation $$ \dot{\pi}_0(t) = \tau^{-1} \pi_1(t) - \sigma^{-1} \pi_0(t) $$ $$ \dot{\pi}_1(t) = \sigma^{-1} \pi_0(t) - \...
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 ...
2
votes
1answer
195 views

What is the difference betwen a time non-homogenous Markov Chain and a non-linear Markov Chain? Example

A time non-homogenous Markov Chain is one in which the transition probabilities are not constant over time. A non-linear Markov Chain is a model that is not linear in parameters and satisfies the ...
1
vote
0answers
34 views

How to create the initial ensemble samples for EnKF

As we know, for the ensemble Kalman filter (EnKF), we need to create a set of samples in the beginning and then to run the predict and analysis step. But for now I have a question of how to create the ...
0
votes
0answers
97 views

Formulating a Transition matrix for Markov Process

I am dealing with a medical process which is as follows. There are 10000 Veterans who are enrolled in this study. All 10000 have medical condition called onychocryptosis which is a fancy term for ...