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
0answers
22 views

Given a one step transition matrix, find $E[X_n | X_0 = 0 ], $as $n -> \infty $

Or even more generally, how would you find $E[X_n | X_0 = i ], $ as $ n -> \infty $ Given the one-step transition matrix for a markov chain. I can't find anything helpful online. My first ...
2
votes
1answer
81 views

How can I analyse a Markov chain whose transition matrix has repeated eigenvalues?

Consider the following stochastic matrix: $$M = \left(\begin{array}{ccc} \frac{1}{2} & \frac{1}{6} & \frac{1}{6}\\ \frac{1}{2} & \frac{1}{2} & \frac{1}{6}\\ 0 & \frac{1}{3} ...
1
vote
0answers
47 views

Wald's Identity for non-i.i.d. Case

I am looking for Wald's Identity for non-i.i.d. case as discussed in the following links: https://en.wikipedia.org/wiki/Wald%27s_equation What are the assumptions for applying Wald's equation ...
1
vote
1answer
31 views

What does it mean to “marginalise out” something?

Especially in machine learning one often reads the phrase "to marginalise out" something, and while I understand that this means to integrate over a property, I cannot quite grasp the larger ...
0
votes
0answers
18 views

What does the transition matrice mean in Markovian processes?

A diploma is organised by the College of Hogwarts on two years: $year1$ and $year2$. Each year an exam is organized in order to go to the upper level or be graduatie. Student has the probability ...
0
votes
0answers
8 views

How to find the probability vectors of an invariant Markov chain?

Let an homogeneous Markov chain be $\{X_n\}_{n \inℕ}$ with three states $a,b,c$ \begin{pmatrix} \alpha & 0.5 & 0.3 \\ 0.1 & \beta & 0.8 \\ 0.5 & 0.2 & \delta ...
0
votes
1answer
49 views

Problem in solving the long run behavior of a Markov chain. (Exercise 1.3 Georgy F.Lawler )

Exercise 1.3 Introduction to Stochastic Processes Georgy.F Lawler : Consider a Markov chain with state space {1,2,3} and transition matrix $$ P= \begin{pmatrix} .4 & .2 & .4 \\ .6 ...
1
vote
0answers
34 views

A time reversible Markov chain problem on urns

Question: (Ross Probability Models, Ch. 4, Ex. 70) A total of $m$ white balls and $m$ black balls are distributed into two urns such that each urn contains $m$ balls. At each stage, a ball is selected ...
0
votes
1answer
49 views

Expected value of the number of “Bad” states in three consecutive steps

A group of $3$ consecutive states is inspected. The first state is known to be Bad, find the expected number of these $3$ states that will be Good. We need to find $E(G)$ knowing that: ...
0
votes
1answer
38 views

$X_{2m}$ is a Markov chain

If $X$ is a Markov chain then $X_{2m}$ is a Markov chain, I have the proof but don't understand one step, why is ...
0
votes
0answers
18 views

First Time Passage References

Does someone have any references for this topic regarding distribution for first time passage? Details included in this topic. Hitting times of Markov chain/process have always finite moments? Best ...
0
votes
0answers
20 views

Transience of random walks starting from each of the sites which have been already visited

Consider a simple random walk on $\mathbb{Z}^d$, $d \geq 3$, which starts from the origin. As $d \geq 3$, there is a positive probability that the random walk never visits the origin again. Now, let ...
1
vote
1answer
21 views

Fault in Reasoning on a Relation of Markov Chains and Injective Mappings

Clearly, if $g$ is a deterministic function then for two random variables $X, Y$: $X \rightarrow Y \rightarrow g(Y)$ i.e. they form a Markov Chain. If $g$ is a one-to-one mapping we can further ...
0
votes
0answers
7 views

Is the value of the discrete Green's function on a box independent of the position of the points within the box?

I currently contemplate over the discrete Green's function on a box and am trying to gain an intuition for its behaviour. Consider the box $B := \{-N,\cdots,-1,0,1,\cdots,N\}^2$ and let $(X_i)_{i \in ...
0
votes
3answers
62 views

markov chains and coin flips

A coin that comes up heads with probability p is continually flipped until the pattern T T T H appears. Let X denote the number of flips, find EX. If I use Markov chains is there a simpler way to ...
0
votes
0answers
20 views

Symmetric states of a Markov Chain

Suppose states $i, j$ are symmetric in a Markov Chain, i.e.: $P(T_j<T_i\mid X_0=i)=P(T_i<T_j\mid X_0=j):=\theta$,$\quad$ where $T_i=\min\{n\geq1:X_n=i\}$. Denote $N$ as the number of visits ...
0
votes
0answers
16 views

Why to fix dangling nodes in the transition matrix before computing PageRank?

Dangling node - page - is a page has no out-links from it to other pages, thus the probability of going from a dangling page to any page else is zero. So any transition matrix has dangling nodes ...
0
votes
0answers
31 views

Importance of uniform stationary distribution

When I study Markov chain (or sampling) related papers, most of them emphasize "uniform stationary distribution". But, I can't sure why it is important for Markov chain problems or randomized ...
1
vote
1answer
94 views

What is the relationship between eigenvector and computing PageRank?

I read several papers about PageRank and didn't get stuck in understanding the idea of PageRank because it is simple, but I got stuck in computing PageRank, those papers talk about some mathematical ...
0
votes
0answers
18 views

Problem with condtional probability in Markov chain

Suppose we have a sequence of independent binomial random variables $\xi \in B(1,p)$. We build a new sequence $\eta_n = 2 \xi_{n+1} + \xi_n$. Will it be a Markov chain? My thoughts. Lets consider ...
1
vote
1answer
53 views

Random walk - Markov chain

I have a problem.If we start at place $0$ and the probability to go right is $p$ and the probability to go left $q$. I need to calculate the probability after 100 steps that the maximum place when we ...
0
votes
0answers
80 views

What is the expected amount of time until the chain is in state 4?

Consider the continuous-time markov chain with state space {1,2,3,4} and infinitesimal generator ...
4
votes
0answers
67 views

Distribution of $\max_{n \ge 0} S_n$, random walk.

Say I have a random walk that's a nearest neighbor random walk on the integers where at each step the probability of moving one step to the right is $p$ and the probability of moving one step to the ...
1
vote
0answers
30 views

The differences between the return times to a recurrent state of a discrete Markov chain are independent and identically distributed

Let $(\Omega,\mathcal A)$ be a measurable space and $\mathbb F=(\mathcal F_n)_{n\in\mathbb N_0}$ be a filtration on $(\Omega,\mathcal A)$ $E$ be an at most countable set equipped with the discrete ...
1
vote
1answer
34 views

Markov process, compute how much time spent in each state in average before absorption.

This problem has three states for a person, which are either employed, unemployed or early retirement. The probability that a working person goes unemployed is 0.2 (ie with intensity 0.2 per year). ...
0
votes
0answers
15 views

Energy functions for CRF/MRF

I am currently working in image segmentation. I have read several papers and books where Markov or Conditional Random Fields are used in order to segment images. Most of them also mention an energy ...
1
vote
0answers
56 views

Random walk evaluated by a Poisson process

I found the following proposition and I want to prove it. Let $S_n$ be a discrete-time random walk with increment distribution p and $N_t$ be a Poisson process with parameter $1$.Then the process ...
0
votes
0answers
18 views

Property of an irreducible Markov Chain

How can we prove that if a Markov Chain is irreducible (does not contain any closed set), then every state can be reached from every other state in the chain ?
0
votes
0answers
29 views

Proof that any sequence of random variables is a Markov Chain

Let $\{X_n; n \geq 0\}$ be a sequence of random variables from $(\Omega, F, P)$ to $(S, B)$ where $S$ is the state space. In my lecture notes Markov chains are defined as those sequences for which : ...
0
votes
1answer
26 views

model with markov chain

Suppose to have the following situation: At a bar at each time unit arrives a certain number of customer with probabilities $p_1,p_2,...,p_n$. In the bar there are 3 bartenders so 3 customer can be ...
0
votes
1answer
56 views

I think I've found an invariant distribution for a transient discrete Markov chain - Where is my mistake?

Let $E$ be an at most countable set equipped with the discrete topology $\mathcal E$ $X=(X_n)_{n\in\mathbb N_0}$ be a discrete Markov chain with values in $(E,\mathcal E)$, distributions ...
1
vote
0answers
31 views

An irreducible Markov chain is positive recurrent if and only if there is an invariant distribution

Let $E$ be an at most countable set equipped with the discrete topology $\mathcal E$ $X=(X_n)_{n\in\mathbb N_0}$ be a discrete Markov chain with values in $(E,\mathcal E)$, distributions ...
0
votes
0answers
89 views

Most likely position for random walk with symmetric jumps after $t$ steps

Consider a random walk on $\mathbb{Z}$ starting at 0 with jump distribution $p(x)$ such that, $p(x) = p(-x)$ $p(x)>0$ for all $x \in \mathbb{Z}$ Let $p^{\,t}(n)$ be the probability that the ...
-1
votes
1answer
19 views

If the probability measure $\mu$ is a left-eigenvector to the eigenvalue $1$ of a stochastic matrix $p$, then $\mu p^n=\mu$

Let $E$ be an at most countable set and $\mathcal E$ be the discrete topology on $E$ $p=\left(p(x,y)\right)_{x,y\in E}$ be a stochastic matrix $\mu$ be a probability measure on $(E,\mathcal E)$ ...
1
vote
0answers
24 views

Prove that $W_n := (X_n,Y_n)$ is a Markov chain and determine the transition probabilities.

Let $X_n$ be an irreducible, aperiodic, positive recurrent Markov chain $(\lambda,P)$ on a state space $I$, with stationary distribution $\pi$. Let $Y_n$ be Markov$(\pi,P)$, and independent of ...
0
votes
0answers
29 views

Find the backward equation for the random walk on the integers in the form $f_n(x) = \alpha_n + (x - \beta_n)^2$

Consider the homogeneous Markov process given by the random walk on the integers with probabilities $a$, $b$, and $c$ of moving one step backward, staying in the same place, and one step forward. ...
0
votes
0answers
22 views

Why is the irreducibility is necessary?

Let $\{X_n\}$ be a an irreducible transient Markov chain on $I$, for $i,j\in I$ let $G(i,j)=E_i\left[\sum\limits_{n\ge0}1_{\{X_n=j\}}\right]$ the expected number of visits to $j$ having started ...
1
vote
0answers
32 views

Probability Assessment of Interactive Markov Chain (IMC)

Firstly, consider a Markov chain in your mind. Probability of each state of the Markov chain can be obtained by following Chapman–Kolmogorov equation. $$ P(n\Delta t) = M^{n}P(0) $$ where P is the ...
0
votes
1answer
49 views

markov chains communication classes

In Bremaud's book about markov chains is stated: If A is stochastic but not irreducible, then the algebraic and geometric multiplicities of the eigenvalue 1 are equal to the number of ...
0
votes
0answers
23 views

How do you generally solve a tridiagonal stochastic matrix to find the steady state vector values?

Suppose an urn has $m$ balls in all. At each time, $t$, $X_t$ of them are red and the rest are blue. At each step $t$, you select one of the $m$ balls with equal likelihood. You replace the ...
0
votes
0answers
20 views

Why is the state $i$ persistent iff $f_{ii}=1$

Why is the state $i$ persistent iff $f_{ii}=1$ By definition; $i$ is persistent if $\Pr(X_n=i, \text{for some}\ n\ge1|X_0=i)=1$ and $f_{ii}=\sum\limits_{n=1}^{\infty}f_{ii}(n)$ with ...
0
votes
1answer
29 views

Meaning of $\bigvee$ for collection of sets

In a book* I found the following: $\mathcal{F} = \bigvee_i \mathfrak{B}(X_i)$ where $\mathcal{F}$ denotes a $\sigma $-algebra on a markov chain and $\mathfrak{B}(X_i)$ is the Borel sigma algebra ...
0
votes
1answer
17 views

Many Markov chains with one graph

I am studying Markov chain as a beginner. When I read some documents, I often find a sentence as follows. "For an undirected graph, many finite irreducible Markov chains can be generated." But, it ...
0
votes
0answers
19 views

Modeling a Classification Problem with an Undirected Graphical Model

I have an undirected graphical model problem which I'm looking for some help on. So, the goal is to perform multivariate classification: based on a set of observations, I want to predict the correct ...
2
votes
0answers
43 views

Excursion of random walk conditioning on return

Consider a simple random walk in one dimension starting from the origin. Let $\epsilon>0$. How to prove that, conditioning on the event that the random walk is at the origin at time $n$, the ...
0
votes
0answers
47 views

how to show if {$Z_n$} is a Markov chain given {$X_n$}

I'm currently working on an practice question from my notes. But I'm not quite understanding the idea of how to prove that something is a Markov chain. Let {$X_i$}, $i = 1,2,...$, be a Markov chain ...
2
votes
1answer
62 views

Comparing hitting probabilities vs comparing mean hitting times of a random walk on a graph

I am trying to understand random walks on graphs and whether an intuition that I have can be made rigorous mathematically, and whether it is also true. Let $G$ be a finite, connected undirected graph ...
0
votes
1answer
22 views

Asymptotically unbiasedness of an weighted estimator

Consider a Markov chain on a state space V with size N, and let $\pi(v_j) = \sum_{v_i \in V} \pi (v_i)P(v_i,v_j)$ be the stationary distribution, where $P(v_i,v_j)$ is the transition probability. ...
1
vote
0answers
38 views

Blackwell's example in Markov process theory and Kolmogorov's extension theorem

I'm reading Continuous Time Markov Processes: An Introduction by Thomas M. Liggett. Chapter 2.4 is devoted to Blackwell's example. Let $E=\left\{0,1\right\}$, $\mathcal E:=2^E$ and $X$ be the ...
1
vote
0answers
29 views

Prove that uniform distribution on a set of vertices $V$ is stationary if the graph is regular.

I was going through Random walks on graphs: A survey It was stated that: Uniform distribution on a set of vertices $V$ is stationary if the graph is regular. Can anyone give me some hints to ...