Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [markov-chains]

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.

0
votes
1answer
6 views

Krylov Bogolubov Theorem in Unbounded space

Let $P$ be a Feller transition probability on an unbounded space $X$, if there exists $x\in X$ such that the sequence $\{P^n(x, \cdot)\}_{n\ge 0}$ is tight, then show that there is a probability ...
0
votes
0answers
13 views

understanding time-homogeneous markov chain

Could anyone make me understand the definition here 1 on page 7 definition 2.25, I quite do not understand the notation $P(a)(A)$, what does this mean? Also, is $P(a, A)$ a probability measure from ...
-1
votes
0answers
20 views

How to show that discrete-time Markov chain run backwards in time is again a Markov chain [on hold]

I have a homework question on Markov Chains, can someone please give some help. The full question is: Show that a discrete-time Markov chain run backwards in time (from some time n and state i) is ...
3
votes
1answer
20 views

Find the probability of the following Markov chain

A Markov chain with 3 states: $S = \left \{1,2,3\right\}$ has the following transition matrix: $P = \begin{pmatrix} 0.65 & 0.28 & 0.07\\ 0.15 & 0.67 & 0.18\\ 0.12 & 0.36 & 0....
0
votes
0answers
3 views

Lower bounds on discrete time finite Markov chains hitting probabilities.

I am interested in some general theorems related to lower bounds on discrete time finite Markov chains hitting probabilities (preferably ergodic chains , but not necessarily ), with references . ...
-1
votes
1answer
18 views

Defining New States to Make it A Markov Property [on hold]

Is there a way to make a process that depends on two time points a markov property, I need help on spotting the new states to be defined I just have problems associating probabilities to them. Please ...
1
vote
0answers
23 views

Spectral Theory of Markov Jump Processes (continuous-time)

I stumbled over the eigenvalue problem while analysing an infinite-dimensional jump process. The state space I am working with is $$ \mathbb{N}^{<\infty}=\bigcup_{k=1}^{\infty}\mathbb{N}^k $$ i.e. ...
1
vote
1answer
18 views

simulating a discrete markov process from a reducible transition rate matrix

I'm trying to model an irreversible, discrete Markov process. I have a set of states $S$ arranged in a tree-like structure (it is only possible to move from parent vertex to child vertex). I compute ...
2
votes
0answers
35 views

Is there a deeper reason why the simple symmetric random walk on $\Bbb Z^D$ turns transient when increasing $D$ from 2 to 3?

Polya proved the following very well-known Theorem: A simple random walk on $\Bbb Z^D$ is recurrent if and only if it is symmetric and $D\le2$. Dropping simplicity (i.e. allowing jumps to non-...
1
vote
0answers
19 views

birth-death processes orthogonal polynomials

Let $Z_t$ be a birth-death process with birth rates $\lambda_n$ and death rates $\mu_n$ defined on the non-negative integers. The family of orthogonal polynomials $\{P_n(x)\}_{n\ge0}$ associated with ...
2
votes
0answers
17 views

Hitting and excursion times for biased random walk on the hypercube

I consider the following update rule for a random walk $\{X_{t}\}_{t \geq 0}$ on the hypercube $\{0,1\}^{n}$: At each time step, I sample $I \in \{1,2,\ldots,n\}$ uniformly at random and $U \sim ...
0
votes
0answers
18 views

understanding transitional probabilities and measure

In this example 1.11, 1, could anyone just explain to me the way he has defined the $\mathcal P(x,\cdot)$? I know the definition of $\delta_x$ which indicates the probability centered at point mass. ...
0
votes
1answer
18 views

What does $\delta_n$ refer to in “distribution of $T_k$”, when defining mean recurrence time?

What does $\delta_n$ refer to in "distribution of $T_k$", when defining mean recurrence time? Particularly $$T_k:= \inf \{ n \geq 1: f_n=k\}$$ then my notes say: $$\mathbb{P}(f_n=k, f_{n-1} \not=k,...
0
votes
0answers
23 views

Krylov-Bogolioubov Theorem

Could anyone kindly explain to me how $2\varphi$ comes in the calculation here in page $7$, 1Proof of Thm $1.10$? Thanks for helping. is thm 1.10 is same as 2here in thm 4.17?
0
votes
1answer
31 views
+100

Best way to visualize queueing theory for a Lecture on Markov Chains

Let the Markov Chain $X:=(X_{n})_{n \in \mathbb N_{0}}$ denote, for every $X_{n}$, the number of people waiting in a line at time $n$. Now note that $X$ is a Markov Chain living on $\mathbb Z_{+}$. ...
0
votes
0answers
7 views

Why does it follow from each entry in transition matrix having a limit probability, that the stationary distr. exists?

Why does it follow from each entry in transition matrix having a limit probability, that the stationary distr. exists? I.e. because the proof goes like: Assume $$A=\begin{pmatrix} s_0 & ... &...
-1
votes
0answers
11 views

If a homogenous transition matrix has some entries, which are unknown, then must they be unique?

If a homogenous transition matrix has some entries, which are unknown, then must they be unique? That is if one's given a matrix, where: some elements are known some are unknown and marked e.g. "?" ...
6
votes
0answers
51 views

Is the matrix $\sum_{g \in G} a_g \rho(g)$ normal and what further properties does it have?

Let $\rho$ be the regular representation of $G$. $S \subset G$ a generating set, $|g| := |g|_S=$ word length with respect to $S$. Then I construct such a matrix, where we have some ordering $g_i$ of ...
2
votes
1answer
38 views

How to determine the transition matrix of the markov chain $X_n = f(X_{n-1}, \xi_n), n \geq 0$

I am having trouble to find the transition matrix of the following question: Let $X_0$ be a random variable taking values in a countable set $I \subset \mathbb{R}$. Let $(\xi)_{n \geq 0}$ be a ...
0
votes
0answers
21 views

Taylor on $h$ smooth

I'm struggling to proof that $\int_{\mathbb{R}}P(z,t|x)\sum_{n=1}^{\infty}D^{(n)}(z)h^{(n)}(z)dz$ (with $D^{(n)}(z):=\frac{1}{n!}\lim_{\Delta t\rightarrow 0}\frac{1}{\Delta t}\int_{\mathbb{R}}P(y,\...
2
votes
0answers
20 views

Strong Markov property and another stopping time

I'm trying to prove that given a regular continuous time Markov chain $X_t$ (pure jump process), its embedded chain given by $Y_n=X_{T_n}$ is a homogeneous Markov chain, where $T_n$ is the time of the ...
1
vote
0answers
11 views

Markov Chain holding time

Let $X$ be a continuous-time Markov chain. How does one justify $P(X(s)=x,0\leq s\leq t\mid X(0)=x)=\lim_{n\to\infty}P(X(kt/n)=x,k=0,1,\dots,n\mid X(0)=x)$ without prior knowledge of the ...
0
votes
0answers
27 views

Steady State of a Markov Chain

If i have a regular transition matrix, $P$, and the initial of $P$ being, $x(0)$, how do i calculate the week-by-week succession of system states using matrix multiplication. The system state vector ...
0
votes
0answers
7 views

Expected population size in Markov probability question [closed]

In a branching process, an individual has 0, 1 or 2 descendants with probability 1/4, 1/4, 1/2, respectively. Start the process at generation 0 with a single ancestor. Compute the expected population ...
1
vote
0answers
10 views

Importance Sampling for Monte Carlo Integration. Choosing the proposal distribution

Lets consider this particular problem. We are interested in computing the expected value of a distribution $p(x|z)$ under $p(z)$. A common choice is to use importance sampling and the example ...
0
votes
0answers
30 views

Can be a transition matrix of homogeneous Markov's Chain to be disjoint in t?

Can be a transition matrix of homogeneous Markov's Chain to be discontonuous of $t$, if $P(X_τ = j∣X_{t_n} = i_n, X_{t_n−1} = i_{n−1}, . . . , X_{t_1} = i_1) = P(X_τ = j∣X_{t_n} = i_n)$ $\forall t_1&...
0
votes
1answer
20 views

Show that $\sum^{N-1}_{i=1} \frac{N-1}{i(N-i)}$ is approximately $2\log N$ for large $N$.

I am working on a problem relating to a Markov chain, that results in the sum: $$\sum^{N-1}_{i=1} \frac{N-1}{i(N-i)}$$ For the expected time until reaching the $N^{th}$ state from $0$. The ...
1
vote
1answer
32 views

Chain rule in conditional probability

I'm currently taking a class on computer vision and I have the following problem: I should prove that, if my probability function is given as $p(a,b,c,d)$ and it can be displayed as: $p(a,b,c,d) = ...
0
votes
1answer
42 views

Let $(Y_n)_{n \ge 1}$ be the number of fair coin tosses until 'heads' appears $n$ times. Is $(Y_n)_{n \ge 1}$ a (stationary) Markov chain?

Let $X$ be the random variable counting the number of fair coin tosses until 'heads' appears for the first time. Let $(Y_n)_{n \ge 1}$ be the number of fair coin tosses until 'heads' appears $n$ times....
1
vote
0answers
26 views

Proof that a Markov chain example is time reversible

A total of $m$ male and $m$ female students are distributed into two classrooms, with $m$ students per classroom. At each time, a student is randomly selected from each classroom and the two students ...
-1
votes
0answers
8 views

What is a time period for a transient state?

I am reading Sheldon Ross' Introduction to Probability models. He describes the transient states in chapter 4 section 2. He first defines $f_i$ to be the probability that the system ever reenter ...
-1
votes
1answer
27 views

How can I compute the limit of a probability vector with a transition matrix?

Consider the probability transition matrix $$\begin{pmatrix} 0.5 & 0.5 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0.5 & 0.2 &...
-1
votes
1answer
37 views

Markov chains and their applications [closed]

I'm trying to solve a Markov chain question, I believe this a special kind of those chains, I've solved part a still I'm stuck in part 2. A city is served by two newspapers, the Star and the Times. ...
0
votes
1answer
24 views

How to find the probability that the male line continue forever for the problem given below.

Suppose that every man in a certain society has exactly three children, which independently have probability one-half of being a boy and one-half of being a girl. Suppose also that the number of males ...
0
votes
0answers
17 views

Partial Sums of Markov Chain.

Let $X_n$ be a independent identically distributed sequence of integer valued random variables. Suppose $S_n = \sum_{k=1}^n X_k$ with $S_0=0$, and $Z_n = \sum_{j=1}^n S_j$. Does $(Z_n)$ form a ...
0
votes
2answers
50 views

Probability of failure of a light bulb in years

Let's assume we have a lightbulb with a maximum lifespan 4 years. We are asked to create a transition matrix (Markov chain theory) for the bulb. The bulb is checked once a year and if it's found that ...
0
votes
3answers
24 views

What's the intuition behind a recurrent state $x$ being null recurrent

I am currently trying to come to grips with Markov Chains. I am confused by the nature of having a null recurrent state, which by definition is also recurrent. Say we have a Markov Chain starting at ...
0
votes
0answers
10 views

Finding Markov chain from hitting probability

I am given a Markov chain with state space S={0,1,2,3}. If h_x=(1/2,1,1/4,0) be the hitting probability to any one of the state (say x) of the chain, I need to find x and then the corresponding ...
0
votes
0answers
20 views

Markov transition matrix

A question gotten from a study on Markov process given by my Lecturer. Question ;A salesman's territory consist of three cities A, B and C. He never sells in the same City on successive days. ...
0
votes
0answers
17 views

Expected extinction time for birth and death process

Suppose we have a birth and death process, with the states describing the number of lives in the population. Suppose the rate of going from state i to i+1 is $\lambda$ and the rate of going from i to ...
0
votes
1answer
15 views

Why can one write $\mathbb{P}(f_{j+i}=m|f_i=l) =\mathbb{P}(f_{j+i}=m|f_i=l, f_0=k)$ for Markov Chain?

Why can one write $\mathbb{P}(f_{j+i}=m|f_i=l) =\mathbb{P}(f_{j+i}=m|f_i=l, f_0=k)$ for Markov Chain? Is this application of Markov property?
0
votes
0answers
62 views

Drunkard’s walk Markov chain

Consider the Drunkard’s walk Markov chain with state space $X = ${$0, 1, . . . , N$} and transition matrix: where $0 < α < 1$ is the probability of moving one step from position $k$ to position ...
0
votes
0answers
13 views

Is the stationary distribution the unique solution to this linear system?

We consider an MDP with a transition matrix $P \in \mathbb{R}^{n \times n}$ and assume it's ergodic. Let $\pi$ be the unique stationary distribution of this MDP, so $\pi$ satisfies $\pi^\top P = \pi^\...
0
votes
0answers
9 views

What does $\omega$ do in $\mathbb{P}(\{ \omega : \exists i \geq 1 \space s.t. f_i(\omega)=k\} | \{\omega : f_0(\omega)=k \})=1$?

What does $\omega$ do in $\mathbb{P}(\{ \omega : \exists i \geq 1 \space s.t. f_i(\omega)=k\} | \{\omega : f_0(\omega)=k \})=1$? This is the def. for $k$ being persistent state. What confuses me now ...
0
votes
1answer
13 views

Why is $\mathbb{P}(f_{j+1}=m, f_i=l | f_0=k) \leq \mathbb{P}(f_{j+1}=m | f_0 =k)$?

Why is $\mathbb{P}(f_{j+1}=m, f_i=l | f_0=k) \leq \mathbb{P}(f_{j+1}=m | f_0 =k)$? Where $i,j \geq 0$ and nothing is assumed by the order of probabilities. And where $(f_i)_i$ is a Markov chain that'...
0
votes
1answer
7 views

What does $\lim_{\theta \uparrow 1}$ mean in criticality of Branching process?

What does $\lim_{\theta \uparrow 1}$ mean in criticality of Branching process? Assume that $\lim_{\theta \uparrow 1} F'(\theta)=F'(1) < \infty$. Where $F$ is is prob. generating function: $$F(\...
0
votes
1answer
17 views

When doesn't a Markov Chain have a stationary distribution?

Is it possible for a Markov Chain not to have a stationary distribution? When doesn't a Markov Chain have a stationary distribution?
0
votes
2answers
16 views

test a Markov Matrix for a stationary distribution.

Consider a Markov chain with transition matrix $ P = \begin{bmatrix} 1/2&1/2&0\\ 1/5&4/5&0\\ 0&0&1 \end{bmatrix} $ How many stationary distributions does this chain ...
0
votes
0answers
11 views

Testing the Stationary distribution of a Markov Chain.

Consider a Markov chain $(X_n)_n$ on $S=\{1, 2\}$ with initial distribution $α$ and the transition matrix $P = \begin{bmatrix} 2/3 & 1/3 \\ 2/3 & 1/3 \\ \end{bmatrix}$ If $α = (2/...
1
vote
0answers
24 views

Are the terms Limiting distribution and Stationary distribution properly perceived?

Consider a Markov chain $(X_n)_n$ on $S=\{1, 2\}$ with initial distribution $α$ and the transition matrix $P = \begin{bmatrix} 2/3 & 1/3 \\ 2/3 & 1/3 \\ \end{bmatrix}$ Limiting ...