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
57
votes
11answers
13k 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. ...
54
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 ...
42
votes
3answers
39k views

What are the differences between hidden Markov models and neural networks?

I'm just getting my feet wet in statistics so I'm sorry if this question does not make sense. I have used Markov models to predict hidden states (unfair casinos, dice rolls, etc.) and neural networks ...
36
votes
2answers
7k views

A fair die is rolled 1,000 times. What is the probability of rolling the same number 5 times in a row?

A fair die is rolled 1,000 times. What is the probability of rolling the same number 5 times in a row? How do you solve this type of question for variable number of throws and number of repeats?
32
votes
2answers
52k 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 ...
31
votes
5answers
33k 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 ...
25
votes
2answers
15k views

Markov Process that depends on present state and past 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'...
25
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 zero mean, and constrained such that the length ($L_2$ norm) of each row is $1$ and the ...
24
votes
2answers
7k views

Can somebody explain to me NUTS in english?

My understanding of the algorithm is the following: No U-Turn Sampler (NUTS) is a Hamiltonian Monte Carlo Method. This means that it is not a Markov Chain method and thus, this algorithm avoids the ...
23
votes
3answers
35k views

What is the difference between “limiting” and “stationary” distributions?

I'm doing a question on Markov chains and the last two parts say this: Does this Markov chain possess a limiting distribution. If your answer is "yes", find the limiting distribution. If your ...
22
votes
4answers
6k views

Can Machine Learning or Deep Learning algorithms be utilised to “improve” the sampling process of a MCMC technique?

Based on the little knowledge that I have on MCMC (Markov chain Monte Carlo) methods, I understand that sampling is a crucial part of the aforementioned technique. The most commonly used sampling ...
22
votes
1answer
38k 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....
21
votes
2answers
37k 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$ ...
21
votes
6answers
11k views

Examples of hidden Markov models problems?

I read quite a bit of hidden Markov models and was able to code a pretty basic version of it myself. But there are two main ways I seem to learn. One is to read and implement it into code (which is ...
17
votes
4answers
4k views

Why is there always at least one policy that is better than or equal to all other policies?

Reinforcement Learning: An Introduction. Second edition, in progress., Richard S. Sutton and Andrew G. Barto (c) 2012, pp. 67-68. Solving a reinforcement learning task means, roughly, finding a ...
17
votes
6answers
4k 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\\ ...
16
votes
3answers
34k views

Estimating Markov transition probabilities from sequence data

I have a full set of sequences (432 observations to be precise) of 4 states $A-D$: eg $$Y=\left(\begin{array}{c c c c c c c} A& C& D&D & B & A &C\\ B& A& A&C &...
16
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 ...
16
votes
2answers
9k views

What is the difference between Markov chains and Markov processes?

What is the difference between Markov chains and Markov processes? I'm reading conflicting information: sometimes the definition is based on whether the state space is discrete or continuous, and ...
15
votes
5answers
36k views

How do you see a Markov chain is irreducible?

I have some trouble understanding the Markov chain property irreducible. Irreducible is said to mean that the stochastic process can "go from any state to any state". But what defines whether it can ...
15
votes
2answers
2k 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 ...
14
votes
4answers
6k views

A practical example for MCMC

I was going through some lectures related to MCMC. However, I don't find a good example of how it is used. Can anyone give me a concrete example. All I can see that is they run a Markov chain and say ...
13
votes
2answers
8k 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
2k 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 ...
12
votes
3answers
17k 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?
12
votes
2answers
2k views

Why does thinning work in Bayesian inference?

In Bayesian inference, one needs to determine the posterior distribution of the parameters from the prior distribution and the likelihood of the data. As this computation might not be possible ...
12
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 ...
11
votes
6answers
4k 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 ...
11
votes
3answers
8k views

Hidden Markov models and expectation maximization algorithm

Can somebody clarify how hidden Markov models are related to expectation maximization? I have gone through many links but couldn't come up with a clear view. Thanks!
11
votes
1answer
4k 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-...
11
votes
1answer
519 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 ...
10
votes
2answers
3k views

Central Limit Theorem for Markov Chains

$\newcommand{\E}{\mathbb{E}}$$\newcommand{\P}{\mathbb{P}}$The Central Limit Theorem (CLT) states that for $X_1,X_2,\dots$ independent and identically distributed (iid) with $\E[X_i]=0$ and $\...
10
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 ...
10
votes
3answers
7k 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 ...
10
votes
1answer
8k 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 ...
10
votes
2answers
5k views

Reinforcement learning in non stationary environment [closed]

Q1: Are there common or accepted methods for dealing with non stationary environment in Reinforcement learning in general? Q2: In my gridworld, I have the reward function changing when a state is ...
10
votes
3answers
4k 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 ...
10
votes
3answers
4k views

Markov models with conditional transition probabilities

First, let me acknowledge up front that I'm not as well versed in statistics and mathematics as I'd like to be. Some might say have just enough knowledge to be dangerous. :D I apologize if I'm not ...
10
votes
3answers
1k views

Build a path probability tree for journeys through a website

I'm currently doing analysis on a website which requires that I create a decision tree diagram showing the likely route that people take whenever they arrive on the website. I am dealing with a ...
10
votes
2answers
794 views

Evaluating clusters of first-order Markov chains

I clustered my dataset of several thousand first-order Markov chains into about 10 clusters. Is there some recommended way how I can evaluate these clusters and find out what the items in the ...
9
votes
2answers
530 views

Differences between Sampler, MonteCarlo, Metropolis-Hasting method, MCMC method and Fisher formalism

1) I make confusions about what we call a "sampler". From what I understand, a sampler allows to generate a distribution of points that follows a known PDF (probability distribution function)...
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 ...
9
votes
1answer
2k views

What books to read for MCMC theory?

Suppose one is interested in stochastic processes for the purpose getting a theoretical understanding of MCMC. They already have a decent understanding of probability theory (let's say at the level ...
9
votes
1answer
14k 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 ...
9
votes
1answer
431 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_{...
8
votes
3answers
646 views

Equilibrium distribution of Markov chain

The transition matrix is $$P =\begin{bmatrix} \frac12 & \frac12 & 0 & 0 \\ \frac12 & \frac12 & 0 & 0 \\ 0 & 0 & \frac13 & \frac23 \\ 0 & 0 & \frac13 & \...
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 ...
8
votes
4answers
205 views

Worm and Apple Expected Value

An apple is located at vertex $A$ of pentagon $ABCDE$, and a worm is located two vertices away, at $C$. Every day the worm crawls with equal probability to one of the two adjacent vertices. Thus ...
8
votes
1answer
355 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 ...
8
votes
4answers
996 views

How to create a markov chain with gamma marginal distribution and AR(1) coefficient of $\rho$

I want to generate a synthetic time series. The time series needs to be a markov chain with a gamma marginal distribution and an AR(1) parameter of $\rho$. Can I do this by simply using a gamma ...

1
2 3 4 5
24