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
58 views

On the Markov chain defined by $X_n=U_nU_{n+1}$, where $(U_n)$ is i.i.d. symmetric Bernoulli

I came across this problem in homework: $U_n$ are i.i.d random variables with $P[Un=1]=P[Un=−1]=0.5$. a) Show that $X_n=U_nU_{n+1}$ is a Markov Chain. b) Show that $X_n=(U_n+U_{n+1})/2$ is not a ...
0
votes
1answer
33 views

About the expected transitions in Markov Chain

The problem is here: The given answer is here: K = $2+ X_1 + X_2$, where $X_1$ and $X_2$ are independent exponential random variables with parameters $2/3$ and $3/5$. $$ E[K] = 2=2+1/p_1 +1/p_2 = ...
0
votes
1answer
17 views

Finding Transition Probabilities using Metropolis Hastings

I want to find the $4$x$4$ Probability Transition Matrix under the temperature parameter T=2 of Metropolis Hastings. I know that, if x and y are neighbors, $p(x,y) =$ $$ f(x) = \left\{ \...
1
vote
2answers
55 views

Given irreducible transition matrix $P$, why does the matrix $(P−I|\mathbb{1})(P−I|\mathbb{1})^T$ have full rank?

Given irreducible transition matrix $P$, why does the matrix $(P−I|\mathbb{1})(P−I|\mathbb{1})^T$ have full rank? I know this is partially due to the fact that since $P$ is irreducible, there exists ...
3
votes
0answers
24 views

How to handle Finite-state-machine with correlated inputs?

My system can be represented by the following state-diagram. where each arch represents Input/Output when a transition is made from one state to the other. The inputs to this FSM are correlated. ...
0
votes
1answer
25 views

Show that if a Markov chain is irreducible and has a state $s_i$ such that $P_{ii}>0$, then it is also aperiodic.

Show that if a Markov chain is irreducible and has a state $s_i$ such that $P_{ii}>0$, then it is also aperiodic. Proof: Let $X=(X_0, X_1, X_2, \dots)$ be an irreducible Markov chain with a state ...
0
votes
0answers
8 views

Ergodicity coefficient of block matrix

I have a stochastic matrix of the following form \begin{equation} X=\begin{bmatrix}A/3&B/3&C/3\\I_n&&\\&I_n&&\\\end{bmatrix}, \end{equation} where $A,B,C$ are all $n$ by $n$...
1
vote
1answer
29 views

Finding the mean given the probability

I'm doing some work on branching processes and would like to know where the process becomes extinct. If $X$ is the number of offspring of an individual, then the process goes extinct when $\mathbb{E}[...
3
votes
0answers
45 views

Hitting probabilities in a random walk on a graph

Consider a random walk $(X_n)$ on the graph below, where we jump from a given vertex to one of its adjacent vertices with equal probability. I want to find: the probability that we hit $A$ before ...
0
votes
2answers
28 views

Show that this MC is ergodic?

Suppose I have a Markov Chain with States, $S = {1,2,3,4}$ and a PTM given by $P =$ $\begin{pmatrix} .25 & .25 & .25 & .25 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0\\ 0 &...
0
votes
1answer
58 views

Markov Chain Transition Matrix Question

Ok, so my question is pretty simple, the question states: A spider web is only big enough to hold 2 flies at a time. Assuming that the flies fly into the web independently: -The probability that no ...
1
vote
1answer
22 views

Strong Markov Property for Markov Chains - Statement Verification

I suspect that my handwritten lecture notes for the Strong Markov Property are wrong. I'd appreciate corrections to them. We first define the following: A random variable $\tau$ is called a ...
0
votes
0answers
9 views

Markov Chain: Aperiodicity => Primitivity

Hellooo, I would like to know how I can show that the transition Matrix $P$ of an aperiodic Markov chain is primitive. Any suggestions?
0
votes
0answers
15 views

Markov chain nulls

hope the question is ok for this forum. I am a developer and not a mathematician but realise your group is likely to know the answer for these questions. The background is that I am writing a program ...
1
vote
1answer
29 views

Limiting Distribution of a Gibbs Distribution

I know that the Gibbs distribution at a particular state, x, is given by $\frac{e^{-\beta E_i}}{\sum_j e^{-\beta E_j}}$ with $\beta = \frac{1}{T}$, but I do not understand what a limiting distribution ...
0
votes
1answer
18 views

Induction proof for a stochastic process.

Let $(X_n)_{n\in\mathbb{N}}$ be a Markovchain. How can I then show following equation for all $ n \in \mathbb{N}$, $ \displaystyle\bigcup_{k=1}^n \lbrace X_k = j \rbrace = \biguplus_{k=1}^n \lbrace ...
0
votes
1answer
30 views

Finding Initial state vector with given values

I am not sure how to use a given values to form a initial state vector. There are 30% of customers from Company A switch to company B every month, and 35% customers from Company B switch to company A ...
0
votes
0answers
22 views

Correlation Matrix Question

Why is this not a possible correlation matrix for any three random variables X, Y, and Z? $\begin{pmatrix} 1 & -1 & -1 \\ -1 & 1 & -1\\ -1 & -1 & 1\end{pmatrix}$
0
votes
0answers
30 views

Partition Theorem and Markov Chains

Suppose a Markov chain has $s$ states, $S = {1, 2, . . . , s}$, with PTM $P =$ ($p_{ij}$). That is, $p_{ij} = P[X_{n+1} = j | X_n = i]$. Use the Partition Theorem to verify that if $X_n ∼ ν$, then $X_{...
2
votes
1answer
19 views

Simple Bayes? Probability of a state at time t in hidden markov model

Suppose we have a HMM with $2$ states -- $A$ and $B$, with $P(A) = 0.4$ and $P(B) = 0.6$. $A$ has a probability of $0.9$ of outputting "hot," and $B$ has a probability of $0.1$ of outputting "hot." ...
0
votes
0answers
14 views

Analysis of incomplete system of diferential equations

I need to find information about the kinetics of a reaction. I tried to solve this problem first generalizing the equations for the different kind of reactions yielding an equation like: $$ \dot{x} =...
3
votes
1answer
40 views

Probability that two random walks on $\mathbb{Z}^2$ meet at the origin

Suppose $X,Y$ are symmetric, independent random walks on the lattice $\mathbb{Z}^2$. I am trying to find the probability: $$\mathbb{P}\big(X_n=Y_n=(0,0)\;\text{for some}\;n\,\big|\,X_0=Y_0=(0,N)\big)$$...
0
votes
0answers
23 views

MCMC and Metropolis-Hastings problem(s)

What does it mean for a particular state to be a "ground" state or a "stable" state? I should make clear that this is final exam review material and not homework. Also, how does one compute a Gibbs ...
0
votes
1answer
66 views

A Question Regarding Markov Chains and Ergodicity

Suppose the Markov chain with Probability Transition Matrix, $P$ = ($p{_x}{_y}$) is ergodic and $p{_m}(x, y) > 0$ for all states $x$ and $y$. If $n ≥ m$, show that $p_n(x, y) > 0$ for all ...
1
vote
1answer
20 views

A formula for an expected value

We have a Markov chain with $X_0 = z$, the return time $\tau_z$ of the first time at which we return to $z$, and some other state $y$. A proof I'm reading states: $$\operatorname{E}(\text{number of ...
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
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
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
29 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
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 "...
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
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
1answer
77 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
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
43 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
25 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 ...