اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدA symmetric entropy bound on the non-reconstruction regime of Markov chains on Galton-Watson trees
165
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We give a criterion of the form Q(d)c(M)<1 for the non-reconstructability of tree-indexed q-state Markov chains obtained by broadcasting a signal from the root with a given transition matrix M. Here c(M) is an explicit function, which is convex over the set of Ms with a given invariant distribution, that is defined in terms of a (q-1)-dimensional variational problem over symmetric entropies. Further Q(d) is the expected number of offspring on the Galton-Watson tree. This result is equivalent to proving the extremality of the free boundary condition-Gibbs measure within the corresponding Gibbs-simplex. Our theorem holds for possibly non-reversible M and its proof is based on a general Recursion Formula for expectations of a symmetrized relative entropy function, which invites their use as a Lyapunov function. In the case of the Potts model, the present theorem reproduces earlier results of the authors, with a simplified proof, in the case of the symmetric Ising model (where the argument becomes similar to the approach of Pemantle and Peres) the method produces the correct reconstruction threshold), in the case of the (strongly) asymmetric Ising model where the Kesten-Stigum bound is known to be not sharp the method provides improved numerical bounds.
قيم البحث
اقرأ أيضاً
We study the totally asymmetric simple exclusion process (TASEP) on trees where particles are generated at the root. Particles can only jump away from the root, and they jump from $x$ to $y$ at rate $r_{x,y}$ provided $y$ is empty. Starting from the
all empty initial condition, we show that the distribution of the configuration at time $t$ converges to an equilibrium. We study the current and give conditions on the transition rates such that the current is of linear order or such that there is zero current, i.e. the particles block each other. A key step, which is of independent interest, is to bound the first generation at which the particle trajectories of the first $n$ particles decouple.
At each site of a supercritical Galton-Watson tree place a parking spot which can accommodate one car. Initially, an independent and identically distributed number of cars arrive at each vertex. Cars proceed towards the root in discrete time and park
in the first available spot they come to. Let $X$ be the total number of cars that arrive to the root. Goldschmidt and Przykucki proved that $X$ undergoes a phase transition from being finite to infinite almost surely as the mean number of cars arriving to each vertex increases. We show that $EX$ is finite at the critical threshold, describe its growth rate above criticality, and prove that it increases as the initial car arrival distribution becomes less concentrated. For the canonical case that either 0 or 2 cars arrive at each vertex of a $d$-ary tree, we give improved bounds on the critical threshold and show that $P(X = 0)$ is discontinuous.
A recursive function on a tree is a function in which each leaf has a given value, and each internal node has a value equal to a function of the number of children, the values of the children, and possibly an explicitly specified random element $U$.
The value of the root is the key quantity of interest in general. In this first study, all node values and function values are in a finite set $S$. In this note, we describe the limit behavior when the leaf values are drawn independently from a fixed distribution on $S$, and the tree $T_n$ is a random Galton--Watson tree of size $n$.
Distinguishing between continuous and first-order phase transitions is a major challenge in random discrete systems. We study the topic for events with recursive structure on Galton-Watson trees. For example, let $mathcal{T}_1$ be the event that a Ga
lton-Watson tree is infinite, and let $mathcal{T}_2$ be the event that it contains an infinite binary tree starting from its root. These events satisfy similar recursive properties: $mathcal{T}_1$ holds if and only if $mathcal{T}_1$ holds for at least one of the trees initiated by children of the root, and $mathcal{T}_2$ holds if and only if $mathcal{T}_2$ holds for at least two of these trees. The probability of $mathcal{T}_1$ has a continuous phase transition, increasing from 0 when the mean of the child distribution increases above 1. On the other hand, the probability of $mathcal{T}_2$ has a first-order phase transition, jumping discontinuously to a nonzero value at criticality. Given the recursive property satisfied by the event, we describe the critical child distributions where a continuous phase transition takes place. In many cases, we also characterize the event undergoing the phase transition.
When normal and mis`{e}re games are played on bi-type binary Galton-Watson trees (with vertices coloured blue or red and each having either no child or precisely $2$ children), with one player allowed to move along monochromatic edges and the other a
long non-monochromatic edges, the draw probabilities equal $0$ unless every vertex gives birth to one blue and one red child. On bi-type Poisson trees where each vertex gives birth to Poisson$(lambda)$ offspring in total, the draw probabilities approach $1$ as $lambda rightarrow infty$. We study such emph{nove
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
