Questions tagged [markov-process]

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

8
votes
1answer
208 views

Mars attack (probability to destroy $n$ spaceships with $k \cdot n$ missiles)

Suppose Earth has been attacked by $n$ Martian spaceships and suppose that we have $m=k \cdot n$ missiles to release against the $n$ spaceships. The probability to hit and destroy each spaceship by ...
4
votes
1answer
8k views

Solving the Kolmogorov forward equation for transition probabilities

Let $\lambda \mu > 0$ and let $X$ be a Markov chain on $\{1,2\}$ with generators $$ Q = \begin{pmatrix} -\mu & \mu \\ \lambda & -\lambda \end{pmatrix}$$ Write down the forward equations ...
2
votes
1answer
311 views

Measuring dependency of subsequent points from Markov chain

The question is about stimulating different type of species (coded 1-10) based on given species frequencies, and other parameters (eg. mean of normally distributed mass and ratio) using gibbs sampling....
11
votes
3answers
14k views

Estimating Markov chain probabilities

What would be the common way of estimating MC transition matrix given the timeseries? Is there R function for doing that?
28
votes
2answers
40k views

Calculate Transition Matrix (Markov) in R

Is there a way in R (a built-in function) to calculate the transition matrix for a Markov Chain from a set of observations? For example, taking a data set like the following and calculate the first ...
55
votes
11answers
12k views

Resources for learning Markov chain and hidden Markov models

I am looking for resources (tutorials, textbooks, webcast, etc) to learn about Markov Chain and HMMs. My background is as a biologist, and I'm currently involved in a bioinformatics-related project. ...
22
votes
2answers
13k views

Markov Process about only depending on previous state

I would just like someone to confirm my understanding or if I'm missing something. The definition of a markov process says the next step depends on the current state only and no past states. So, let'...
10
votes
2answers
6k views

Does a MCMC fulfilling detailed balance yields a stationary distribution?

I guess I understand the equation of the detailed balance condition, which states that for transition probability $q$ and stationary distribution $\pi$, a Markov Chain satisfies detailed balance if $$...
13
votes
2answers
1k views

What is the connection between Markov chain and Markov chain monte carlo

I am trying to understand Markov chains using SAS. I understand that a Markov process is one where the future state depends only on the current state and not on the past state and there is a ...
9
votes
1answer
13k views

Hidden Markov model for event prediction

Question: Is the set-up below a sensible implementation of a Hidden Markov model? I have a data set of 108,000 observations (taken over the course of 100 days) and ...
14
votes
2answers
26k views

Intuitive explanation for periodicity in Markov chains

Can someone explain me in a intuitive way what the periodicity of a Markov chain is? It is defined as follows: For all states $i$ in $S$ $d_i$=gcd$\{n \in \mathbb{N} | p_{ii}^{(n)} > 0\} =1$ ...
2
votes
2answers
6k views

Problem in discrete valued time series forecasting

I have a temporally ordered discrete valued data. The only possible states for the data are: {1,2,3,4,5,6}. So the series is something like {1,2,3,5,6,4,3,5,2,......} I want to forecast the next value ...
7
votes
2answers
7k views

Converting 2nd order Markov chain to the 1st order equivalent

Given a 2nd order Markov chain where each state takes values in the set $\mathcal{X}=\{A,C,G,T\}$, such that all transition probabilities $p(x_t|x_{t-1},x_{t-2})$ are larger than zero, How to convert ...
5
votes
1answer
284 views

Are the mean of samples taken from Metropolis-Hastings MCMC normally distributed?

I've come across the following theorem while studying MCMC. It seems to suggest that the sample mean taken from the MCMC – the posterior marginal expectation – should be normally distributed, using ...
4
votes
1answer
1k views

Explanation regarding Gibbs Sampling

I am new to MCMC and reading a intro paper regarding Gibbs sampling. However, there are two parts in the paper I cannot understand and get stuck. The first part is equation 2.3 in page 168. It says ...
24
votes
1answer
1k views

Random matrices with constraints on row and column length

I need to generate random non-square matrices with $R$ rows and $C$ columns, elements randomly distributed with mean = 0, and constrained such that the length (L2 norm) of each row is $1$ and the ...
11
votes
6answers
3k views

How should one approch Project Euler problem 213 (“Flea Circus”)?

I would like to solve Project Euler 213 but don't know where to start because I'm a layperson in the field of Statistics, notice that an accurate answer is required so the Monte Carlo method won't ...
5
votes
1answer
1k views

Markov chain convergence, total variation and KL divergence

I have a few related questions regarding the convergence of continuous-state Markov chains. The theorems that I found claim that Markov chains converge in total variation if they are $\phi$-...
4
votes
1answer
878 views

Which Algorithms can model a sequence and predict the next value of this sequence

I have a repeating sequence like the following, with occasionally random values (maybe noise): ABCDABCEDABCDABCD What could be an algorithm to model the sequence and predict a following value at a ...
3
votes
1answer
409 views

What is the difference between Markov chain approximation and variational approximation?

I know they are two different approximation approaches to explicit models(which require approximation, that is transforming a non-optimization problem to an optimization problem to avoid the ...
2
votes
1answer
2k views

WinBUGS: Multiple definitions of a node

So this question is about the BUGS modeling language. So you either know it or have no clue. I'm a newbie to this so it's been driving me mad. I want to define a simple two-state hidden Markov model (...
2
votes
1answer
204 views

Markov chain getting stuck due to insufficient data samples

There is a lot of theory on Markov models and output generation out there, but I cannot locate any information on models getting stuck. I'm trying to create a model of a data set using a Markov model....
0
votes
1answer
754 views

Deriving Transition Matrix of the Embedded Markov Chain given the generator matrix?

Full Problem: A continuous-time Markov chain has generator matrix $$Q= \begin{pmatrix} -1 & 1 & 0 \\ 1 & -2 & 1 \\ 2 & 2 & -4 \\ \end{pmatrix} $$ (i) ...
19
votes
1answer
26k views

Real-life examples of Markov Decision Processes

I've been watching a lot of tutorial videos and they are look the same. This one for example: https://www.youtube.com/watch?v=ip4iSMRW5X4 They explain states, actions and probabilities which are fine....
50
votes
3answers
2k views

Do we have a problem of “pity upvotes”?

I know, this may sound like it is off-topic, but hear me out. At Stack Overflow and here we get votes on posts, this is all stored in a tabular form. E.g.: post id voter id vote type ...
13
votes
2answers
1k views

Numeric solvers for stochastic differential equations in R: are there any?

I'm looking for a general, clean and fast (i.e. using C++ routines) R package for simulating paths from a non-homogeneous nonlinear diffusion like (1) using the Euler-Maruyama scheme, the Milstein ...
10
votes
3answers
6k views

Expected number of coin tosses to get N consecutive, given M consecutive

Interviewstreet had their second CodeSprint in January that included the question below. The programmatic answer is posted but doesn't include a statistical explanation. (You can see the original ...
17
votes
6answers
3k views

Check memoryless property of a Markov chain

I suspect that a series of observed sequences are a Markov chain... $$X=\left(\begin{array}{c c c c c c c} A& C& D&D & B & A &C\\ B& A& A&C & A&D &A\\ ...
10
votes
3answers
2k views

Mathematically modeling neural networks as graphical models

I am struggling to make the mathematical connection between a neural network and a graphical model. In graphical models the idea is simple: the probability distribution factorizes according to the ...
5
votes
3answers
3k views

Identify different periods of variance in a time series

I have a time series $x_t$ which may go through different phases of volatility. One example might be some stock that has high variance from 9 AM to 11 AM, low variance from 11 AM to 2 PM, and then ...
15
votes
2answers
1k views

Sampling from an Improper Distribution (using MCMC and otherwise)

My basic question is: how would you sample from an improper distribution? Does it even make sense to sample from an improper distribution? Xi'an's comment here kind of addresses the question, but I ...
10
votes
1answer
3k views

Test for markov-property in a time-series

Given an (observed) time-series $X_t$ with $X_t\in\{1,...,n\}$, is there a statistical test for testing the null-hypothesis that $P(X_t|X_{t-1},X_{t-2},...,X_1)=P(X_t|X_{t-1})$ (i.e. the markov-...
4
votes
1answer
1k views

Energy function of RBM

The Hammersley-Clifford Theorem tells us that the distribution of a RBM must be Gibbs since it is Markov Random Field, but how to prove that its energy function must be of the form: $$E = -\sum_{i,j}...
9
votes
2answers
2k views

Is Markov chain based sampling the “best” for Monte Carlo sampling? Are there alternative schemes available?

Markov Chain Monte Carlo is a method based on Markov chains that allows us to obtain samples (in a Monte Carlo setting) from non-standard distributions from which we cannot draw samples directly. My ...
4
votes
0answers
440 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 \...
3
votes
2answers
3k views

Fit and evaluate a second order transition matrix (Markov Process) in R?

I already built 1 first order discrete state Markov Chain model. It was built with R using the function 'markovchainFit()' in ...
9
votes
1answer
6k views

Calculating log-likelihood for given MLE (Markov Chains)

I am currently working with Markov chains and calculated the Maximum Likelihood Estimate using transition probabilities as suggested by several sources (i.e., number of transitions from a to b divided ...
5
votes
1answer
2k views

How to estimate the infinitesimal generator of a Markov chain?

I am working on an 8 state (8th state absorbing) multi-state markov model, and what I am having difficulty understanding is, how sensitive are the results to the initial qmatrix and what is the best ...
2
votes
1answer
53 views

Checking whether a given formula is correct for a homogeneous Markov chain

I am new to cross validated so I hope my question belongs here. I saw in a paper where I study someone claiming the following: Given a $ \{ X_n \}_{n=0}^{\infty} $ be a homogeneous Markov chain (...
8
votes
3answers
3k views

Number of Markov chain Monte Carlo Samples

There is a lot of literature out there about Markov chain Monte Carlo (MCMC) convergence diagnostics, including the most popular Gelman-Rubin diagnostic. However, all of these assess the convergence ...
7
votes
0answers
302 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
3answers
689 views

Probability of n-bit sequence appearing at least twice in m-bit sequence

Lets assume that we have a pattern $\alpha$ of bits of length $n$. Then I wish to know what the probability is of $\alpha$ appearing on a string of bits of length $m$ at least twice (where $m > n$),...
4
votes
2answers
348 views

Use Markov chains to compute probability of rolling a 1 followed by a 2 before rolling two consecutive sixes

I was curious about how to apply the concept of Markov chains to the following problem: Rolling a die, what is the probability that 1 followed by 2 will happen before two sixes in a row? I have ...
11
votes
1answer
406 views

Confidence intervals for difference in time series

I have a stochastic model used to simulate time series of some process. I am interested in the effect of changing one parameter to a specific value and want to show the difference between the time ...
9
votes
1answer
1k views

Given two absorbing Markov chains, what is the probability that one will terminate before the other?

I have two different Markov chains, each with one absorbing state and a known starting position. I want to determine the probability that chain 1 will reach an absorbing state in fewer steps than ...
8
votes
3answers
2k views

Random walk: kings on a chessboard

I have a question about the random walk of two kings in a 3×3 chessboard. Each king is moving randomly with equal probability on this chessboard - vertically, horizontally and diagonally. Τhe ...
7
votes
1answer
983 views

Using $\chi^2$ to compare two Markov transition matrices

I have a set of observed Markov sequences for which I have calculated first and second order transition matrices: $$M={P}(X_i=x_i|X_{i-1}=x_j)$$ and $$M^2=P(X_i=x_i|X_{i-1}=x_j,\,X_{i-2}=x_i )$$. I ...
7
votes
1answer
415 views

Expected number of times you spent in a state of an absorbing markov chain, given the eventual absorbing state

It's well known that, if $Q$ is the matrix of transient state transition probabilities, and $$ N = \sum_{n=0}^{\infty} Q^n = (I - Q)^{-1}$$ then $N_{ij}$ describes the expected number of times the ...
5
votes
0answers
89 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^...
4
votes
2answers
4k views

Calculating probabilities of an nth step transition matrix for discrete time markov chains

"Let $\{X_n, n \geq 0\}$ be a DTMC with state space $S = \{1, 2, 3, 4, 5\}$ and the following transition probability matrix: $$ P = \begin{pmatrix} 0.1 & 0.0 & 0.2 & 0.3 & 0.4 \\ 0.0 &...