ترغب بنشر مسار تعليمي؟ اضغط هنا

Typicality and entropy of processes on infinite trees

65   0   0.0 ( 0 )
 نشر من قبل Charles Bordenave
 تاريخ النشر 2021
  مجال البحث
والبحث باللغة English




اسأل ChatGPT حول البحث

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.



قيم البحث

اقرأ أيضاً

Consider a statistical physical model on the $d$-regular infinite tree $T_{d}$ described by a set of interactions $Phi$. Let ${G_{n}}$ be a sequence of finite graphs with vertex sets $V_n$ that locally converge to $T_{d}$. From $Phi$ one can construc t a sequence of corresponding models on the graphs $G_n$. Let ${mu_n}$ be the resulting Gibbs measures. Here we assume that ${mu_{n}}$ converges to some limiting Gibbs measure $mu$ on $T_{d}$ in the local weak$^*$ sense, and study the consequences of this convergence for the specific entropies $|V_n|^{-1}H(mu_n)$. We show that the limit supremum of $|V_n|^{-1}H(mu_n)$ is bounded above by the emph{percolative entropy} $H_{perc}(mu)$, a function of $mu$ itself, and that $|V_n|^{-1}H(mu_n)$ actually converges to $H_{perc}(mu)$ in case $Phi$ exhibits strong spatial mixing on $T_d$. We discuss a few examples of well-known models for which the latter result holds in the high temperature regime.
Chase-escape is a competitive growth process in which red particles spread to adjacent uncolored sites, while blue particles overtake adjacent red particles. We introduce the variant in which red particles die and describe the phase diagram for the r esulting process on infinite d-ary trees. A novel connection to weighted Catalan numbers makes it possible to characterize the critical behavior.
95 - Natasha Dobrinen 2019
This article discusses some recent trends in Ramsey theory on infinite structures. Trees and their Ramsey theory have been vital to these investigations. The main ideas behind the authors recent method of trees with coding nodes are presented, showin g how they can be useful both for coding structures with forbidden configurations as well as those with none. Using forcing as a tool for finite searches has allowed the development of Ramsey theory on such trees, leading to solutions for finite big Ramsey degrees of Henson graphs as well as infinite dimensional Ramsey theory of copies of the Rado graph. Possible future directions for applications of these methods are discussed.
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$.
119 - Tobias Johnson 2020
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.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا