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

Merging rates on a CTMC model

first time question here. I'm having a rough time trying to represent the following CTMC. Any help would be gladly appreciated. We consider a server with a infinite buffer connected to a network. ...
1
vote
0answers
34 views

Identifying markov chains

Problem: A regular dice is thrown repeatedly. Which one of the following random variables with values in $\mathbb{N}\cup\{\infty\}\cup\{0\}$ is a Markov chain? For those who are, give the ...
1
vote
0answers
30 views

Markov chain converges to boundary

I am learning martingale and related concepts recently and come across the following problem. Suppose $D$ is a bounded, connected, open subset of $\mathbb{R}^2$ with boundary $\partial D$. ...
1
vote
0answers
58 views

How to calculate this integral?

I got confused with this Markov Chain problem: suppose the kernel $Q$ is $Q_x=N(cx,1)$, $c$ is a fixed constant with $|c|<1$ and the stationary distribution is $\pi=N(0,\frac{1}{1-c^2})$. I want ...
1
vote
0answers
50 views

Expected time of reaching 0 of a simple symmetric random walk

Consider the symmetric, simple random walk on $S = \{0, 1, \ldots , k\}$ for $k \in \mathbb N$. Let $$T = \min \{ n \in \mathbb N_0|X_n = 0\}$$ be the first time where the process reaches $0$ and ...
1
vote
0answers
25 views

Random DFS properties

Have there been any work analyzing some properties of random DFS walks? By that I mean a DFS search, which chooses the next node to visit with uniform probability. i.e, it still refrains from visiting ...
1
vote
0answers
45 views

Limiting probability of a successful bid

I'm having trouble completing the above question, as my working knowledge of "limiting probabilities" is not very good. For the 1-step transition matrix, I have $$P= \begin{pmatrix} 0.0 & 0.0 ...
1
vote
0answers
31 views

Learning about Markov Chains

I am trying to learn about how to use markov chains for complicated probability problems. I have been looking for different materials to learn these but haven't had much luck. Does anyone have any ...
1
vote
0answers
18 views

Mixing time analysis of time inhomogeneous markov chaons

There are common methods to characterize mixing times of time homogeneous Markov chains through coupling, conductance and strongly stationary times. However, suppose there is a time-inhomogeneous ...
1
vote
0answers
34 views

Getting stuck in a loop or the probability of hitting all points in a random walk around a circle.

Suppose you are walking around a circular path made up of $n$ tiles. Each tile $i$ is assigned a distinct value $r_i$ by a random variable uniformly distributed on the set of integers $\{1,...,k\}$ ...
1
vote
0answers
27 views

Dwell times of an absorbing markov chain conditional on reaching specific absorbing state

The fundamental matrix of a discrete time markov chain with absorbing states dictates the expected amount of time spent in each state $j$, given that you started in state $i$. The equation is $$S = ...
1
vote
0answers
16 views

Is the steady state of a uniform markov chain always a vector of proportions?

Given that all edges in a markov chain are bi-directional (though not necessarily equally weighted), and each edge for a given node has equal probability, does the steady state always converge to a ...
1
vote
0answers
32 views

Does Markov Chain converge in Variance Norm?

Assume the chain $\{X_n\}_{n\in\mathbb{N}}$ on the statespace $(S,\mathcal{F})$ is aperiodic, irreducible and positive recurrent. We denote with $\pi$ its (unique) stationary distribution. Is it true ...
1
vote
0answers
44 views

The value of a stochastic game

I understand why a stochastic game with discounted payoff has a value $v$ and optimal strategies over the set of stationary strategies. But why is $v$ also the game's value over the set of behavioral ...
1
vote
0answers
26 views

Prove that $E_x[T_y]<\infty$ for irreducible positive recurrent Markov chains.

This is an exercise from Durret's "Probability: Theory and Examples". Suppose $p$ is a irreducible and positive recurrent Markov chain. Then $E_x[T_y]<\infty$ for all $x,y$. I had the following ...
1
vote
0answers
28 views

Converse of Perron Frobenius Theorem: Necessary and Sufficient Conditions for positivity (or non negativity)

As I understand, Perron Frobenius theorem asserts only in one direction, i.e. if Matrix A is positive then there is a perron eigenvalue, eigenvector etc. What I wanted to know is what are the ...
1
vote
0answers
17 views

Estimating Markov transition matrix for regularization

Suppose that I have a sequence of discrete distributions: $$ p_j = (p_{1j},...,p_{Cj}), \: j=1...D,\\ p_{ij}>0 \:\: \forall i,j,\: \sum_{k=1}^Cp_{kj}=1\:\:\forall j. $$ I suppose that these ...
1
vote
0answers
37 views

Survival function of birth-death process

There is a linear birth-death process with $N$ states + an absorbing state $0$, with $$\Pr[X_{t+1}=0|X_{t}=0]=1, \\ \Pr[X_{t+1}=i+1|X_{t}=i]=\Pr[X_{t+1}=i-1|X_{t}=i]=q_i, i\in [1..N-1],$$ and ...
1
vote
0answers
19 views

No null recurrent state in finite state space from definition.

Let $\{X_n\}$ be a markov chain on finite state space $I$, with stationary transition probabilities. Let us denote $f^n(i,i):=P(X_n=i,X_{n-1}\neq i,\ldots X_1\neq i\mid X_0=i)$. We say $i$ is ...
1
vote
0answers
53 views

Markov chain in continuous time (transition probabilities)

Let $(X_t)_{t \geq 0}$ be a markov chain in continuous time with state space $\mathbb{N}_0$. I want to express $\mathbb{P}(X_t = 2| X_0 = 1, X_{3t} = 1)$ and $\mathbb{P}(X_t = 2 | X_0 = 1, X_{3t} = ...
1
vote
0answers
40 views

How to Simplify a Markov chain in order to estimate the average number of transitions to reach to a final state?

Is there any approach to approximate the expected number of transitions to complete a Markov chain without knowing the exact transition probabilities? The reason I ask this is because I want to ...
1
vote
0answers
19 views

Calculate $P(X_{16}=2|X_0=0)$

Given a Markov Chain with three states 0,1,2 with the following State Transition Probabilites: $$M = \left( \begin{array}{ccc} 0.3 & 0.3 & 0.4 \\ 0.2 & 0.7 & 0.1 \\ 0.2 & 0.3 ...
1
vote
0answers
7 views

Why does a Markov chain with one irreductible class has a lower triangular transition matrix?

Given a Markov chain on an infinite and countable set of states, with one irreductible class that has a finite number of states, why can its transition matrix be put in a lower triangular form ? ...
1
vote
0answers
15 views

Marcov Chain confirmation

I am currently having some problems on the following question: Given is the function $f(x)$: $f(x) = 0,1,2$ with probability $\frac{1}{3}$ for each. I have to give the state space, transition ...
1
vote
0answers
40 views

Construction of pure birth process

I am considering a Markov chain $\lbrace X(t) \rbrace_{t≥0}$ in continunous time on the countable state space $S=\lbrace 0 \rbrace\cup \lbrace (i,j) \mid i \in \mathcal{A} , j \in \mathbb{N} \rbrace, ...
1
vote
0answers
68 views

Explosion of a Markov chain

I am considering a Markov chain i continunous time on the countable state space $S=\lbrace 0 \rbrace\cup \lbrace (i,j) \mid i \in \lbrace A,B,C,D,E,F \rbrace , j \in \mathbb{N} \rbrace$. The ...
1
vote
0answers
56 views

How would I find this constant?

I have this equation, and I'm not sure how to solve for the constant $\nu$, since everything else is known: $$\begin{equation} a + \sqrt{a_i + 4 b_i \nu} + \sum^N_{j=1} (\sqrt{a_j + 4 b_j \nu}) ...
1
vote
0answers
70 views

Compute transition probability in n step in infinte markov chain

I want to calculate the probability of transition in n step from state 0 to state 0 ($p_{00}^{(n)}$) in below Markov-Chain : if self loop in state 0 doesn't exist, probability computed with Catalan ...
1
vote
0answers
22 views

Checking the closeness of probability distributions

Suppose I have a Markov chain that satisfies all the conditions of ergodicity and has a stationary distribution pi. I want to find the time when the probability distribution of the markov chain is ...
1
vote
0answers
85 views

Random Walk, Markov Process

I'm stuck on a homework question and am wondering if anyone can offer some hints. Suppose we have some straight line graph G over the set $ V = \{1, 2, 3, ... , n\} $ of vertices, with an edge between ...
1
vote
0answers
39 views

Find condition on $X$ so that $P(\exists n\in\mathbb{N}: N_n=0)=1$

Let $X, X_{n,k}$ for $k,n\in\mathbb{N}$ denote independent random variables with values in $\mathbb{N}_0$. $X$ is identically distributed as all $X_{n,k}$. Define $N_0:=1$ and for ...
1
vote
0answers
52 views

Check if $(N_n)$ is a Markov chain

Let $X, X_{n,k}$ for $k,n\in\mathbb{N}$ denote independent random variables with values in $\mathbb{N}_0$. Define $N_0:=1$ and for $n\in\mathbb{N}$ set $$ N_n:=\begin{cases}0, & \text{ ...
1
vote
0answers
83 views

Kolmogorov backward equations for Birth-Death

I'm trying to solve the Kolmogorov backward equations for a Birth-Death Markov chain with three states. I have 2 equations: $$P_{00}'(t) = \lambda_0 (P_{10}(t)-P_{00}(t))$$ $$P_{10}'(t) = ...
1
vote
0answers
92 views

Chapman-Kolmogorov equations of time inhomogenous Markov chains

Let us assume that we are given a time inhomogenous Markov chain in continuous time (ICTMC) $(X(t))_{t \geq0}$ with a finite state space $\{1,\ldots,n\}$. Set $P(t)_{i,j} := \mathbb{P}(X(t) = j \mid ...
1
vote
0answers
27 views

Closed communicating class and stochastic matrix

Let $(X_n)_{n\in\mathbb{N}_0}$ be a Markov chain with state space $E$ and transition matrix $(p_{ij})_{i,j\in E}$. Let $C\subseteq E$ be a closed communicating class. Show that $$ ...
1
vote
0answers
35 views

Comparing frequencies in stationary distribution

Do there exist theorems for comparing frequencies in the stationary distribution of a (say) aperiodic, positive recurrent Markov chain? i.e. given the transition probability matrix $\mathbf{P}$ with ...
1
vote
0answers
28 views

Is there a single matrix norm such that for all stochastic $P$, $\| P \| = 1$?

By a stochastic matrix I mean a square real non-negative matrix with rows summing to one. Denote the set of all such matrices $\mathcal{S}$. By matrix norm I mean a norm in the vector space of ...
1
vote
0answers
34 views

Markov chains (which book can be recommended?)

This semester I am learning about Markov chains, mainly including basic definitions & properties Recurrence & Transience Perron-Frobenius Theory equilibrium states convergence to ...
1
vote
0answers
37 views

Random Walk and strong law

I want to prove that a Random Walk in 1 dimension is transient when $p\neq\frac{1}{2}$ but i want to prove it by the strong law of large numbers, so i have this: Define a random variable $$X_i = ...
1
vote
0answers
172 views

Can we find a correlation between states of a Markov chain?

I have a fair bit of knowledge on Markov chains but I recently wondered if there is a way to find out a correlation between the states of a finite Markov chain. I could not find any material on this. ...
1
vote
0answers
50 views

Linear Filtering Problem (Keynman Fac/Particle Model)

$lienar Filtering Problem $$X_n^1 = X_{n-1}^1 + \epsilon_n *W_n $$ $$X_n^2 = (1-\alpha* \delta) X_{n-1}^2 + \beta*\delta X_n^1 $$ $$X_n^3 = X_{n-1}^3 + \delta*X_n^2$$ above is $$\approx$$ $$dX_n^1 ...
1
vote
0answers
55 views

Stochastic process using Markov chain (thief on the run!!)

I'm given an exercise where we are to simulate a thief escaping from an officer. The thief (let's call him/her T for simplicity) and an officer (O) have four cities to be in. Let's call the cities A, ...
1
vote
0answers
111 views

Decomposing a stochastic matrix into a product of stochastic matrices.

It is well-known that any square real matrix of small rank $k$ can be decomposed into a product of a skinny matrix with $k$ columns and a fat matrix with $k$ rows by means of an SVD. This question is ...
1
vote
0answers
19 views

Calculate ultimate survival when more than 1 survival curve is needed to determine outcome

I would like to know if it is possible to combine multiple survival curves via an equation (e.g., via matrix multiplication or whatever) rather than stepping through multiple equations. E.g., assume ...
1
vote
0answers
53 views

Cereal boxes - Mean time spent in transient states

Problem: A cereal company gives 2 images in each cereal box it has. There are a total of 5 images. Once a buyer have 5 images she wins a prize. No box contains 2 images that are the same. What is the ...
1
vote
0answers
62 views

Follow-up on solution to Markov process equation

I asked a question here about solving a system related to an absorbing Markov chain. I now have a variation where there are $m$ types (of student, job seeker, etc) each of which applies to ...
1
vote
0answers
30 views

A question about Markov

There is a continuous-time markov chain,and we know the probability transition matrix P.The time between 2 states can be formulated as a exponential distribution whose u is related to the 2 states.Now ...
1
vote
0answers
59 views

Use Hasting-Metropolis to generate a random element from a large complicated combinatorial set L

Let $P$ the set of all permutations $(x_1, \ldots, x_n)$ of numbers $(1, \ldots,10)$ and $L$ the subset of $P$ where $\sum_{j=1}^{n}jx_j> a$. To use Hasting-Metropolis algorithm I followed the ...
1
vote
0answers
34 views

Finding a probability measure

Could someone helpme with this problem? First, consider the transition kernel in $\mathbb{R^2}\times B(\mathbb{R})$ given by $K(x,A)=U_{S^1}(A-x)$. We can than define an other kernel in ...
1
vote
0answers
30 views

Markov chains mixing time

Informally, the mixing time of a Markov chain is the time it takes to reach “nearly uniform” distribution from any arbitrary starting distribution. What does it mean by nearly uniform? I hope some one ...