The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
1answer
71 views

Deterministic finite-state automaton driven by a Markov chain

I've stumbled on some problem, and I have the feeling that this is closed to something well-studied in dynamical systems. The problem is the following. Consider a finite-state automaton with state ...
5
votes
1answer
222 views

Can ergodic theory help to prove ergodicity of general Markov chain?

I am a beginner in ergodic theory. I have read some lecture notes(such as this and this) about it in hope that I could find something which helps to prove the ergodicity of some Markov chain taking ...
-2
votes
2answers
70 views

Convergence of series made out of Markov Chain

$\{X_n\}$ be a ergodic Markov Chain taking values in $\Bbb Z$. Can I find some sufficient condition under which the $E[e^{\sum_{i} |X_i|}] < \infty$ (or say with some high probability).
3
votes
0answers
90 views

Worst-Case Solution to (Stochastic) Matrix Inequality

EDIT: Some specific conjectures added. This problem comes with an associated stochastic process, but I phrase everything as linear algebra in case somebody from a non-probability community has seen ...
4
votes
0answers
110 views

minimal polynomial for a graph

I wonder if there is any result relating the degree $d$ of the minimal polynomial of a directed finite graph to any of its topological features - such as its diameter, or any other similar 'natural' ...
1
vote
1answer
84 views

Mixing time of a continuous time Markov chain with arbitrary rate matrix

I would like to calculate the mixing time of a continuous time starting from the rate matrix and not necessarily assuming that the time in between jumps have rate 1 - all I have is the (finite ...
0
votes
1answer
105 views

On the inverse problem of Dobrushin

Dobrushin, in this paper, looked into the following problem. Suppose We are given a Markov kernel (conditional distribution) $P_{Y|X}$. Information theorist usually call $W$ a channel. It is known ...
0
votes
0answers
21 views

Is there effective algorithm for finding “minimal discovery time” for large graphs?

Consider a large, probably sparse graph with Markovian random walkers on it. Define discovery time as time to first reach a vertex by random walk from uniform start. Are there effective ways to find ...
0
votes
1answer
54 views

Does a irreducible set of states necessarily need to be closed in a Markov chain?

I have come across two different definitions for a 'irreducible set of states' of a Markov chain. Definition 1: A subset of states $A$ of a Markov chain is irreducible if it is possible to access ...
0
votes
0answers
126 views

A doubt on Balaji Meyn's ergodic theorem paper

I have a question regarding the classic paper by Balaji and Meyn: "Multiplicative ergodicity and Large Deviations for an Irreducible Markov Chain". Consider a recurrent aperiodic irreducible Markov ...
1
vote
0answers
74 views

Conditional probabilities in epidemic model

I was contemplating an epidemic model where infection and recovery rates are determined by links. Here node $i$ is infected first and recovers at a rate $\mu_i$. For all other nodes, the recovery is ...
2
votes
1answer
128 views

Stationary distribution of Markov chain

Suppose I have a discrete time Markov chain $\boldsymbol{X}$ with state space $\mathbb{R}^+$. The chain is $\psi$-irreducible, aperiodic, atomless and has an invariant measure $\pi$. If $\pi$ is ...
1
vote
0answers
73 views

An optimization problem for a Markov Chain

Consider a Markov Chain $\{X_n\}$ whose transition probability depends on some parameter $\theta$ ($p_{ij}(\theta)$). Now I want to optimize the following quantity $$\lambda(\theta) = ...
1
vote
1answer
159 views

Can ergodic theorem be used here [closed]

Suppose I have an ergodic Markov Chain $\{X_n\}$ where $X_n$ are bounded. Now, Can I say anything on the limit $$ \lim_{n\to\infty} \frac{1}{n}\ln E\left[e^{\sum_{i=0}^{n} X_i}\right]$$ I don't ...
1
vote
1answer
187 views

Double Markovity

Suppose we have a double Markov relation for three random variables $X$, $Y$ and $W$ as follows $$X\to W\to Y,$$ and $$X\to Y\to W.$$ How to prove that there exist functions $f$ and $g$ such that ...
0
votes
1answer
39 views

Constructing a transition matrix of a time-homogeneous, finite Markov chain with full support stationary distribution

is there a way to construct a transition matrix of a time-homogeneous, finite Markov chain such that the stationary distribution always has full support (this is equivalent to all states of the chain ...
0
votes
1answer
43 views

DTMC random walk model [closed]

For a discrete Markov chain random walk with p < 0.5 with state space S= {0,1,2..} What is the stationary distribution? I could use any help. Thank you
5
votes
0answers
129 views

Maximal inequalities for square of partial sums

Let $S_n = \sum_{i \leq n} X_i$ be the partial sums of a nice sequence of random variables $X_i$. In my application, $X_i$ is a functional of a finite-state, irreducible, aperiodic Markov chain, so ...
1
vote
0answers
52 views

Simultaneous multiple perturbations in Markov chain Monte Carlo

I'm coding a McMC algorithm for geophysical applications. Using the Metropolis-Hastings scheme to accept/reject the proposed models is smth that i thought i completely understood, but i don't. To be ...
3
votes
1answer
130 views

Approximating Markov chains by Brownian motion

I would like a result along the following lines to be true, but haven't been able to locate it in the literature; pointers would be welcome. Let $X_t$ be a finite-state, irreducible, aperiodic Markov ...
1
vote
1answer
100 views

N random walkers that hit node v in a graph

Consider a finite, undirected graph G, with uniform edge weights. Assume that there are n number of random walkers that will start at different nodes (lets say n=3, hence the random walkers will start ...
0
votes
0answers
60 views

Nonstationary Markov chain maximal inequality

Let $X_i$ be a (finite-state, irreducible, aperiodic) Markov chain, not necessarily stationary. (That is, it doesn't start from the invariant distribution; I'm happy to have it be time-homogeneous if ...
1
vote
0answers
157 views

random walk with reflecting barriers [closed]

Consider a random walk on the line 1,...,d. You start at point 1. At each step you flip a coin: heads means go left, tails means go right. If you're at 1 and get a heads, just stay where you are (same ...
1
vote
1answer
118 views

Gibbs sampler with linear constraints

My problem concerns the estimation of truncated multivariate normal distributions under constraints. Let $X_1$ and $X_2$ two random variables following normal distributions ...
4
votes
3answers
500 views

How to explain “Feller process” to an undergraduate student?

I had to explain in informal terms what a Feller process was, to undergraduate students who understand Markov property, Poisson processes and such. It was easy to define Levy process as generalisation ...
6
votes
1answer
189 views

First Collision Time for k Random Walkers on a Torus

I consider $k$ random walkers on $\mathbb{Z}^{d}/n \mathbb{Z}^{d}$, the $d$-dimensional torus of side length $n$. More precisely, I will define a Markov chain $Z_{t} = (X_{t}[1], \ldots, X_{t}[k])$ ...
2
votes
0answers
32 views

Markov decision processes: action set revealed at point of decision

I have a problem which looks like a finite horizon Markov decision process (MDP), except the action space at each time is revealed at the decision making point. There is no way to know before hand the ...
6
votes
2answers
534 views

References for a physicist migrating to stochastic processes

I've studied "Markov Chains" - Norris and "Measure, Integral and Probability" - Capinski, Kopp. Now, I'm looking for a couple of books (or other references) that help me bridging these two topics. ...
2
votes
0answers
70 views

Mixing time for dimers on the square-octagon graph

Consider the "fortress graph" of order $n$ (see Figure 9 of http://faculty.uml.edu/jpropp/tiling/www/mdblum/arctic.html). It's been known empirically for twenty years that if one turns the set of ...
3
votes
3answers
621 views

Time-inhomogeneous Markov Chains

I'm trying to find out what is known about time-inhomogeneous ergodic Markov Chains where the transition matrix can vary over time. All textbooks and lecture notes I could find initially introduce ...
0
votes
0answers
20 views

Examples of POMDPs where the actions impact the transitions of the underlying markov Chain

I am not sure if the following is a legitimate question for this board. I am looking for examples of Partially observed Markov decision processes (preferably infinite horizon, Discrete time, Discrete ...
0
votes
1answer
109 views

Monte Carlo estimator with autocorrelated samples

Given an integration problem $I=\int{f(x)dx}$, we can construct an ordinary Monte Carlo estimator as $E[I]=\sum\limits_i\frac{f(x_i)}{p(x_i)}$ where the samples $x_i$ are usually i.i.d. and drawn ...
0
votes
1answer
103 views

Is any invariant, ergodic measure with full support on an irreducible Markov shift a Markov measure?

I have this question I have been struggling with for a while. It seems rather intuitive, however, I was not able to proof it yet: Let $\Omega = \{1,2,\cdots,N\}$ a finite alphabet, $\Sigma \subset ...
1
vote
2answers
125 views

Invariant measure of Euler-Maruyama Discretisation of an Ito diffusion

Let $(X_t)_{t \geq 0}$ be a diffusion process with dynamics governed by the stochastic differential equation \begin{equation} dX_t = b(X_t)dt + \sigma(X_t)dW_t, ~~ X_0 = x_0, \end{equation} where ...
2
votes
1answer
120 views

convergence rate of occupation measure of ergodic Markov Chain

Given an ergodic Markov chain $(X_n)_{n\geq 1}$ in $R^d$with $\pi$ as the invariant distribution of the transition kernel, under good conditions we have that the empirical occupation measure converges ...
1
vote
1answer
133 views

forward algorithm Hidden Markov Model

I am studying the the forward-backward algorithm used in Hidden Markov Models. I understand that that you are trying to propagate through a sequence (and the available states) to find the most ...
3
votes
0answers
90 views

Nonlinear Markov process

Consider the following nonlinear $\mathbb{R}$-valued stochastic recursive sequence: $ X_{n+1} = F(X_n) + W_{n+1}, \quad (W_n)_{n\ge1} \stackrel{ \scriptsize \mathrm{i.i.d.} }{ \sim } \phi. $ How can ...
3
votes
2answers
165 views

Markov Partitions for toral automorphisms

I know that my question is more practical than theoretical. But, I do know where to look for the theoretical sources. I want to find a program in the case that it exists (does it?), or to program it. ...
0
votes
0answers
75 views

An attempt to solve “Maximization of a total variation distance subject to another total variation distance in Markov chain”

I have been trying to solve Maximization of a total variation distance subject to another total variation distance in Markov chain. As a recall, suppose we have a pair of correlated random variables ...
1
vote
0answers
86 views

segmental k-means hmm algorithm

I'm trying to determine the state parameters for an hmm with a minimum of 9 states. I'm running chunks of my data through hmmtrain on MATLAB which I think uses the Baum/Welch aka forward/backward ...
1
vote
0answers
246 views

Closed-form solution to a system of linear equations

Consider the following $n \times n$ matrix with a particularly nice structure: \begin{equation}\mathbf{P}=\begin{pmatrix} 0 & 0& \dots&0 & 0 &1\\ 0 & 0& \dots&0 & ...
0
votes
1answer
231 views

Generating independent random variable from two correlated random variables

Suppose two random variables $X$ and $V$ are given. I am wondering what kind of condition we need to impose on joint distribution of $V$ and $X$ to make sure that there exists a random variable $Z$ ...
14
votes
4answers
714 views

Eigenvectors of a particular transition matrix

I am considering a Markov chain with $n$ states with a particularly nice structure. The transition matrix is as follows: \begin{equation}\mathbf{P}=\begin{pmatrix} 0 & 0& \dots&0 & 0 ...
1
vote
0answers
68 views

CLT for a Markov Renewal Process

Suppose $(X,T)=\{(X_n,T_n)\}_{n\geq0}$ is a Markov renewal process, where $X$ is a finite-state, discrete-time Markov chain with state space $\{1,2,...,R\}$. $T$ is the additive component, more ...
2
votes
1answer
172 views

Quasi-stationary distribution for a death process

In the paper, Survival in a quasi-death process by van Doorn and Pollett, the quasi-stationary distribution of a transient CTMC is discussed and QSD for a simple death process is derived. Consider a ...
2
votes
1answer
155 views

Transition probabilities in coupled Markov chains

I know that for a continuous-time Markov chain, the probability of transition from time $0$ to $t$ is given by $P(t)=e^{Q(t)t}$. I have a system of $N$ interdependent continuous-time Markov chains ...
1
vote
1answer
68 views

Minimal variance for phase-type distributions?

Let $\mathcal{D}(m)$ be the set of phase-type distributions constructed from $m+1$-state Markov chains. Recall that the coefficient of variation of a distribution $D$ is the ratio of the standard ...
3
votes
0answers
185 views

Maximization of a total variation distance subject to another total variation distance in Markov chain

Suppose two dependent random variables $X$ and $V$ from finite alphabets $\mathcal{V}$ and $\mathcal{X}$ with known joint and marginal distributions are given. Let $P_{XV}$ and $P_X$ and $P_V$ are the ...
3
votes
0answers
53 views

Relative vulnerabilities in SIS epidemic model

Consider the SIS model of epidemic spreading. There is a finite graph $G(V,E)$, link infection rates $\lambda_{ij}$ and node recovery rates $\mu_i$. There are a few initial nodes which are infected at ...
4
votes
1answer
151 views

Log-likelihood in regime switching

Not sure if this question is too simple to be asked here... In the following paper Cho, Jin Seo, and Halbert White. "Testing for regime switching." Econometrica 75.6 (2007): 1671-1720. doi: ...