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.
5,776
questions
0
votes
0
answers
30
views
Is it true that $\lim_{n}p_{ij}^{(n)}=0$ for transient $j$?
For a discrete-time Markov chain that is not necessarily irreducible or aperiodic, I am attempting to show that for transient $j$
\begin{equation*}
\lim_{n\to\infty}p_{ij}^{(n)} = 0.
\end{equation*}
...
- 97
1
vote
0
answers
80
views
Show that $\mathbf{P}(\tau<\infty)=1$
Consider a homogeneous and irreducible recurrent Markov chain $\{X_n\}_{n\in\mathbb N}$ defined on a countable state space $S=\mathbb{Z}$.
Let $\tau:=\text{inf}\{n\in\mathbb N\,: X_n\ge1\}$
where $\...
- 11
-1
votes
0
answers
10
views
Prove that the sum of the probabilities of all state paths of same length is equal to 1.
The sum of the probabilities of all possible sequences of length L can be formulated as a Markov chain as followed:
$$
\sum_{\{x\}}P(x) = \sum_{x_1}\sum_{x_2}...\sum_{x_L}P(x_1)\prod_{i=2}^{L}a_{x_{i-...
- 1
2
votes
0
answers
28
views
Convergence of urn model with repeated binomial draws
I'm analyzing a simple urn model, defined for $N>1$ an integer.
The setup is as follows: we have an urn with $\frac{N}{2}$ white balls and $\frac{N}{2}$ black balls.
At each step $k$, we sample $N$ ...
- 239
1
vote
1
answer
94
views
Why is a sequence of random variables not a markov chain?
I have a sequence of random variables: Y1, Y2, Y3, .... where Y1 and Y2 are both i.i.d. Bernoulli(0.5),
and for all j >= 3, the following holds:
if min(Yj-1, Yj-2) = 1, then Yj is Bernoulli(2/3), ...
- 71
1
vote
0
answers
47
views
Does there exist a connection between the Markov Chains and Dynamic Programming?
For context, I currently taking a class on Probability Modeling and I also happen to be teaching Dynamic Programming (Graduate Seminar), in the former class the instructor is starting to teach us ...
- 941
1
vote
0
answers
69
views
Probability and Markov chains in a knight's tour
I've been working on my math IA for a month now, but I cannot happen to stumble across anything important to calculate within my chosen topic. I've tried optimization of algorithms but it went wrong, ...
0
votes
0
answers
13
views
Almost sure convergence to infinity of a series of random variables in a Markov Model
Consider observations $X_1,X_2,\cdots$ from a Markov model (first order) with two states 0 and 1 having transition probabilities from state $i$ to state $j$, $p_{j|i}\neq 0,1/2,1$, for $i,j=0,1$. ...
- 934
0
votes
0
answers
19
views
Calculating $p^n_{11}$ in a Markov Chain with Complex Eigenvalues
I have recently started learning Markov Chains and feel somewhat out of my depth, as im not a mathematics student. I am trying to calculate $p^n_{11}$ for a 3 state chain with the following transition ...
- 1
0
votes
1
answer
45
views
A simple question about conditional probability
Let $(X_n)_{n \ge 0}$ be a homogeneous Markov chain with a countable state space $(E,\mathcal B).$
Why we have that $$\mathbf{P} \left ( X_r=i,X_{r-1} \ne j,...,X_1\ne j\mid X_0={i}\right )\cdot\...
- 11
2
votes
2
answers
61
views
Inequailities on conditional entropy of a markov chain
Let $x_{n}$ a stationary discrete markov chain . I have to prove that:
For $n\geq 1$
$$ H(X_{n} | X_{0}) \geq H(X_{n-1} | X_{0})$$
$$ H(X_{0} | X_{n}) \geq H(X_{0} | X_{n-1})$$
Where $H(X)$ is the ...
- 119
0
votes
0
answers
38
views
Proving that a sequence of random variables is a markov chain
I have a sequence of random variables, $S_1, S_2, ..., S_n$. Here, $(S_1, S_2, ..., S_n)$ represents a random sequence that is chosen uniformly from the set of all sequences $(s_1, s_2, ..., s_n)$, ...
- 71
0
votes
0
answers
46
views
Relationship between Markov chains and i.i.d. random variables
I am studying Markov chains. I understand that a sequence of i.i.d. random variables is a special type of Markov chain. However, I am trying to prove that a finite-valued Markov chain is a sequence ...
- 71
0
votes
0
answers
34
views
probability generating function for hitting times
Let $S = \{1,2,3,4,5,6\}$ and
$$P = \frac{1}{6}\begin{pmatrix}
3 & 3 & 0 & 0 & 0 & 0\\
1 & 2 & 0 & 3 & 0 & 0\\
0 & 1 & 4 & 0 & 1 & 0\\
0 &...
- 113
1
vote
0
answers
23
views
How to find Q-Matrix
Hello I have following example and dont really know how to solve it:
I need to find a Q-matrix for Markov Chain with 4 states , I = {1,2,3,4} with following conditions:
There is no escape from state ...
- 55
-3
votes
0
answers
32
views
Markov Chain Question, don't know how to solve it [closed]
enter image description here
Can anyone help me with this problem? Have no clue where to start.
- 1
3
votes
1
answer
104
views
+350
Proof about Markov kernels and absolute continuity
Assumptions:
$(\mathsf{X}, \mathcal{X})$ is a measurable space.
$M_n$ and $L_{n-1}$ are Markov probability kernels for $n=2, \ldots, P$.
$\mu_n$ be probability measures on $(\mathsf{X}, \mathcal{X})$ ...
1
vote
0
answers
17
views
When a one-dimensional random walk with self-loops is positive-recurrent
I'm asking about a discrete-time Markov chain whose state space is the set of non-negative integers.
The transition probability from state $0$ to state $1$ is $p$ and from state $0$ to state $0$ is $1 ...
- 155
-1
votes
0
answers
31
views
(𝑋, 𝑌, 𝑍) does not form a Markov chain problem
I am not quite sure how to solve this:
Suppose (𝑋, 𝑌, 𝑍) does not form a Markov chain. Is it possible for 𝐼(𝑋;𝑌) ≥ 𝐼(𝑋; 𝑍)? If yes, give an example of 𝑋, 𝑌, 𝑍 where this happens. If no, ...
- 1
0
votes
0
answers
17
views
Lower bound for probability of birth-death process at 0
Consider a birth-death process with birth transition rate of 1 and death transition rate of $r + \gamma$ at every state $r \in \mathbb{N}$. Can we come up with an lower bound efor the steady-state ...
2
votes
3
answers
250
views
Show the conditional probability
Let $\theta, U_1, U_2,\ldots$ be independent and uniform on $(0,1)$. Let $X_i = 1$ if $U_i\le\theta$ ,$X_i=−1$, if $ U_i >\theta$, and let $S_n = X_1 + \cdots+ X_n$. In words, we first pick $\...
- 437
0
votes
1
answer
104
views
Expected number problem of buttons needed to be pressed:
Bob’s calculator has only four buttons: 1, 2, 3 and clear which clears the display. Bob starts with an empty display and randomly clicks buttons until only 123 remains on the display. What is the ...
3
votes
1
answer
122
views
Markov Process with time varying transition probabilities.
I am interested in studying the evolution of a variable $\alpha_t\in [0,1]$ governed by the following stochastic dynamical system:
$$
\begin{cases}
\alpha_0\in [0,1]\\
\alpha_{t+1}=\frac{t+1}{t+2}\...
- 2,451
0
votes
1
answer
36
views
Convergence to the expected stationary value of an ergodic discrete-time Markov chain
Let $(X_n)$ be an irreducible, aperiodic, positive recurrent, time-homogeneous DTMC on the integers. Let $\pi$ denote the limiting/stationary distribution. It is known that the expected deviation from ...
- 363
-1
votes
0
answers
21
views
Don't understand how to get the transition matrix. It's a discrete markov chain problem
Two buses arrive at a bus stop per hour. Each of them may or may not arrive at the time established for their arrival, since each one takes a different route. For any time “n”, each bus can arrive on ...
- 1
0
votes
0
answers
18
views
Expected value of minimum first passage time of several Markov Chains
Consider $m$ finite state discrete time Markov chains $X_t^1,X_t^2,...,X_t^m(t=0,1,...)$. All of these $m$ Markov Chains have $N$ states $1,2,...,N$ and are irreducible. Let $P^l=[p_{ij}^l]$ be the ...
- 103
0
votes
0
answers
21
views
Markov chains with Poisson
We have a garage that can fix 3 cars at a time and the total number of cars is 7 (3 + 4). If a vehicle comes when the garage is full then it does not get serviced. Τhe service time is exponential with ...
- 11
0
votes
0
answers
17
views
Prove this inequality about Markov Chains with Fatou's Lemma
Consider an irreducible aperiodic (so that it's positive recurrent) Markov chain. Let $\lim_{n \to \infty}p_{ii}(n) =: \pi_{i}$, where $p_{ii}(n)$ denotes the $(i,i)$-element of the $n$th power of the ...
- 335
0
votes
0
answers
22
views
What are the eigenvalues of this matrix-valued equation?
In the following, let $P$ be a stochastic matrix, i.e. $\sum_{j} P_{ij} = 1, P_{ij} \geq 0.$ Assume furthermore $P$ is irreducible and aperiodic, which implies there is a unique stationary ...
- 1,394
1
vote
2
answers
35
views
For a branching process $\left\{X_{n}\right\}$ with PGF $\varphi(s)=\frac{1-(b+c)}{1-c}+\frac{b s}{1-cs}$ find $ \lim \text{Pr}\{X_{n}=k|X_{n}>0\} $
Consider a discrete time branching process $\left\{X_{n}\right\}$ with probability generating function
$$
\varphi(s)=\frac{1-(b+c)}{1-c}+\frac{b s}{1-c s}, \quad 0<c<b+c<1
$$
where $(1-b-c) / ...
- 1,949
0
votes
0
answers
16
views
How many times does a random walk starting at vertex v return to v before first visiting vertex to u
Suppose we have a simple random walk on a graph, or possibly more generally a reversible Markov chain, that begins at vertex v and continues until vertex u is first reached. What is the expected ...
- 101
2
votes
1
answer
29
views
Petite Set for Deterministic Markov Process
I am reading the book Markov Chain and Stochastic Stability by Meyn and Tweedie, and I came across the definition of petite sets that was used later in chapter 15 to derive some ergodicity result of ...
- 163
1
vote
1
answer
60
views
How does this Markov chain behave?
I encountered a specific kind of Markov chain with two parameters $\alpha,\beta\in(0,1)$. It works as follows: the variables $X_0,X_1,\dots$ live in the real interval $[0,1]$. When we have $X_n$, the ...
- 590
0
votes
0
answers
36
views
Stopping Time of a Sequence of Digits
Now I have a program which will generate a sequence of digits. Each digit will output a number uniformly randomly in $\{0,1,2,3,4,5,6,7,8,9\}$. However it will never print the same digit twice in a ...
- 1
0
votes
0
answers
36
views
Number of heads streaks across $16$ coin tosses with unfair coin
Here is a question I am trying to solve:
An unfair coin with probability $p$ for head is thrown $16$ times in a row. Find the expectation of the number of streaks of heads.
My thoughts: The result ...
- 405
0
votes
0
answers
43
views
Necessary and sufficient conditions for a transition matrix to have a limit
Let $T$ be an $n \times n$ transition matrix, i.e. the rows sum to 1 and the entries all lie in the interval $[0,1]$. What are necessary and sufficient conditions for which the limit $lim_{n \...
- 1,199
1
vote
0
answers
17
views
Is this Markov Chain class aperiodic?
I am reading through Introduction to stochastic models by Roe Goodman, but I am a little confused by an answer to one of the exercises.
Consider the below Markov chain. In my mind the class {1,3} is ...
- 55
2
votes
1
answer
38
views
Continuous approximation of discrete Markov Chain
I have a tenuous grasp of stochastic processes and am looking for help solving a problem. Apologies for any abuse of notation or naivete. Thanks in advance!
Say we have a random walk on the lattice $\...
- 21
0
votes
0
answers
15
views
Why does this (markov chain related) system have a unique solution
Expectation of hitting time of a markov chain
In the question above we can find a system that allows us to calculate the expected time to hit a state $i$ , from every other state
$$
\psi(j) =
\begin{...
- 1,480
0
votes
0
answers
14
views
Expected State to reach using Expected Moves to collect all coupons.
I'm working on a scenario in the coupon collector's problem where I draw $v_n$ coupons and look at the expected number of different coupons I get. Now if I set $v_n$ to the expected number of draws ...
1
vote
0
answers
46
views
Showing that some vectors are linearly independent
Let $n \in \mathbb{N}, n \geq 2$. For $j, k \in \{1,...,n\}$, $j \neq k$, let $\rho_{jk} \geq 0$ such that $\sum_{k=1, k \neq j}^n \rho_{jk} >0$ for all $j=1,...,n$. We define the vectors $(e^j)_{j=...
- 404
0
votes
1
answer
23
views
Process distribution which is a Markov chain
A Markov chain $(ξ_n,n ∈ \mathbb{Z}_+)$ has an initial state $ξ_0 = 0$ and transient probabilities $P(ξ_{n+1} = k+1| ξ_n = k) = p, P(ξ_{n+1} = k| ξ_n = k) = 1 − p, k,n ∈ \mathbb{N}, p ∈ [0,1]$. I find ...
- 447
1
vote
1
answer
34
views
Check whether a markov chain in naturals is recurrent
I have a markov chain defined in $N = \{1,2,..\}$ has transition
probabillities that satisfy : $$p(n,n+1) = \frac{n}{n+2}\cdot
p(n+1,n), \forall n \in N$$ Also $p(m,n) =0, \quad |m-n|>1$ and
$p(...
- 797
0
votes
0
answers
10
views
Convergence of stochastic approximation with markov chain input and some nontrivial dependence on input?
Assume $u_t$ is some time-homogenous Markov-Chain with unique stationary distribution $\pi$.
Consider iterations of the form
$$x_{t} = f(y_t,u_t)$$
$$y_{t+1} = y_t + \varepsilon_t \nabla_y g(v,w,y)\...
- 1,394
0
votes
0
answers
48
views
Intuition behind Penney's game
Penney's game: Player A selects a sequence of heads and tails (of length 3 or larger), and shows this sequence to player B. Player B then selects another sequence of heads and tails of the same length....
0
votes
0
answers
44
views
Hitting time for integer random walk
Suppose there is a random walk on the integer line, where the value cannot go below $0$,
and the process stops when it hits a barrier at value $k$. The goal is to compute the expected number of steps ...
- 73
6
votes
2
answers
261
views
Markov chains: Hitting time of random walk on Sierpinski triangle
Given a Sierpinski triangle $G_n$ and a random walk on $G_n$ denoted as $(X_i)_{i\in\mathbb{N}}$, I'm attempting to prove that the hitting time $T_n$ to go from one corner to any of the other two ...
- 435
1
vote
0
answers
20
views
Separating the product of dependent samples from a Markov Chain
Suppose
$$x_1, x_2,...,x_N$$
are samples from a Markov Chain $P(x_t|x_{t-1})$ with all the nice properties (unique steady state $\pi$ or any other reasonable conditions you need)
Is there a nice way ...
- 31
0
votes
0
answers
7
views
when transmission matrix $P(t)$ of markov process is differentiable, is stationary distribution differentiable?
"Markov chain {Xn} is inreducible and positive reccurent, the transimission function $P_{ij}(t)$ is differentiable about t for any state i,j.
prove the stationary distribution $\pi$ of {Xn} is ...
0
votes
2
answers
81
views
Deficiency of unit eigenvalues in a stochastic matrix
Statement
Let $A\in\mathbb{R}^{m\times m}$ be a (row) stochastic matrix.
It is known that the eigenvalues of such matrix lies in the complex unit disk.
Now I am only interested in the eigenvalues ...
- 119