The tag has no usage guidance.

learn more… | top users | synonyms

1
vote
0answers
32 views

Eigenvectors of a perturbed reducible stochastic matrix

Let $Q$ be a $n\times n$ reducible stochastic matrix. Let $J$ be such that $[J]_{ij}={1 \over n}$. Now for a small positive constant $\alpha\in [0,1]$, consider the matrix ...
0
votes
0answers
50 views

Circular process ergodic?

Let us define a continuous-time Markov process on a circle consisting of $m-$ equally spaced points, i.e. every point has two neighbours. Now, we define a space of functions $S:= ...
-1
votes
1answer
78 views

Mixing time of lazy random walk on the directed cycle $C_n$

Briefly: A hint (if this is easy), reference or derivation would be of great help. The question Let $C_n$ be the directed cycle with loops in each of its $n$ vertices, and consider the random walk ...
1
vote
0answers
14 views

Bounding Hidden Markov model Bayesian filter error with inexact models

In context of a hidden Markov model, I am interested in bounding the error of a Bayesian filter when using inexact state transition and observation models. Consider a hidden Markov model (HMM) with ...
0
votes
0answers
43 views

Regularity of the entrance measure of SRW

Let $S(n)$ be the discrete sphere of radius $n$ (i.e., the internal boundary of the Euclidean discrete ball $B(n)$) centered in the origin, and consider a simple random walk starting at some ...
0
votes
0answers
48 views

Order statistic of Markov chain sample path and related probabilities

Consider a 1D sample path, denoted as $\{X(1), ..., X(t), ..., X(n)\}$, generated from a discrete time finite state (time homogeneous) Markov chain over states $\{1,...,m\}$, with transition ...
1
vote
0answers
22 views

steady state of a continuous-time birth-death process

we consider a continuous-time birth-death process $\{X(t),t\geq 0\}$ with discrete state space taking non0negative integer values $\{0,1,2,3,...\}$. The transition rates of the process $\{X(t)\}$ are ...
3
votes
1answer
55 views

Similarity transformation of transition matrix of reversible Markov chain (reference request)

If $P$ is the transition matrix of a reversible Markov chain, and $\pi$ is its stationary distribution, and let $R$ be defined by: $$R_{ij} = \sqrt{\frac{\pi_i}{\pi_j}}P_{ij}~.$$ By reversibility, ...
2
votes
0answers
34 views

Spectral gap of two step Markov chain

Suppose $X_1,X_2,\ldots$ is a reversible Markov chain with state space of size $k$ and absolute spectral gap $\gamma_*.$ What is the spectral gap of the (non-reversible) Markov chain $Y_1,Y_2,\ldots,$ ...
0
votes
0answers
26 views

steady state distribution for a jump Markov chain

Consider a queueing process with the following transition matrix: $\mathbf{P}=\left( \begin{smallmatrix} 1-\lambda & \lambda & & & & & & &\\ \mu & ...
0
votes
1answer
79 views

Finite hitting time implies hits at any finite time?

I was wondering about the following problem: Assume we have a state space $S:=\mathbb{Z}$ and a Markov chain, such that we can go from any state $x$ to some state $y$ with positive probabilities, ...
0
votes
0answers
24 views

steady state distribution of the following infinite-state Markov chain

Given the following state transition equation: $P_0(n+1)=P_0(n)(1-\lambda \Delta t)+ P_1(n)\mu \Delta t$ $P_j(n+1)=P_{j}(n)(1-\lambda \Delta t-\mu \Delta t)+\lambda \Delta t P_{j-1}(n)+ \mu \Delta ...
0
votes
1answer
102 views

Markov chain with Feller property

Does anybody know whether there is an analysis of when the monotone decreasing chain has the Feller-property? The monotone decreasing is defined as a chain on $\mathbb{N}$ and the rate of going down ...
0
votes
0answers
33 views

Calculate the KL divergence between two transition matrices

I want to calculate how different two markov transition matrices are. For example: $\begin{pmatrix} .2 & .8 \\ .1 & .9 \end{pmatrix}$ and $\begin{pmatrix} .3 & .7 \\ .1 & .9 ...
3
votes
0answers
38 views

Memorylessness of residence times for a Markov process

I'm stuck on the trivial problem of showing memorylessness of holding (residence) times for a continuous time homogeneous Markov chain on finite state space. I have a homogeneous Markov process ...
8
votes
1answer
141 views

Equalizing Geometric means of Graph Cycles

Consider a strongly connected directed graph $G$. I have been stuck on the following question: can you assign real numbers in $[0,1]$ to each edge of $G$ so that the geometric mean of all cycles are ...
0
votes
0answers
35 views

positive Harris recurrent, aperiodic, stationary Markov chain

How to proof that every positive Harris recurrent, aperiodic, stationary Markov chain is alpha-mixing (strong-mixing)?
1
vote
1answer
118 views

Two types of random walkers on square lattice

Consider a two dimensional square lattice ($n$ by $n$), which is our space $S$ (each point labelled by an index $1\to n^2$), containing two types of particles, distinguished here by either an index ...
3
votes
1answer
100 views

Markov-semigroup sobolev inequality

I have a question about the following definition: A probability measure $\mu$, such that the Markov semi-group $e^{Lt} \in L(L^2)$ exists and is symmetric, satisfies the Sobolev inequality iff for ...
0
votes
0answers
30 views

maximum for a nonstationary Markov Chain

Let $\{X_j\}$ be a nonstationary Markov Chain with transition matrix $P$. What is a relation between $P(M_{1:n} \leq x)\quad \text{and}\quad P(M_{1:T} \leq x), \quad P(M_{T:n} \leq x)$ where $M_{k:n} ...
3
votes
1answer
73 views

How much larger than the relaxation time can the mixing time be?

The notation is mostly taken from the book "Markov chains and mixing times" by Levin, Peres, and Wilmer. Consider an irreducible, aperiodic, time-reversible, discrete-time Markov chain on a finite ...
1
vote
1answer
63 views

General Markov Chains on same Probability Space?

A Markov chain $(X_i)_{i\in \mathbb{N}}$ on a measurable space $(E,\Sigma)$ is (see e.g. Revuz or Meyn/Tweedie) constructed on the following probabilty space. $$ \Omega = \{ (x_l)_{l \in \mathbb{N}} ...
0
votes
0answers
37 views

Validating a probability density distribution forecast model for a Markov process

Let's say we have a Markov process $X_t$, and we come up with a forecast model that takes some information from outside world and says: "value $X_{t+1}$ has probability density distribution $P_t(x)$". ...
0
votes
0answers
59 views

Markov chain matching local time

Let $\left(X_{t}\right)_{t\geq0}$ be a Markov process taking values in a finite state space $E$. Its local time at $y\in E$ started at $x\in E$ is defined as $$ ...
3
votes
0answers
99 views

The spring Markov chain on $\mathbb{N}$

I'm trying to understand and learn more about "almost surely bounded" Markov chains on countable state spaces. I'm looking for references where I can learn how to work with more complicated examples ...
0
votes
0answers
38 views

The effect of a single Markov transition on fidelity

Let $p$ and $q$ be two probability vectors of length $n$. The fidelity (or Bhattacharyya coefficient) of $p$ and $q$, is $$ F(p,q) \ := \ \sum_{i=1}^n \sqrt{p_i \cdot q_i}. $$ Let $A$ be a ...
0
votes
0answers
43 views

Ergodicity property for continuous-time Harris positive Markov process

I have posted this question on there, but got no answer. The following theorem is Theorem 13.3.3 of Meyn and Tweedie's Markov Chains and Stochastic Stability on page 328: Theorem 13.3.3. If ...
2
votes
0answers
66 views

Customers and Anti-Customer Queueing Problem: What is the Customer delete probability

Hello may I ask for your help? First the setting: I have got a problem with some queueing theory. The whole problem would be a grid of nodes, all nodes have an operation intensity $\mu_{i,j}$. ...
2
votes
1answer
156 views

Stationary distribution for time-inhomogeneous Markov process

I have a two state, discrete time, time-inhomogeneous Markov process with transition matrix defined by $$T_i=\begin{pmatrix} 1-p_i\alpha & p_i\alpha \\ p_i\beta& 1-p_i\beta \end{pmatrix}$$ ...
1
vote
1answer
125 views

Row-stochasticity of the Jacobian matrix of a stationary distribution

Let $P_{\mathbf{p}}$ be a $n \times n$ row-stochastic matrix whose entries are a function of a probability vector $\mathbf{p} \in \mathbf{R}_{> 0}^n$, $\sum_i p_i = 1$ and define the following ...
0
votes
0answers
71 views

Markov chains on a polyhedron

A modification of a question from Gerard Letac (1976): A m-sided q-adjacent-faced polyhedron has one of its faces "up." Each round, the polyhedron rolls so that any of the adjacent faces is now up. ...
1
vote
0answers
43 views

Oscillating Markovprocess Transition Probabilities

Suppose we have an irreducible positive-recurrent Markov process $\{X(t), t\geq0\}$ with generator $G$. Let $P(t)$ be its transition probability matrix and $\pi$ its stationary distribution. Then we ...
1
vote
0answers
56 views

Link Between Birkhoff Ergodic Theorem and Strong LLN for Harris Recurrent Markov chain

Is it possible to derive strong law of large numbers for a Harris recurrent stationary Markov chain form Birkhoff Ergodic Theorem? As I know that there is a link between SLLN for iid sample and ...
0
votes
0answers
49 views

Strong Markov Property of the joint process $(B_t,L_t)_{t\ge 0}$

Let $B=(B_t)_{t\ge 0}$ be a Brownian motion and $L=(L_t)_{t\ge 0}$ be its local time in zero. Given two strictly increasing functions $\phi_1$, $\phi_2: \mathbb R_+\to\mathbb R$ such that ...
2
votes
0answers
51 views

Mappings between adaptive networks and Markov processes

Are there any known mappings between adaptive networks models (i.e. graph model representations of networks where the internal vertex dynamics and connectivity topology can change subject to specific ...
31
votes
6answers
3k views

Deep Learning / Deep neural nets for mathematician

I am interested in finding out the math ideas behind the technologies that are under the umbrella of "Deep Learning" or "Deep neural nets". Most of the papers/books that are often quoted in ...
1
vote
1answer
144 views

Variation of Markov Chain Convergence Theorem

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

How to fit a stochastic matrix to given data.?

Given a data sequence of noisy observations of a 3-state Markov chain $X$ -- $y_1$,$y_2$,...$y_n$, with two transition matrices $A_1$ and $A_2$ corresponding to different regions (**) in the (unit) ...
1
vote
0answers
114 views

Spectral radius of a column stochastic matrix perturbed by a rank-1 matrix

$P\in \mathbb{R}^{n\times n}$ is an irreducible column stochastic matrix. $P$ is also diagonally dominant. $w \in \mathbb{R}^{n} $ is a strictly positive vector satisfying $w^T \mathbf{1} = 1$ where ...
1
vote
0answers
79 views

Theorems on stochastic Lyapunov function

Let $X_n$ be a sequence of random variables such that $$P(X_{n+1} \in A|X_m,x_m,m\leq n)= \int_A p(dw|X_n,x_n)$$ It is called a controlled Markov process. Now, suppose there exist $\epsilon_0$, ...
1
vote
0answers
193 views

Is the stationary distribution of this Markov chain uniform?

First, a little bit of background: Since 2012, Canada has decided to phase out the penny for its coinage system. Product prices may still use arbitrary cents, especially since prices do not typically ...
1
vote
0answers
36 views

Effects of merging states on the limiting distribution of a Markov Chain

Consider a discrete time, homogeneous, finite state Markov chain given by a stochastic $n\times n$ matrix $M$. We also have a cost vector $w$ of size $n$ with non-negative integer costs. The cost of ...
5
votes
1answer
251 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
470 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 ...
3
votes
0answers
123 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
139 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
147 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
170 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 ...
1
vote
0answers
35 views

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

Consider a large, probably sparse graph with Markovian random walkers on it. Define the discovery time as the expected time to first reach a vertex by random walk from a uniform start. Are there ...
0
votes
1answer
169 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 ...