ИСТИНА |
Войти в систему Регистрация |
|
Интеллектуальная Система Тематического Исследования НАукометрических данных |
||
\documentclass[12pt]{article} \usepackage[T2A]{fontenc} \usepackage[cp1251]{inputenc} \renewcommand{\baselinestretch}{1.5} \textwidth=160mm \textheight=232mm \voffset=-22mm \pagestyle{empty} \begin{document} \centerline{\large\bf Classification of loaded graphs} \centerline{\large\bf and convergence of equilibrium states} \medskip \centerline{\bf Gurevich B.M.} \medskip \centerline{\it Moscow State University, Institute for Information Transmission Problems RAS} \centerline{\it bmgbmg2@gmail.com} \bigskip Let $G=(V,E)$ be a countable directed graph with vertex set $V$ and edge set $E\subseteq V\times V$, and $\mathcal W$ a positive function on $E$. The pair $(G,\mathcal W)$ is called a {\it loaded graph} with {\it weight function} $\mathcal W$. If $e\in E$, let $s(e)$ and $t(e)$ denote the starting and terminal vertices of $e$. A sequence $e_1,\dots,e_n$, $e_i\in E$, is called a path of length $n$ in $G$ if $t(e_i)=s(e_{i+1})$, $i=1,\dots,n-1$. For $n\geq1$ and $v\in V$, let $\Gamma_{v}^{(n)}$ be the set of the paths in $G$ such that $s(e_1)=t(e_n)=v$ ($v$-cycles), and $\Gamma_{v|v}^{(n))}$ the set of all paths in $\Gamma_{v}^{(n)}$ that do not visit $v$ in between (simple $v$-cycles). For each path $\gamma=e_1,\dots,e_n$, denote $\mathcal W(\gamma):=\mathcal W(e_1)\cdot\dots\cdot\mathcal W(e_n)$ (the weight of $\gamma$). Let $$ \mathcal W_v^{(n)}:=\sum_{\gamma\in\Gamma_v^{(n)}}\mathcal W(\gamma),\ \ \mathcal W_{v|v}^{(n)}:=\sum_{\gamma\in\Gamma_{v|v}^{(n)}}\mathcal W(\gamma),\ \ v\in V. $$ Introduce the generating functions $$ \Phi_v(t)= \sum_{n=1}^\infty \mathcal W_v^{(n)}t^n,\ \ \ \ \Phi_{v|v}(t)= \sum_{n=1}^\infty\mathcal W_{v|v}^{(n)}t^n, $$ and denote the radii of convergence of these power series by $R_v$ and $R_{v|v}$, respectively. Clearly $R_v\le R_{v|v}$. Assume that $G$ is connected, then $R_v$ does not depend on $v$, and we may denote it by $R$. We consider only the case that $R>0$. A loaded graph $(G,\mathcal W)$ is said to be {\it recurrent} and {\it positive recurrent} if for some $v\in V$, $\Phi_v(R)=\infty$ and $\mathcal W_v^{(n)}R^n$ does not go to zero, respectively, as $n\to\infty$. $(G,\mathcal W)$ is known to be positive recurrent if, for some $v\in V$, either $\Phi_{v|v}(R)>1$, or $\Phi_{v|v}(R)=1$ and $\Phi'_{v|v}(R)<\infty$. In the former case $(G,\mathcal W)$ is said to be {\it stable positive recurrent}, in the latter case it is {\it unstable positive recurrent}. All properties in these definitions are obeyed or not for all $v$ simultaneously (as $G$ is connected). A finite loaded graph is always stable positive recurrent. Let $X=X(G)\bigsqcup$ be the space of two-sided infinite paths in $G$, i.e., $$ X=\{x=(x_i)_{i\in\mathbf Z}:x_i\in E,\ s(x_{i+1})=t(x_i),\ i\in\mathbf Z\}. $$ Introduce the standard topology on $X$ and observe that $X$ is compact in this topology if and only if $G$ is finite. The shift transformation $S:X\to X$ defined by $(Sx)_i=x_{i+1}$, $x\in X$, $i\in\mathbf Z$, is a homeomorphism of $X$. Denote the set of $S$-invariant ergodic Borel probability measures on $X$ by $\mathcal E=\mathcal E(X,S)$ and define a function $f=f_{G,\mathcal W}:X\to\mathbf R$ by $$ f(x):=-\ln\,\mathcal W(x_0),\ \ x=(x_i)_{i\in\mathbf Z}\in X(G). $$ Let $P_f(\mu):=h_\mu(S)+\mu(f)$ for all $\mu\in\mathcal E$ such that $f\in L^1_\mu$; here $\mu(f):=\int_Xfd\mu$, and $h_\mu(S)$ is the entropy of the dynamical system $(X,\mu,S)$. A measure $\mu_0\in\mathcal E$ is said to be $\mathcal W$-{\it equilibrium} if $P_f(\mu)$ reaches its maximum at $\mu_0$. It is known that such a measure exists if and only if $\mathcal W$ is positive recurrent; then it is unique. Given a subset $\tilde V\subset V$, consider the subgraph $\tilde G=(\tilde V,\tilde E)$ of $G$, where $\tilde E=\{e\in E:s(e),t(e)\in \tilde V\}$, and the weight function $\tilde \mathcal W=\mathcal W|_{\tilde E}$, the restriction of $\mathcal W$ to $\tilde E$. This determines $(\tilde G,\tilde\mathcal W)$ as a loaded subgraph of $(G,\mathcal W)$. A sequence of loaded subgraphs $(G_n,\mathcal W_n)$ of a loaded graph $(G,\mathcal W)$ is called exhaustive if 1) $\bigcup_nV(G_n)=V(G)$, $\bigcup_nE(G_n)=E(G)$, 2) $V(G_n)\subset V(G_{n+1})$, $E(G_n)\subset E(G_{n+1})$, $n=1,2,\dots$, and 3) $\mathcal W_n$ is the restriction of $\mathcal W$ to $E(G_n)$, $n=1,2,\dots$. The aim of this report is to describe, for different classes of infinite loaded graphs, the asymptotic behavior of the $\mathcal W_n$-equilibrium measures corresponding to exhaustive sequences of finite loaded subgraphs $(G_n,\mathcal W_n)$ as $n\to\infty$. Open questions and possible generalizations will also be presented. \end{document}