Stochastic processes (with either discrete or continuous time dependence) on a discrete (finite or countably infinite) state space in which the distribution of the next state depends only on the current state. For Markov processes on continuous state spaces please use (markov-process) instead.

learn more… | top users | synonyms

0
votes
2answers
27 views

What is an example of a second-order markov chain? [closed]

I'd like to see an example of a second-order markov chain. Haven't found one over google or in any of my textbooks
0
votes
0answers
13 views

Gaussian blur over (or random walk in) a surface mesh

Let $V$ be the set of mesh vertices, connected by edges $E$, forming a mesh that represents a surface embedded in $\mathbb{R}^3$. On this mesh a function $f:V\rightarrow\mathbb{R}$ is defined. For ...
2
votes
1answer
24 views

Building a hidden markov model with an absorbing state.

I'm working on trying to implement a hidden markov model to model the affect of a specific protein that can cut an RNA when the ribosome is translating the RNA slowly. Some brief background: The ...
4
votes
1answer
49 views

What is the expected number of steps in a random walk from leaf to leaf in a full binary tree?

Let $h \geq 2$ be a natural number. Consider a complete binary tree of height $h$. Say we take a random walk starting from the "leftmost" leaf. What is the expected number of steps before the "...
0
votes
1answer
38 views

Expectation in reversible Markov chain

Let $X$ be a Markov chain with transition matrix: $$\mathbf{P}=\begin{pmatrix} 0 & \frac{3}{5} & \frac{2}{5} \\ \frac{3}{4} & 0 & \frac{1}{4} \\ \frac{2}{3} & \frac{1}{3} & 0\...
1
vote
0answers
22 views

Perron-Frobenius Theorem: Markov Chain -> Matrices

I am interested in finding out a way how to transform the stochastic results of perron-frobenius for markov chains to any matrix. I am aware that perron-frobenius was originally proofed with linear ...
0
votes
0answers
18 views

How to formally justify matrix manipulation in countable-state Markov chain

I have a Markov chain with transition probabilities $t_{i,i+1} = \binom{k+i}{k}^{-1}$ and $t_{i,0} = 1-t_{i,i+1}$, i.e. we have an absorbing chain with absorption probability approaching one as $i \...
2
votes
0answers
21 views

Markov property for the gambler's ruin problem

Let $(X_n)_{n\ge 0}$ be a simple asymmetric random walk on states $0,1,\dots,M$, where $0$ and $M$ are absorbing. Initial state is $i\neq 0,M$. Let $(X_n^*)_{n\ge 0}$ be the process $(X_n)$ ...
10
votes
2answers
7k views

Is ergodic markov chain both irreducible and aperiodic or just irreducible?

As I find some definition says: Ergodic = irreducible. And then Irreducible + aperiodic + positive gives Regular Markov chain. A Markov chain is called an ergodic chain if it is possible to go ...
0
votes
0answers
25 views

This markov-chain diagram is correct? [duplicate]

Consider two Poisson process arriving with rate $\lambda_1$ and $\lambda_2$ to a single line, and rate of handling $\mu_1$ and $\mu_2$. The time of handling is exponential with rate $\mu_i$. The ...
1
vote
1answer
144 views

Prove that this transformation of a stochastic matrix (or markov chain) is still a stochastic matrix (or markov chain)

Assume to have an $N \times N$ stochastic matrix $W$, where $\sum_j w_{ij} = 1$ and $w_{ij}$ is a generic element on row $i$ column $j$ of the matrix $W$. Moreover you have the following two $N \times ...
0
votes
1answer
59 views

Strong Markov property and time homogeneity

Let $X$ be a Markov chain with state space $\mathcal{S}$ and denote $\mathbb{N} := \{ 0, 1, \cdots\}$. We know that for any stopping time $\tau < \infty$ and any bounded measurable function $\phi : ...
2
votes
0answers
69 views

Relation between the expected number of visits to a state and reachability in a Markov chain

Let's consider a discrete time Markov chain $X_n$. Let $R_{ij} = \sum_{n=0}^\infty \mathbb{1}_{\{X_n= j | X_0 = i\}}$ be the number of visits to $j$ starting from $i$, and let $f_{ij}$ be $\text{Prob}...
0
votes
0answers
8 views

Recurrent states - proof of claim

I want to prove: If $x↔y$, then $x$ is recurrent iff $y$ is recurrent. $i\in S$ is recurrent if $P(T_i<\infty)=1$ How can I properly prove this? I don't know where to start from. Thanks
0
votes
1answer
23 views

Recurrence of a state in a finite state space

Suppose $T_A := \inf\{ n \ge 1 : X_n \in A\}$ where $A \subset \mathcal{S}$ is finite. Assume $\mathbb{P}\{T_A < \infty \; | \; X_0 = x\}= 1$ for $\forall x \in \mathcal{S}-A$. I need to show that ...
0
votes
1answer
29 views

Recurrence of 0 in a random walk

Assume $\mathcal{S} := \{0, 1, \cdots \}$, $p(0,1)=1$ and $p(n,0)=p(n,n+1)=\frac{1}{2}$ for $n=1,2, \cdots$. Is $0$ recurrent or transient? So, basically this is an irreducible, closed but infinite ...
0
votes
0answers
15 views

What is the probability to reach every single number in an infinite random walk over $\mathbb{Z}$?

Suppose we have a Markov chain starting in $X_0 = 0$, with states $S = \mathbb{Z}$ and the transition probabilities $$P(X_{n+1} = i | X_n = j) = \begin{cases}0.9 &\text{if } i = j+1\\ ...
0
votes
1answer
56 views

Finite-state Markov chain

Suppose $X_n$ is a Markov chain with transition probability matrix $p$ where the set of possible states is $S = \{1,2, \ldots, k\}$. If we are given, $X_1$, $X_2, \ldots, X_{2000}$, can we say about ...
1
vote
1answer
52 views

How to Express the Probabilities Associated with a Third Variable in a Hidden Markov Model?

Suppose I have an observation $Y_t$ that is conditionally dependent on $X_t$. (More specifically, Y is a series of observations emitted by an underlying hidden Markov state sequence X.) I can ...
2
votes
0answers
182 views

How to Derive Gibbs Sampling Update Formula for Hidden Markov Model?

I want to understand how to derive the update formula for Gibbs sampling for Hidden Markov Model, for example, in here: $$p(z_t | \mathbf{x}, \mathbf{z}_{\setminus t}, \boldsymbol{\alpha}, > \...
1
vote
4answers
429 views

Figuring out probabilities with Hidden Markov Models

I'm really new to Math so sorry in advance if this question does not make sense. Also I cross posted this on stats.stackexchange.com also. Background: I'm trying to learn about hidden Markov models ...
1
vote
1answer
384 views

HMM as special case of MRF

I have learned that any Hidden Markov Model (HMM) can be described as a special case of a Markov Random Field (MRF) model. However, AFAIK, the dependencies in a HMM are directed, while the ...
3
votes
2answers
52 views

Example of a markov chain that has a distribution that converges to some limit.

Can someone give me an example of a Markov chain that has a distribution that converges to some limit which depends on the initial distribution?
3
votes
0answers
63 views

Strong Markov property proof

Let $X$ be a Markov chain with state space $\mathcal{S}$ and denote $\mathbb{N} := \{0,1, \cdots\}$. I need to show that for any stopping time $\tau < \infty$ and any bounded measurable function $\...
0
votes
2answers
42 views

Expectation of stopping time on a random walk

Assume $X_1 , X_2 , \cdots$ are i.i.d. with distribution Bernouli$(\frac{1}{2})$, i.e., $P(X_i = 0)=P(X_i=1)=\frac{1}{2}$. Denote $S_0 := 0$, $S_n := \sum\limits_{i=1}^n X_i$, and $\tau_{1000} := inf\{...
0
votes
1answer
38 views

Snakes and Ladders and Sample Space

for my Data class project we had to play a board game and do an analysis of it. My group chose rehashed version of Snakes and Ladders. I am almost done the majority of the project, but am stuck on ...
1
vote
1answer
14 views

Invariant distributions: Applications in the real World

I'm studying about invariant distributions for Markov processes; say in the context of dynamics of Random Neural Networks (biological Networks). I can't fully understand what does an invariant ...
0
votes
2answers
29 views

A relation between first passage time and occupation time

Let's think about a discrete time Markov chain $X_t$ with only one recurrent state. Let $T$ be the random variable that is the number of steps taken from a given state $i$ to the recurrent state (ie. ...
0
votes
1answer
22 views

How to properly determine observations related to a Hidden Markov Model alike problem?

I got a an exercise problem which should be seen as a HMM scenario and argument some statements. However I'm quite confused about how to properly solve and argument my solutions. Problem tells: ...
1
vote
1answer
150 views

Forward Algorithm Hidden Markov Model matrix help [Discrete]!

So this may seem like a bioinformatics question but it is the math part that is giving me trouble. I'm using a Python package called YAHMM to model DNA sequences. I created a model with two states (...
1
vote
1answer
83 views

Hidden Markov Models and Viterbi Algorithm: Fair and Biased Die

So following is the problem that I am trying to solve using Viterbi algorithm and HMM: Before attempting to write a program, I want to do this problem by hand for the first 3 observations($651$). ...
1
vote
1answer
43 views

How long does it take two identical hidden Markov models run on same observations to forget their initial distributions (if ever)?

Let $H_1$ and $H_2$ be two instances of a finite Hidden Markov Model (HMM) $H$. That is, $H_1$ and $H_2$ have identical state spaces $Q$ as well as identical transition $A$ and emission probabilities $...
3
votes
2answers
66 views

Is there a proof that the observations of a hidden Markov chain is not itself a Markov chain?

Suppose $\{X_n\}$ is the hidden Markov chain, and $\{Y_n\}$ is the series of observations, where $\mathbb{P}\{Y_n = j| X_n = i\}$ is the same for all $n$ (please correct me if I have not stated the ...
0
votes
0answers
74 views

Transition matrix in left-right hidden semi-Markov model

I'm developing a hidden semi-Markov model left-right . In a left-right model a sequence of $M$ states starts in state $1$ and ends in state $M$, with no repetition of states. Since the model is semi-...
1
vote
2answers
114 views

Has there been significant study of deterministic Hidden Markov Models?

By 'deterministic Hidden Markov Models', I mean HMMs in which all state transition probabilities and output probabilities = 1 or 0. Have models subject to this restriction received any significant ...
2
votes
2answers
51 views

Hidden Markov Model and Viterbi algorithm: Understanding the Casino Problem?

I am deeply struggling with understanding how to apply the Viterbi algorithm. From my course notes, I have the following simple(I'm told) example: If the sequence ...
0
votes
1answer
13 views

emmission probabilities in a hidden markov model with 2 states and an alphabet of 4 characters

I'm reading through a text that is describing how to use use hidden markov models to identify areas of biological sequences that correspond to specific biological features. It starts with a simple ...
1
vote
0answers
56 views

Hidden Markov Model Transition Probability

I am doing my assignment and I am asked to derive transition probability of a HMM. There are Three states. H, E and T. They initially gave me the information as follow. E is followed by an H 40% of ...
0
votes
1answer
91 views

Beginner's questions about Hidden Markov Models

I have started reading about Hidden Markov Models, and have some (more or less) minor questions about things I am not sure I understood correctly. I hope asking here is fine: 1. Assumption about ...
0
votes
0answers
24 views

Binary Hidden Markov Model

Consider a binary HMM with 2 observed variables $O_n \in \{0,1\} \; \forall n \in \mathbb{N}$. Suppose that the hidden Markov process $X_n$ is characterised by a known transition probability matrix ...
0
votes
0answers
28 views

How to Compute Distributions in Hidden Markov Models?

Let $Z_1, Z_2, ..., Z_n$ be the latent variables, and $X_1, X_2, ... X_n$ be the observed ones in a hidden Markov models. Let's assume that the parameters of the hidden Markov models are known: the ...
0
votes
0answers
26 views

Derivation of backward probabilities $\beta_i(s_i)$ of a Hidden Markov Model (message passing). Any help in completing it?

I am trying to formulate in a recursive manner the backwards probabilities $\beta$ of a Hidden Markov Model where $w_i$ are the observed symbols and $s_i$ are the latent states. Is the following ...
1
vote
1answer
24 views

Are queues CTMC?

The $M/M/1$ queue have all the properties of the countable state continuous time markov chain. Is any general queue also a countable state CTMC?
1
vote
2answers
36 views

Expected time between successive visits in a Markov Chain?

This is a pretty basic question and I know the answer is probably really obvious, but I am having trouble reasoning as to why the following is true: (From my lecture notes): """ Expected time ...
0
votes
1answer
41 views

How to understand this kind of Markov chain?

There are two unidirectionally coupled processes $X_t$ and $Y_t$. The coupling is $Y_t=g(X_{t-\delta},\dots)$. The Bayesian network of the two process is described in the following figure: Now this ...
0
votes
0answers
25 views

Finding the stationary distribution of specific homogeneous Markov chain and determining its uniqueness

I am presented with $P =\begin{bmatrix} 0.5 & \alpha & \beta \\ \alpha & \beta & 0.5 \\ \beta & 0.5 & \alpha \end{bmatrix}$ where $\alpha+\beta=0.5$ and $\alpha,\beta \in (0,0....
0
votes
0answers
19 views

Underlying sample space in a markov chain

I am studying discrete-time Markov chain and I am confused about the very first example. The example is the Gambler's Ruin: Consider a gambling game in which on any turn you win $\$1$ with ...
0
votes
0answers
19 views

A problem on random q-colourings of a graph for randomly chosen vertex

Here is an exercise from Olle Haggstrom's "Finite Markov Chains and Algorithmic Applications" from the chapter "Fast Convergence of MCMC Algorithms". The exercise is based on random $q$-colorings of ...
1
vote
0answers
21 views

Reducing sequential correlations in Metropolis Algorithm

In our last lab, we use MCMC method to simulate a walker walking in the phase space. Using the Metropolis method, a walker at its currect position will sample another point inside a cube (centered at ...
1
vote
0answers
20 views

Pure Birth Question. Find the probability that the population at time $t$ is an odd # given it starts at $0$.

Here is the question. Consider a pure birth process $\{X(t) : t ≥ 0\}$ with birth parameters $\lambda_{2n} = α>0$ and $\lambda_{2n+1} =β>0$ for $n∈N$. Compute $Pr\{X(t) \text{ is odd } \mid X(0)...