The tag has no usage guidance.

learn more… | top users | synonyms

1
vote
0answers
118 views

A M/M/$\infty$ queue of depositors with compound interest

Hello, I'm trying to model a bank's liabilities using a queue. Suppose a bank begins with a cash reserve of $M$. Depositors are a M/M/$\infty$ queue; they arrive with rate $\lambda$ and deposit 1 ...
12
votes
1answer
470 views

Random walk origin return monotinicity

Consider a Markov chain on $\mathbb{Z}^d$ with transition kernel $P$ for adjacent vertices (non-diagonal). Essentially this is a $d$ dimensional random walk with the probability of a transition ...
1
vote
2answers
468 views

Rate of decay of variance for a tensor product Markov process (100 pt bounty for good answer by 1800 EST Fri)

Let $Q$ be the generator of a well-behaved (not necessarily reversible) Markov process $X$ on $[n] = \{1,\dots,n\}$ and let $Q^\otimes = \sum_{m=1}^N I^{\otimes(m-1)} \otimes Q \otimes ...
10
votes
4answers
2k views

What is the cover time of a random walk on a cube?

I can't quite figure this problem yet. There is an ant at one vertex of a cube. The ant goes from one vertex to another by choosing one of the neighboring vertices uniformly at random. What is the ...
2
votes
2answers
481 views

Spectral gap of a product of Markov processes

For $m \in [N] \equiv \{1,\dots, N\}$, let $Q^{(m)}$ be the generator of a (well-behaved) continuous-time Markov process on a finite state space $[n_m]$. Write $J \equiv (j_1,\dots,j_N) \in \prod_m ...
2
votes
3answers
544 views

Markov random field with continuous index set

Hi There's Markov random field (MRF) which, by my Wikipedia-based knowledge, is an extension of Markov chain. I'd like to think of it as going from 1D to higher dimensional spaces. Inherent in its ...
1
vote
0answers
193 views

Is the variance of an eigenfunction of a finite state space aperiodic irreducible markov chain starting at a single state always non-decreasing?

I am reposting a previous question due to incorrect initial formulation. Given an ergodic (aperiodic and irreducible) finite state space Markov chain $P$. Let $f$ be an eigenfunction, i.e., $P_t f = ...
2
votes
1answer
263 views

is the variance of a test function of a markov chain always increasing?

Edits: Changed function to eigenfunction. I should have stated the problem with more explicit conditions. Anyways I realized the original formulation is not true, even when one starts at a single ...
1
vote
1answer
448 views

Markov chain: Obtaining transition matrix from recurrence probabilities

Consider a markov chain with finite space { 0,1,..n} with transition probability matrix whose entries are $P_{ij}$. Let $f_{ij}^n$ = probability that starting from state $i $ it goes to state $j$ ...
3
votes
1answer
128 views

mutual hitting measure between two sets

Given disjoint nonempty subsets $X_1, X_2$ of the state space of a finite irreducible Markov chain, there are unique measures $\mu_1$ on $X_1$ and $\mu_2$ on $X_2$ such that (a) starting from a ...
1
vote
2answers
602 views

Borel-Cantelli Lemma on MCs (absorbing states)

hi, I'm sorry if the question is silly, but I couldn't get my head around it for a while now. In Markov Chains (MC) proving that a state is either recurrent or transient is through Borel-Cantelli ...
2
votes
0answers
346 views

How to bound the second largest eigenvalue of a transition matrix of a non-irreducible Markov chain?

I have found several bounds (e.g., Cheeger, Poincare) for the case that the Markov chain is irreducible and reversible, however my Markov chain has one absorbing state. Any bound would be helpful, but ...
0
votes
1answer
617 views

Convergence of sets

Let $E$ be a compact subset of $\mathbb{R}^n$. Let the density function $\phi(x,y)$ be Lipschitz continuous and such that $$ \int\limits_E \phi(x,y)dy=1 $$ for all $x\in E$. Let us consider the ...
3
votes
0answers
321 views

maximum variance unfolding

Consider positive weights $\pi_1, \ldots, \pi_n$ (one can suppose that they add up to $1$) and $n-1$ lengths $d_1, \ldots, d_{n-1}$. Is there an analytical solution to the following problem: find the ...
2
votes
2answers
577 views

Exist closed forms of the distribution of return time in markov chains?

Hi, I am interested in the distribution of return times in simple random walks on finite graphs. Let $G$ be a connected finite graph with, with two independent random walks. If both random walks ...
2
votes
2answers
640 views

Counterexample Markov process

Let $X$ be a homogeneous Markov process in a continuous time with value in the set $E$. Suppose that for some $T>0,x\in E, A\subset E$ we have $$ P_x[X_t\in A] = 0 $$ for all $t\in [0,T]$ but $$ ...
2
votes
1answer
424 views

Reachability for Markov process

Let $X$ be a Markov process (in continuous or discrete time) and define an event $$ R(T,A) = (\exists t\leq T: X_t \in A). $$ I have seen in one paper that $$ \Pr[R(\infty,A)] = \sup\limits_{\tau} ...
3
votes
3answers
1k views

Statistics of a simple Markov chain

Imagine a two-state Markov chain which hops between the states $\pm 1$ with probability $p<1/2$, so that the autocorrelation function after $k$ steps is $\rho_k = (2p-1)^k$ If I take an ...
2
votes
1answer
159 views

scalar diffusions are reversible

It is well known that under mild assumptions a scalar diffusion $dX_t = a(X_t) dt + \sigma(X_t) dW_t$ with invariant probability distribution $\pi$ is reversible. This is indeed not true for ...
8
votes
1answer
547 views

Bounds on $||P^{k+1} - P^k||$ for $n$ by $n$ stochastic matrix $P$ with trace $n-1$ and integer $k>>n$.

The problem: We have a $n$-state Markov chain with arbitrary initial distribution and transition matrix $P$ that is arbitrary except that we know that $P$ has trace $n-1$. Of course $P$ is also a ...
4
votes
1answer
690 views

A simple problem in markov chains

I'm trying to understand a 1954 paper of Kubo intitled "Note on the stochastic theory of resonance absorption". The specific problem can be stated mathematically as follows: let $X(t)$ be a random ...
2
votes
2answers
1k views

Is there MDPs (Markow Decision Process) which have a non deterministic optimal policy ?

I'm working on Markov Decision Process and I have not found yet an example of MDP that has a stochastic (non deterministic) optimal policy. Is there MDPs that have a stochastic optimal policy or is it ...
6
votes
2answers
847 views

Expectation of first positive value in random walk

Let $p$ be a parameter in $]0,1[$. Let $(X_k)_{k\geq 0}$ be an independent, identically distributed sequence of random variables, such that each $X_k$ takes values only in $\lbrace -1, \frac{1-p}{p} ...
0
votes
1answer
100 views

how to find a sequence of digits in base b such that each consecutive block of size k appears exactly once?

My question is most precisely stated in the title. As an example, if we consider base 10, and k=4, then I am asking, is it possible to have a sequence of length 10^4 + 3, such that each 4 digit number ...
1
vote
1answer
2k views

How to do integration using MCMC?

I want to evaluate $I = \int_V f(\vec{x}) d\vec{x}$. The classical Monte Carlo method is to sample uniformly from within the integration volume $V$, and then compute $I \approx V \frac{1}{N} ...
8
votes
1answer
383 views

Potts model simulation

I was wondering what were the state-of-the-art methods to simulate low temperature configurations of Potts-like models that exhibit a discontinuous phase transition. For models with a continuous phase ...
1
vote
2answers
465 views

Markov chain convergence problem.

Consider a markov chain matrix P of size n x n (n states). P is known to be: 1- there are at least two absorbent states. one of them is denoted by null. (thus, we have that P_null,null = 1) 2- For ...
-2
votes
3answers
690 views

Convergence of a markov matrix

Consider a markov chain matrix P of size n x n (n states). P is known to be: 1- Not irreducible (i.e. there exist at least a pair of states i, j such that we cannot go from i to j) 2- Not all ...
15
votes
5answers
2k views

Where to publish a paper on the Mafia game?

I wrote a research paper "A mathematical model of the Mafia game" (arXiv:1009.1031 [math.PR]). However, I do not know where to publish it. As an undergraduate studying majorly physics, I have little ...
1
vote
1answer
316 views

Lower bound on the convergence rate of a specific Markov chain

I have a Markov chain $\mathbf{A} = (A_0, A_1, \ldots)$ with state space $\{0, \ldots, n\}$ which converges towards a stationary distribution $\pi$. There are a lot of well-known results on ...
3
votes
1answer
390 views

(Stochastic) matrix for which a stochastic matrix logarithm exists?

I think this is basically the inverse question of Matrices whose exponential is stochastic. i.e. what are sufficient conditions on the matrix representation of an evolution operator of a (finite) ...
13
votes
0answers
677 views

representation theoretic interpretation of Jack polynomials

Monomial symmetric polynomials on $n$ variables $x_1, \ldots x_n$ form a natural basis of the space $\mathcal{S}_n$ of symmetric polynomials on $n$ variables and are defined by additive symmetrization ...
13
votes
0answers
720 views

Diagonalizing some matrices arising from Fourier transform on $S_n$.

Consider the function $f$ on $S_n$ which equals $1/n$ on all adjacent transpositions $(i,i+1)$, where we let $n+1 = 1$, and $0$ otherwise, and its Fourier transform $\hat{f}(\rho)$ evaluated at the ...
1
vote
0answers
256 views

Markov Chain Patterns

Hi I would like to detect repetitive patterns and deviations from these repetitions. I have historical data and can calculate probabilities for the transitions between my many states. I have ...
13
votes
2answers
1k views

Random walk is to diffusion as self-avoiding random walk is to …?

One can view a random walk as a discrete process whose continuous analog is diffusion. For example, discretizing the heat diffusion equation (in both time and space) leads to random walks. Is there a ...
63
votes
3answers
3k views

Gromov's list of 7 constructions in differential topology

At the 2010 Clay Research Conference, Gromov explained that we know of only 7 different methods for constructing smooth manifolds. Working from memory, and hence not necessarily respecting the order ...
3
votes
1answer
319 views

initial condition of a diffusion approximation

I am trying to prove that a certain sequence of Markov chains $x^N_k$ converges towards a diffusion process. The invariant measure of $x^N$ is $\pi^N$ and the Markov chain $x^N$ is started in ...
7
votes
1answer
242 views

Existence of Limiting Distribution for Moving Regions in Stat. Phys. Models

As the title (hopefully) suggests, I've been trying to prove (or disprove) the existence of a limiting distribution for a certain projection in a statistical physics model. I'll give the details of ...
2
votes
1answer
501 views

“Induced” arrivals in an M/M/1 queue?

I'm a newcomer to the realm of queueing theory, so please bear with me :) I'd like to model web server traffic with a modified M/M/1 queue. In the simple case we have two parameters - $\lambda$ for ...
4
votes
1answer
449 views

When is a 1-block factor of a non-Markovian process Markov?

Let $Y$ be a discrete stationary stochastic process. Suppose that $Y$ is not $n$-step Markov for any positive integer $n$. Let $Z$ be a 1-block factor of $Y$. For what condition on $Y$ or the ...
7
votes
2answers
297 views

Examples of Slowly Mixing Chains in Statistics

This should probably be community wiki, but I don't know how to set that myself. I'm looking for examples or Markov chains that are used in statistics or statistical physics, and which are known to ...
3
votes
1answer
265 views

Finitarily Markovian Finite Factors of Bernoulli Schemes

By processes, I mean discrete, stationary stochastic processes, that is $(X,\mathcal{U},\mu,T)$ where $X$ is the set of doubly infinite sequences of some alphabet $A$, $\mathcal{U}$ is the ...
13
votes
3answers
1k views

Markov chain on Groups

Let $G$ be a permutation group on the finite set $\Omega$. Consider the Markov chain where you start with an element $\alpha \in \Omega$ chosen from some arbitrary starting probability distribution. ...
5
votes
2answers
637 views

Is there a way to analytically compute the recurrence time of a finite Markov process?

Let $X_t$ be an ergodic (time-homogeneous) Markov process (in discrete or continuous time) on a finite state space $\{1,\dots,n\}$. Let $T(X_0)$ be the stopping time given by the infimum of times such ...
0
votes
1answer
309 views

Where can I learn about master equation?

I am reading a paper by Dorogovstev on structure of growing complex networks with preferential linking. I need to learn master equation for this. I need a reference for the same.
4
votes
2answers
292 views

Efficiently sampling points from an integer lattice.

Let $\mathcal{L}$ = {x$\in$ $N^n$ : ||x||$_1$ $\leq$ m} denote the set of integer points in the positive orthant of the $\ell_1$ ball of radius $m$, where $m < n$. For each $x \in \mathcal{L}$, let ...
16
votes
9answers
2k views

How can I generate random permutations of [n] with k cycles, where k is much larger than log n?

I've been thinking a lot lately about random permutations. It's well-known that the mean and variance of the number of cycles of a permutation chosen uniformly at random from Sn are both ...