Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userProjections of the Aldous chain on binary trees: Intertwining and consistency
83
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Consider the Aldous Markov chain on the space of rooted binary trees with $n$ labeled leaves in which at each transition a uniform random leaf is deleted and reattached to a uniform random edge. Now, fix $1le k < n$ and project the leaf mass onto the subtree spanned by the first $k$ leaves. This yields a binary tree with edge weights that we call a decorated $k$-tree with total mass $n$. We introduce label swapping dynamics for the Aldous chain so that, when it runs in stationarity, the decorated $k$-trees evolve as Markov chains themselves, and are projectively consistent over $kle n$. The construction of projectively consistent chains is a crucial step in the construction of the Aldous diffusion on continuum trees by the present authors, which is the $nrightarrow infty$ continuum analogue of the Aldous chain and will be taken up elsewhere. Some of our results have been generalized to Fords alpha model trees.
rate research
Read More
Aldous [(2007) Preprint] defined a gossip process in which space is a discrete $Ntimes N$ torus, and the state of the process at time $t$ is the set of individuals who know the information. Information spreads from a site to its nearest neighbors at rate 1/4 each and at rate $N^{-alpha}$ to a site chosen at random from the torus. We will be interested in the case in which $alpha<3$, where the long range transmission significantly accelerates the time at which everyone knows the information. We prove three results that precisely describe the spread of information in a slightly simplified model on the real torus. The time until everyone knows the information is asymptotically $T=(2-2alpha/3)N^{alpha/3}log N$. If $rho_s$ is the fraction of the population who know the information at time $s$ and $varepsilon$ is small then, for large $N$, the time until $rho_s$ reaches $varepsilon$ is $T(varepsilon)approx T+N^{alpha/3}log (3varepsilon /M)$, where $M$ is a random variable determined by the early spread of the information. The value of $rho_s$ at time $s=T(1/3)+tN^{alpha/3}$ is almost a deterministic function $h(t)$ which satisfies an odd looking integro-differential equation. The last result confirms a heuristic calculation of Aldous.
Aldous spectral gap conjecture asserts that on any graph the random walk process and the random transposition (or interchange) process have the same spectral gap. We prove the conjecture using a recursive strategy. The approach is a natural extension of the method already used to prove the validity of the conjecture on trees. The novelty is an idea based on electric network reduction, which reduces the problem to the proof of an explicit inequality for a random transposition operator involving both positive and negative rates. The proof of the latter inequality uses suitable coset decompositions of the associated matrices on permutations.
This paper considers the asymptotic distribution of the longest edge of the minimal spanning tree and nearest neighbor graph on X_1,...,X_{N_n} where X_1,X_2,... are i.i.d. in Re^2 with distribution F and N_n is independent of the X_i and satisfies N_n/nto_p1. A new approach based on spatial blocking and a locally orthogonal coordinate system is developed to treat cases for which F has unbounded support. The general results are applied to a number of special cases, including elliptically contoured distributions, distributions with independent Weibull-like margins and distributions with parallel level curves.
We construct a stationary Markov process corresponding to the evolution of masses and distances of subtrees along the spine from the root to a branch point in a conjectured stationary, continuum random tree-valued diffusion that was proposed by David Aldous. As a corollary this Markov process induces a recurrent extension, with Dirichlet stationary distribution, of a Wright-Fisher diffusion for which zero is an exit boundary of the coordinate processes. This extends previous work of Pal who argued a Wright-Fisher limit for the three-mass process under the conjectured Aldous diffusion until the disappearance of the branch point. In particular, the construction here yields the first stationary, Markovian projection of the conjectured diffusion. Our construction follows from that of a pair of interval partition-valued diffusions that were previously introduced by the current authors as continuum analogues of down-up chains on ordered Chinese restaurants with parameters (1/2,1/2) and (1/2,0). These two diffusions are given by an underlying Crump-Mode-Jagers branching process, respectively with or without immigration. In particular, we adapt the previous construction to build a continuum analogue of a down-up ordered Chinese restaurant process with the unusual parameters (1/2,-1/2), for which the underlying branching process has emigration.
Consider a uniformly sampled random $d$-regular graph on $n$ vertices. If $d$ is fixed and $n$ goes to $infty$ then we can relate typical (large probability) properties of such random graph to a family of invariant random processes (called typical processes) on the infinite $d$-regular tree $T_d$. This correspondence between ergodic theory on $T_d$ and random regular graphs is already proven to be fruitful in both directions. This paper continues the investigation of typical processes with a special emphasis on entropy. We study a natural notion of micro-state entropy for invariant processes on $T_d$. It serves as a quantitative refinement of the notion of typicality and is tightly connected to the asymptotic free energy in statistical physics. Using entropy inequalities, we provide new sufficient conditions for typicality for edge Markov processes. We also extend these notions and results to processes on unimodular Galton-Watson random trees.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
