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

1
vote
1answer
30 views

Why do we have these probability functions for this Markov Chain?

The following shows one of the questions we were given in lectures a while back: We have been given the following solutions to this question: I'm rather confused by these. Take, for example, the ...
0
votes
2answers
28 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
14 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 ...
0
votes
2answers
33 views

Transition Matrix and Invariant Probability

Given the transition matrix for a 2 state Markov Chain, how do I find the n-step transition matrix P^n? I also need to take n--> inf and find the invariant probability pi?
1
vote
0answers
24 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
1answer
39 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\...
0
votes
0answers
19 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 \...
1
vote
0answers
30 views

Series with Markov Chains Probabilities

Notation For each $t \in \mathbb{N}$, let $h_t \in H$ be a random variable that follows a Markov chain, and $h^t \equiv \{h_0,h_1,\dots,h_t\} \in H^t$. Let $\Pi(h^{t})$ be the probability that a ...
4
votes
1answer
51 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 "...
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)$ ...
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 ...
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
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 : ...
1
vote
0answers
29 views

Mean value function of a discrete-time Markov-modulated Poisson process

By "discrete-time Markov-modulated Poisson process" I mean a semi-Markov process $\{(X_n,T_n):n=0,1,\ldots\} $ which satisfies $$T_{n+1}-T_n\mid X_n\sim\operatorname{Exp}(\lambda_{X_n}), $$ with $\...
2
votes
0answers
70 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
1answer
78 views

Distribution of a process dependent on a Markov chain's states

Consider a Markov chain $X_t$ with state space $\{0,1\}$, initial distribution $$ \begin{array}{l} \mathbf{P}(X_0=1)=\lambda \\ \mathbf{P}(X_0=0)=1-\lambda \end{array} $$ and transition ...
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 ...
3
votes
0answers
64 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
45 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\{...
2
votes
1answer
30 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 ...
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
39 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 ...
0
votes
2answers
30 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. ...
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?
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
22 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
22 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)...
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
18 views

Markovian Model: scheduling jobs to servers

I have the following problem. I tried to look at queuing theory, but it probably fits better as a scheduling problem. I have a set of $C$ servers: each one can perform 1 job. Processes arrive ...
0
votes
0answers
37 views

Question regarding regular stochastic matrix

We say that a stochastic matrix is regular iff $\exists n\in \mathbb N$ such that $p_{ij}(n)>0$ for all states $i,j$ How many powers of a matrix do we need to compute at most in order to verify ...
1
vote
1answer
41 views

Show that a function of a markov chain is not a markov chain [closed]

How do you show that a function, $Y(n)=g(X(n))$ if some Markov chain $X(n)$ cannot be a Markov chain?
0
votes
0answers
8 views

How to find transition matrix in cascaded FSMs?

I am considering a 4-state system Equivalently, I can use a cascade approach to represent the same system as In cascade approach, If I consider independent condition on input on both subsystems,...
1
vote
0answers
44 views

For a finite state irreducible aperiodic MC, show that $P^{d^2}$ has all coordinates positive.

Suppose $X_n$ is an irreducible aperiodic finite state MC, with $P$ being the transition matrix. Then we know that $P^n$ has all positive entries for some $n\in\mathbb N$. If the state space $S$ of ...
0
votes
0answers
8 views

How to make Markov Chain model from sequence of data in MATLAB?

Markov Chain model considers only 1-step transition probabilities i.e. probability distribution of next state depends only on current state and not on previous state. I have a sequence and from that I ...
3
votes
2answers
54 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?
0
votes
1answer
44 views

Markov Chain that isn't Irreducible

What is an example of a Markov chain that isn't irreducible but has a unique distribution, such that its distribution converges to that unique invariant distribution for any initial distribution.
0
votes
1answer
17 views

Does an embedded discrete-time Markov chain preserve its properties in continuous time?

Given a discrete-time Markov chain without independent increments, is the embedding of it into a continuous time Markov chain (i.e. via the use of exponential waiting times) an example of a continuous ...
1
vote
0answers
25 views

How to test quality of probability estimates?

I have a Markov chain model which produces a probability distribution for absorption in 4 possible absorbing states. I.e. the model estimates the probability distribution for a discrete random ...
1
vote
0answers
58 views

Prediction Interval from Markov Chains

Thank you for taking the time to look at my question. Short, less involved question: How do you find Prediction Intervals with non-Gaussian residuals? Here is the situation: I have made a model that ...
0
votes
1answer
29 views

What does it mean for an object to not be following a definition based on some implication

I want to get a deeper understanding of what being an object that doesn't follow a definition means in terms of predicates and logical operators. Suppose the following definition of the closedness ...
3
votes
1answer
73 views

Example of a Continuous-Time Markov Process which does NOT have Independent Increments

1. Given a discrete-time Markov chain without independent increments, is the embedding of it into a continuous time Markov chain (i.e. via the use of exponential waiting times) an example of a ...
1
vote
1answer
30 views

probability of which alarm clock goes off first

I'm learning about continuous time markov chains, in the text I am reading, they are setting up the discussion by talking about a series of alarm clocks that are set: Suppose $T_1,...,T_n$ are ...
1
vote
1answer
31 views

distance from the origin in a simple random walk on $\mathbb Z^2$

let $S_{n}= \sum_{i=1}^{n}X_i$ be a simple random walk on $\mathbb{Z}$, with $S_0 = 0$. $X_i = 1$ with probability $p$ and $X_i = -1$ with probability $1-p$. It can be shown that $$\mathbb{P}(S_n=i\...
3
votes
1answer
26 views

Show that a matrix satisfying certain conditions is non-singular

I have a square matrix $A$ satisfying the following conditions: The elements on the diagonal are negative; All other elements are non-negative; All row sums are less than or equal to $0$; There is ...
-1
votes
1answer
18 views

Initial point and initial distribution of the Markov chains

I am reading about Markov chains on a general state space and the ergodicity theory. Some of the ergodic theorems are presented when we consider n-step transition probability conditional on initial ...
1
vote
1answer
22 views

Markov chain - Expectation $+1$?

Let the transition matrix of a markov chain with states $\{0,1,2\}$ : \begin{equation} A=\begin{bmatrix} \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\ 0 & \frac{1}{2} & \frac{1}{2} ...