
\documentclass[10pt, reqno]{amsart}
\usepackage[cp1251]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage[hidelinks,unicode]{hyperref}
\usepackage{indentfirst}
\usepackage{anyfontsize}
\usepackage{dsfont}
\usepackage{relsize}

\def\udcs{519.724} %Here the author places classificators of the paper according to Russian classification system
\def\mscs{60K25,90B15} %Here the author places  classificators according to the AMS classification list.
\setcounter{page}{1}

\newtheorem{lemma}{Лемма}
\newtheorem{theorem}{Теорема}
\newtheorem{definition}{Определение}
\newtheorem{corollary}{Следствие}
\newtheorem{proposition}{Предложение}

\newtheorem*{theorem*}{Теорема}
\newtheorem{repeated_theorem}{Теорема}
\newtheorem{numbered_theorem}{Утверждение}
\newtheorem{numbered_corollary}{Замечание}

\usepackage{hyperref}

% \setmathfont{DejaVu Sans}
% DejaVu Sans: $\mathbb{\Gamma\gamma\Pi\pi\sum}$

\newcommand{\norm}[1]{\left\lVert#1\right\rVert}

\newcommand{\cgy}[6]{
	\text{П}\arraycolsep=1.4pt\def\arraystretch{0.87}
	\scriptsize
	\begin{array}{ccc}
		#2 & #4 & #6\\
		#1 & #3 & #5
	\end{array}
	\normalsize
}

\newcommand{\stcomp}[1]{\overline{#1}}

\DeclareMathOperator*{\E}{\mathbb{E}}
\DeclareMathOperator*{\Pb}{\mathbb{P}}

\def\logo{{\bf\huge S\raisebox{0.2ex}{\hspace{0.55ex}\raisebox{0.05ex}e\hspace{-1.65ex}$\bigcirc$}MR}}

\def\semrtop
{
	\vbox{
		\noindent\logo
		\hspace{80mm}\raisebox{1ex}{ISSN 1813-3304 }
		
		\vspace{5mm}
		
		\begin{center}
			{\huge СИБИРСКИЕ \ ЭЛЕКТРОННЫЕ} \\[2mm]
			{\huge МАТЕМАТИЧЕСКИЕ ИЗВЕСТИЯ} \\[2mm]
			{\large Siberian Electronic Mathematical Reports} \\[1mm]
			{\LARGE\tt{http://semr.math.nsc.ru}}\\[0.5mm]
			%     {\small Институт математики им. С.Л.Соболева СО РАН}\\[-1mm]
			%     {\small Sobolev Institute of Mathematics SB RAS}
		\end{center}
		\vspace{-3mm}
		\noindent
		\begin{tabular}{c}
			\hphantom{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa} \\
			\hline\hline
		\end{tabular}
		
		\vspace{1mm}
		{\flushleft\it Том 16, стр. 144--144 (2019) \hspace{65mm}{\rm\small УДК \udcs}}
		\newline
		{\rm\small DOI~10.33048/semi.2019.16.xxx}\hphantom{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa}{\rm\small MSC\ \ \mscs }
	}%\vbox
}


\begin{document}
	\renewcommand{\refname}{References}
	
	
	\thispagestyle{empty}
	
	\title[\myshorttitle]{Стабильность и нестабильность систем случайного множественного доступа с механизмом накопления и потери энергии}
	\author{{А.В. Резлер, М.Г. Чебунин}}%
	
	\address{Alexandr Vadimovich Rezler
		\newline\hphantom{iii} Novosibirsk State University
		\newline\hphantom{iii} 2, Pirogova str.
		\newline\hphantom{iii} St.-Petersburg University of Aerospace Instrumentation, 
		\newline\hphantom{iii} Bolshaya Morskaya 67,
		\newline\hphantom{iii} 190000, St.-Petersburg, Russia.}%
	
	\email{rezlers123@gmail.com}%
	\address{Mikhail Georgievich Chebunin
		\newline\hphantom{iii} Karlsruhe Institute of Technology,
		\newline\hphantom{iii} Institute of Stochastics,
		\newline\hphantom{iii} Karlsruhe, 76131, Germany.}%
	
	\email{chebuninmikhail@gmail.com}%
	
	
	
	\thanks{\sc A. Rezler, M. Chebunin,
		Stability and instability of a random multiple access system with an energy harvesting and self-discharge mechanism}
	\thanks{\copyright \ 2023 Резлер А.В., Чебунин М.Г}
	\thanks{\rm Работа первого автора выполнена при финансовой поддержке Российского научного фонда, грант №22-19-00305 "Пространственно-временные стохастические модели беспроводных сетей с большим числом абонентов"}
	
	
	\semrtop \vspace{1cm}
	\maketitle {\small
		\begin{quote}
			\noindent{\sc Abstract. } We study a generalisation of the model of the classical synchronised multiple access system with a single transmission channel controlled by a randomised transmission protocol (ALOHA) and additionally equipped with an energy harvesting mechanism as well as self-discharge mechanism and suppose that message batteries may receive an unlimited amount of energy.\medskip
			
			\noindent{\bf Keywords:} Markov chains, ALOHA algorithm, energy harvesting, self-discharge, generalised Foster criterion, ergodicity, transience.
	\end{quote}}
	
	
	\section{Введение}
	
	Использование энергетической подпитки (energy harvesting) позволяет устройствам непрерывно получать энергию из различных источников окружающей среды, таких как, например, свет, тепло, вибрация и множество других. Несмотря на то, что количество энергии, получаемое таким образом, сравнительно невелико, данная технология находит широкое применение, например, среди устройств с низким потреблением энергии (Low-Power Systems). Снабжение устройств механизмом энергетической подпитки позволяет использовать их в тех местах, где классические источники энергии недоступны. В силу того, что заряд батарей непрерывно восполняется, продолжительность "жизни"$ $ используемых устройств может быть продлена. Например, в работе \cite{Harb_Adnan} приведен пример устройства, использующего микроэлектромеханические (MEMS) системы для извлечения энергии из вибраций окружающей среды.
	
	Механизм энергетической подпитки также имеет широкое применение среди систем множественного доступа. Например, сенсорные сети, оснащенные перезаряжающимися батареями, которые "подпитываются"$ $ энергией из окружающей среды, могут существенно продлить срок ее службы (см. \cite{Sudevalayam_Kulkarni}). Другой пример использования данного механизма был предложен в работе \cite{Example_of_applying_Xun_Zhou}, где авторы рассмотрели многопользовательскую систему с базовой станцией, использующей технологию <<OFDM>> (orthogonal frequency division multiplexing)$ $ и беспроводной канал для передачи информации и энергии пользователям.
	
	Одной из основных задач, возникающих при исследовании систем случайного множественного доступа, оснащенных механизмом энергетической подпитки, является задача нахождения пропускных способностей систем. Например, в статье \cite{Jeon_finite_users} рассматривалась система с ограниченным количеством пользователей, децентрализованным механизмом энергетической подпитки и протоколом передачи данных типа ALOHA. В статье была найдена пропускная способность данной системы, а также был продемонстрирован эффект ее уменьшения при ограничении вместимости у механизма для хранения энергии, которым снабжен каждый пользователь системы. Изучению энергоэффективности протоколов разрешения конфликтов посвящена работа \cite{Efficiency_protocols}.
	
	Как известно, традиционные (в частности, не использующие механизм энергетической подпитки) системы множественного доступа (см. например \cite{Abramson_dev_of_aloha_net}, \cite{FGL_1977}) с бесконечным числом пользователей в известном смысле нестабильны ни при каких значениях управляемых параметров (см. \cite{Kelly_classical_aloha_instability}) и метастабильны при малых значениях входного потока и вероятности передачи сообщений (см. \cite{Vvedenskaya_metastability}). Однако, как было показано в работах \cite{Foss_2014} и \cite{Foss_original}, ограничения на поступление энергии и входной поток в систему с бесконечным числом пользователей может стабилизировать ее, не позволяя сообщениям в накопителе неограниченно расти. В статье \cite{Foss_2014} была найдена пропускная способность модели классической синхронизированной системы случайного множественного доступа с одним передающим прибором, управляемой протоколом передачи типа ALOHA и снабженной централизованным механизмом энергетической подпитки. Однако, как отмечают авторы, такая модель далека от практики. Тем не менее, рассмотренная в работе \cite{Foss_original} модель для децентрализованного механизма энергетической подпитки, в которой каждый пользователь системы снабжен индивидуальным механизмом для хранения энергии, имеет практические аналоги. В упомянутой работе при определении конкретного вида функции интенсивности подзарядки сообщений на каждом шаге, обратно пропорциональной общему количеству присутствующих в системе сообщений, была найдена пропускная способность системы.
	
	В статье \cite{Rezler_Chebunin} изучалось обобщение предыдущей модели. Главное отличие состояло в том, что сообщения могут принимать более одной единицы энергии. Одной из причин изучения обобщенной модели являлся эффект, продемонстрированный в работе \cite{Jeon_finite_users}, возникающий при увеличении емкости накопителя энергии у пользователей и, как следствие, приводящий к увеличению области стабильности системы. Однако результаты, полученные в статье \cite{Rezler_Chebunin}, показывают, что максимальная пропускная способность системы не меняется при заданной интенсивности подзарядки. 
	
	Любая система, использующая механизм энергетической подпитки, помимо "сборщика"$ $ энергии, снабжена аккумулятором, который имеет свойство саморазрядки, то есть потери энергии в период простоя. Будет логичным учитывать данное свойство в моделях, соответствующих описываемым системам. В данной работе мы обобщаем результаты, полученные в статье \cite{Rezler_Chebunin}, на случай, учитывающий эффект саморазрядки. Главное отличие от предыдущих результатов состоит в изменении функции интенсивности подзарядки для сохранения пропускной способности системы.
	
	Работа состоит из 5 параграфов и Приложения. Во втором параграфе описывается математическая модель и формулируется основной результат, в третьем параграфе проводится доказательство стабильности и нестабильности для частного случая описанной модели, когда каждая батарея имеет только одну ячейку для хранения энергии. В четвертом параграфе проводится доказательство основной теоремы. В пятом параграфе рассматривается случай, когда каждая батарея имеет произвольное ограниченное количество ячеек для хранения энергии. В Приложении приводятся формулировки утверждений, используемых при доказательстве теорем.
	
	\section{Описание модели и основные результаты}
	Мы рассматриваем систему случайного множественного доступа (далее \textit{систему}/\textit{модель}) с одним передающим прибором, которая принимает и, при успешной передаче, отправляет сообщения. Время слотировано. Пусть $\xi_{n}$ --- случайная величина, определяющая количество сообщений, поступивших в накопитель системы в течении интервала времени $[n-1, n)$ (далее \textit{$n$-ый временной слот}), и $\{\xi_{n}\}_{n \geq 0}$ образует семейство независимых одинаково распределенных (н.о.р.) неотрицательных целочисленных случайных величин с конечным математическим ожиданием $\lambda$. Мы предполагаем, что за один временной слот систему может покинуть только 1 сообщение, то есть в каждом временном слоте возможны 3 различные ситуации:
	\begin{itemize}
		\item На передающий прибор не поступало сообщений (\textit{пустой слот}).
		\item На передающий прибор поступило одно сообщение и к концу временного слота покинуло систему (\textit{успех}).
		\item На передающий прибор поступило 2 и более сообщений и к концу временного слота они вернулись в накопитель системы (\textit{конфликт}).
	\end{itemize}
	Пусть $p \in (0, 1)$ и $\widehat{p} \in [0, 1]$ -- фиксированные параметры системы. Мы предполагаем, что каждое сообщение снабжено батареей с неограниченным количеством ячеек для хранения энергии, прибывает в накопитель системы с разряженной батареей, а также имеет механизм энергетической подпитки. При этом батарея подвержена эффекту саморазрядки. Полный цикл работы системы в каждом временном слоте разбит на следующие 5 последовательных интервалов:
	\begin{itemize}
		\item[(\it{\romannumeral 1})] Каждое сообщение, имеющее в начале временного слота батарею, заряженную на $i \geq 0$ ячеек, независимо от остальных параметров системы поступает на передающий прибор с вероятностью $p_{i}:=1-p^{i}$ или остается в накопителе с вероятностью $1-p_{i}$.
		\item[(\it{\romannumeral 2})] Каждое заряженное сообщение, оставшееся в накопителе, независимо от остальных параметров системы теряет одну единицу энергии с вероятностью $\widehat{p}$.
		\item[(\it{\romannumeral 3})] Новые сообщения поступают в накопитель с разряженной батареей.
		\item[(\it{\romannumeral 4})] Каждое сообщение из накопителя, которое не потеряло заряд в интервале (\textit{\romannumeral 2}), получает единицу заряда с вероятностью $\mu \in [0, 1]$, которая зависит от общего количества сообщений, находящихся в системе к началу временного слота.
		\item[(\it{\romannumeral 5})] Если в интервале (\textit{\romannumeral 1}) произошел конфликт, то сообщения, поступившие на передающий прибор, возвращаются в накопитель, теряя одну единицу заряда.
	\end{itemize}
	Случай $p=0$ мы не рассматриваем, так как он эквивалентен стандартному централизованному протоколу ALOHA, а при $p=1$ сообщения не могут покинуть систему. Заметим, что вторая система, рассмотренная в работе \cite{Rezler_Chebunin}, совпадает с данной системой при $\widehat{p}=0$, то есть при отсутствии эффекта саморазрядки.
	
	Пусть $\xi_{n}$ --- количество новых сообщений, которые прибыли в накопитель системы в течении $n$-го временного слота в интервале (\textit{\romannumeral 3}), а $q_{n}$ --- количество сообщений, присутствующих в системе к началу $(n+1)$-го временного слота. Обозначим через $v^{(i)}_{n}$ количество сообщений, имеющих $i \geq 0$ единиц энергии к началу $(n+1)$-го временного слота. Очевидно, что
	\begin{align*}
	\sum_{i=0}^{\infty}v^{(i)}_{n} = q_{n} \text{ п.н.}
	\end{align*}
	Определим семейство независимых равномерно распределенных в единичном кубе $[0, 1]^{3}$ случайных величин $\{\pmb{U}_{n, j}^{(i)}\}_{n, i \geq 0, j \geq 1}$, независимых от входного потока, то есть $\{\xi_{n}\}_{n \geq 0}$. Заметим, что данное семейство случайных величин можно разбить на три независимых семейства независимых случайных величин, имеющих равномерное распределение на единичном отрезке, $\big\{U^{(i)}_{n,j}\big\}$, $\big\{\widehat{U}^{(i)}_{n,j}\big\}$ и $\big\{\widetilde{U}^{(i)}_{n,j}\big\}$ так, что
	\begin{align*}
	\pmb{U}_{n, j}^{(i)} = \left(U^{(i)}_{n,j}, \widehat{U}^{(i)}_{n,j}, \widetilde{U}^{(i)}_{n,j}\right).
	\end{align*}
	Пусть $\mathds{1}(A)$ --- индикаторная функция события $A$, а $\mu:\mathbf{Z}_{+} \to [0,1]$ --- некоторая измеримая неотрицательная функция. В зависимости от количества сообщений, скажем, к началу $(n+1)$-го временного слота $q_{n}$, значение $\mu(q_{n})$ равно вероятности подзарядки каждого сообщения в интервале (\textit{\romannumeral 4}) в течении $(n+1)$-го временного слота. Определим через
	\begin{align*}
	\cgy{u}{v}{\widehat{u}}{\widehat{v}}{\widetilde{u}}{\widetilde{v}} = [u, v] \times [\:\widehat{u}, \widehat{v}\:] \times [\:\widetilde{u}, \widetilde{v}\:] \quad \overset{*}{u}, \overset{*}{v} \in [0, 1];\; * \in \{\quad, \widehat{\quad}, \widetilde{\quad}\},
	\end{align*}
	соответствующую область в единичном кубе $[0, 1]^{3}$ и случайные величины \\$B^{(i)}_{n}\left(k, \cgy{u}{v}{\widehat{u}}{\widehat{v}}{\widetilde{u}}{\widetilde{v}}\right)$ следующим образом:
	\begin{align*}
	B^{(i)}_{n}\left(k, \cgy{u}{v}{\widehat{u}}{\widehat{v}}{\widetilde{u}}{\widetilde{v}}\right) = \begin{cases}
	\sum\limits_{j=1}^{k}\mathds{1}\left(\:\pmb{U}_{n, j}^{(i)} \in \cgy{u}{v}{\widehat{u}}{\widehat{v}}{\widetilde{u}}{\widetilde{v}}\:\right) & k \geq 1,\\
	0, & k=0.
	\end{cases}
	\end{align*}
	Пусть
	\begin{align*}
	I_{p}^{n} = \mathds{1}\left(\sum_{i=1}^{\infty}B^{(i)}_{n}\left(v^{(i)}_{n}, \cgy{0}{p_{i}}{0}{1}{0}{1}\right) = 1\right),
	\end{align*}
	то есть $I_{p}^{n}$ --- индикатор события, состоящего в том, что в $(n+1)$-ом временном слоте произошла успешная передача сообщения. Таким образом, мы получим следующую рекурсию.
	
	\fontsize{8.5}{9}\selectfont
	\begin{equation}
	\begin{cases}
	q_{n+1} = q_{n} - I_{p}^{n} + \xi_{n}, \\\\
	v_{n+1}^{(1)} = B_{n}^{(1)}\left(v_{n}^{(1)}, \cgy{p_{1}}{1}{\widehat{p}}{1}{\mu(q_{n})}{1}\right) + B_{n}^{(0)}\left(v_{n}^{(0)} + \xi_{n}, \cgy{0}{1}{0}{1}{0}{\mu(q_{n})}\right) \\+ B_{n}^{(2)}\left(v_{n}^{(2)}, \cgy{p_{2}}{1}{0}{\widehat{p}}{0}{1}\:\right) + B_{n}^{(2)}\left(v_{n}^{(2)}, \cgy{0}{p_{2}}{0}{1}{0}{1}\right)\cdot\left(1-I_{p}^{n}\right), \\
	...
	\\
	v_{n+1}^{(i)} = B_{n}^{(i)}\left(v_{n}^{(i)}, \cgy{p_{i}}{1}{\widehat{p}}{1}{\mu(q_{n})}{1}\right) + B_{n}^{(i-1)}\left(v_{n}^{(i-1)}, \cgy{p_{i-1}}{1}{\widehat{p}}{1}{0}{\mu(q_{n})}\right)\\ + B_{n}^{(i+1)}\left(v_{n}^{(i+1)}, \cgy{p_{i+1}}{1}{0}{\widehat{p}}{0}{1}\right) + B_{n}^{(i+1)}\left(v_{n}^{(i+1)}, \cgy{0}{p_{i+1}}{0}{1}{0}{1}\right)\cdot\left(1-I_{p}^{n}\right),\\
	...
	\end{cases}
	\tag{$M$}
	\label{M}
	% \label{not_coupling_equation}
	\end{equation}
	\normalsize
	где $v_{n}^{(0)} = q_{n} - \sum\limits_{i=1}^{\infty}v_{n}^{(i)}$. В силу громоздкости модели (\ref{M}), мы дадим интерпретацию ее слагаемых. Рассмотрим рекурсию для элементов $v_{n+1}^{(i)}$ при $i \geq 2$. Первое слагаемое
	\begin{align*}
	B_{n}^{(i)}\left(v_{n}^{(i)}, \cgy{p_{i}}{1}{\widehat{p}}{1}{\mu(q_{n})}{1}\right)
	\end{align*}
	равно количеству сообщений, которые не передавались на передающий прибор, не разряжались и не заряжались в течении $(n+1)$-го временного слота соответственно в интервалах (\textit{\romannumeral 1}), (\textit{\romannumeral 2}) и (\textit{\romannumeral 4}). Следующее слагаемое 
	\begin{align*}
	B_{n}^{(i-1)}\left(v_{n}^{(i-1)}, \cgy{p_{i-1}}{1}{\widehat{p}}{1}{0}{\mu(q_{n})}\right)
	\end{align*}
	равно количеству сообщений, заряженных на $i-1$ ячейку, которые получили единицу заряда в интервале (\textit{\romannumeral 4}) в течении $(n+1)$-го временного слота. Для случая $i=1$, в выражении для $v_{n+1}^{(1)}$, соответствующее слагаемое имеет следующий вид
	\begin{align*}
	B_{n}^{(0)}\left(v_{n}^{(0)} + \xi_{n}, \cgy{0}{1}{0}{1}{0}{\mu(q_{n})}\right),
	\end{align*}
	то есть единицу заряда могло получить каждое новое и разряженное сообщение. Третье слагаемое
	\begin{align*}
	B_{n}^{(i+1)}\left(v_{n}^{(i+1)}, \cgy{p_{i+1}}{1}{0}{\widehat{p}}{0}{1}\right)
	\end{align*}
	равно количеству сообщений, заряженных на $i+1$ ячейку, которые потеряли заряд в следствии саморазрядки в интервале (\textit{\romannumeral 2}). Последнее слагаемое
	\begin{align*}
	B_{n}^{(i+1)}\left(v_{n}^{(i+1)}, \cgy{0}{p_{i+1}}{0}{1}{0}{1}\right)\cdot\left(1-I_{p}^{n}\right)
	\end{align*}
	равно количеству сообщений, заряженных на $i+1$ ячейку, которые были переданы на передающий прибор в интервале (\textit{\romannumeral 1}) и потеряли единицу заряда в интервале (\textit{\romannumeral 5}). При этом сообщения остаются в системе только в случае их конфликта.
	
	Заметим, что стохастическая последовательность $X_{n} = \left(q_{n}, v^{(1)}_{n}, v^{(2)}_{n}...\right)$ принимает значения в польском пространстве
	\begin{align}
	\mathfrak{X} = \left\{x = \left(q, v^{(1)}, v^{(2)}...\right) \in \mathbf{Z}_{+}^{\infty} \: : \: \sum_{i=1}^{\infty}v^{(i)} \leq q\right\},
	\label{State_space}
	\end{align}
	и образует цепь Маркова. Всюду далее нам удобно будет отождествлять модели и соответствующие им стохастические последовательности, а также шаги цепи и временные слоты работы системы. Будем говорить, что система работает стабильно, если соответствующая ей цепь Маркова сходится к своему стационарному распределению в метрике полной вариации, стартуя из любого начального состояния $x \in \mathfrak{X}$.
	
	Построенная модель (\ref{M}) предполагает наличие у каждого пользователя механизма для хранения неограниченного количества ячеек энергии. В существующих системах с передачей энергии по радиоканалу (см., например, \cite{Example_of_applying_Xun_Zhou}) энергия, передаваемая базовой станцией, накапливается у каждого абонента в своем индивидуальном источнике и далее используется для передачи информации. Однако, каждый индивидуальный источник имеет только одну ячейку для хранения энергии. Таким образом, модель (\ref{M}) отражает работу беспроводных систем, снабженных механизмом энергетической подпитки и саморазрядки, с тем отличием от существующих, что в ней дополнительно предполагается наличие механизма для хранения неограниченного количества ячеек энергии у пользователей сети. В параграфе 5 мы покажем, что рассматриваемая нами модель является обобщением моделей, соответствующих упомянутым беспроводным системам.
	
	Сформулируем основной результат данной работы. Заметим, что без ограничения общности $\lambda < 1$. В противном случае общее количество сообщений в системе неограниченно растет (система нестабильна) в силу того, что за один временной слот может быть передано лишь 1 сообщение. Следовательно $\Pb(\xi_{1} = 0) > 0$. Таким образом, цепь Маркова (\ref{M}) за один шаг с положительной вероятностью не меняет состояние, то есть является апериодической. Покажем, что все состояния цепи являются сообщающимися. Рассмотрим два произвольных состояния $x = (q, v^{(1)},...)  \in \mathfrak{X}$ и $\widetilde{x} = (\widetilde{q}, \widetilde{v}^{(1)},...) \in \mathfrak{X}$. Пусть цепь находится в состоянии $x$. Предположим, что $q \geq \widetilde{q}$. Ясно, что нужно не более двух временных слотов, чтобы произвольное сообщение с положительной вероятностью могло покинуть систему. Действительно, в первом временном слоте данное сообщение с положительной вероятностью получит единицу заряда (в интервале (\textit{\romannumeral 4})) и во втором временном слоте сообщение с положительной вероятностью покинет систему (в интервалах (\textit{\romannumeral 1}) и (\textit{\romannumeral 5})). Следовательно с положительной вероятностью $q - \widetilde{q}$ сообщений покинет систему за $2(q-\widetilde{q})$ временных слотов. Предположим, что $q < \widetilde{q}$. В силу того, что $\Pb(\xi_{1} = s) > 0$ для некоторого $s \geq 1$, значит с положительной вероятностью в систему поступит по крайней мере $\widetilde{q} - q$ сообщений за $\lceil (\widetilde{q} - q) / s \rceil$ временных слотов. Следовательно через $\lceil (\widetilde{q} - q) / s \rceil$ временных слотов в системе будет не менее $\widetilde{q}$ сообщений. Учитывая рассуждения выше, можно заключить, что достаточно $\lceil (\widetilde{q} - q) / s \rceil + 2(s-1)$ временных слотов, чтобы общее количество сообщений в системе стало равным $\widetilde{q}$. При этом с положительной вероятностью за любое заданное количество временных слотов общее количество сообщений в системе не изменится (в следствии конфликтов/пустых слотов). Также каждое сообщение может получить или потерять единицу заряда в каждом временном слоте (в интервалах (\textit{\romannumeral 2}), (\textit{\romannumeral 4}) и (\textit{\romannumeral 5})) с положительной вероятностью. Значит с положительной вероятностью за некоторое количество временных слотов общее количество сообщений в системе не изменится, а также для любого $i \geq 1$ количество сообщений, заряженных на $i$ ячеек, будет равно $\widetilde{v}^{(i)}$. Таким образом, можно утверждать, что все состояния цепи являются сообщающимися. Следовательно, для определения пропускной способности системы, достаточно показать, что цепь Маркова (\ref{M}) положительно возвратна в некоторое ограниченное множество, чему и посвящена большая часть данной работы.
	
	Перейдем к рассмотрению основной теоремы, доказательство которой основано на утверждениях, сформулированных в Приложении (см. работы \cite{Foss_original}, \cite{Foss_theorem_for_instability} и \cite{Foss_Konstantinopolous}). Всюду далее мы будем использовать следующие обозначения:
	\begin{gather*}
	\Pb{}_{x}(\cdot) = \Pb(\cdot \:|\: X_{0} = x), \quad
	\E{}_{x}(\cdot) = \E(\cdot \:|\: X_{0} = x),\\
	\norm{x}_{l_{1}} = \norm{x} = q +  \sum_{i=1}^{\infty}v^{(i)}, \quad
	p^{*} = \frac{1-p(1-\widehat{p})}{1-p}.
	\end{gather*}
	
	\begin{repeated_theorem}
		Если $\mu(q)$ имеет следующий вид
		\begin{align*}
		\mu(q) = \begin{cases}
		\min(cp^{*}/q, 1), & q \in \mathbb{N}\\
		1, & q = 0
		\end{cases},
		\end{align*}
		где $c>0$, то система (\ref{M}) стабильна при входной интенсивности $\lambda < ce^{-c}$ и нестабильна при $\lambda > ce^{-c}$.
	\end{repeated_theorem}
	Заметим, что при $c = 1$ мы получим максимально допустимую область стабильности системы, то есть $\lambda < e^{-1}$.
	
	\section{Случай единичной вместимости}
	В работе \cite{Foss_original} было показано, что если для некоторой константы $c > 0$
	\begin{equation}
	\mu(q) = \begin{cases}
	\min(c/q, 1), & q \in \mathbb{N}\\
	1, & q = 0
	\end{cases} 
	\label{mu_definition}
	\end{equation}
	то двумерная цепь Маркова, описывающая систему, в которой у каждого сообщения аккумулятор не подвержен эффекту саморазрядки и имеет только одну ячейку для хранения энергии, стабильна при входной интенсивности $\lambda < ce^{-c}$ и нестабильна при $\lambda > ce^{-c}$. В текущих обозначениях данная цепь Маркова может быть записана в следующем виде
	\[
	\begin{cases}
	q_{n+1} = q_{n} - \mathds{1}\left(B_{n}\left(v^{(1)}_{n}, \cgy{0}{p_{1}}{0}{1}{0}{1}\right) = 1\right) + \xi_{n}, \\
	v^{(1)}_{n+1} = B^{(1)}_{n}\left(v^{(1)}_{n}, \cgy{p_{1}}{1}{0}{1}{0}{1}\right) + B^{(0)}_{n}\left(v^{(0)}_{n} + \xi_{n}, \cgy{0}{1}{0}{1}{0}{\mu(q_{n})}\right)
	\end{cases}
	\tag{$M_{1}^{old}$}
	\label{M0'}
	\]
	
	Если в модели (\ref{M}) положить $v^{(i)}_{n} \equiv 0$ для всех $i \geq 2$, $n \geq 0$, то получим следующую модель
	\[
	\begin{cases}
	q_{n+1} = q_{n} - \mathds{1}\left(B^{(1)}_{n}\left(v^{(1)}_{n}, \cgy{0}{p_{1}}{0}{1}{0}{1}\right) = 1\right) + \xi_{n}, \\
	v^{(1)}_{n+1} = B^{(1)}_{n}\left(v^{(1)}_{n}, \cgy{p_{1}}{1}{\widehat{p}}{1}{0}{1}\right) + B^{(0)}_{n}\left(v^{(0)}_{n} + \xi_{n}, \cgy{0}{1}{0}{1}{0}{\mu(q_{n})}\right)
	\end{cases}
	\tag{$M_{1}$}
	\label{ms}
	\]
	
	Мы будем использовать запись $z(\text{\textasteriskcentered{}})$, чтобы указать, что символ $z$ относится к модели $\text{\textasteriskcentered{}} \in \{\text{\ref{M0'}}, \text{\ref{ms}}\}$, если из контекста это не ясно. Предположим, что цепи Маркова (\ref{M0'}) и (\ref{ms}) стартуют из одного начального состояния, то есть $q_{0}(\text{\ref{ms}}) = q_{0}(\text{\ref{M0'}})$ и $v_{0}^{(1)}(\text{\ref{ms}}) = v_{0}^{(1)}(\text{\ref{M0'}})$. Можно заметить, что в конце первого временного слота выполняются следующие соотношения
	\begin{align}
	v^{(1)}_{1}(\text{\ref{ms}}) \leq v^{(1)}_{1}(\text{\ref{M0'}}) \text{, } q_{1}(\text{\ref{ms}}) = q_{1}(\text{\ref{M0'}}) \text{ п.н.},
	\label{coupling_consequence}
	\end{align}
	так как в модели (\ref{ms}) присутствует эффект саморазрядки.
	
	В работе \cite{Foss_original} для доказательства стабильности цепи (\ref{M0'}) используется обобщенный критерий Фостера (см. Приложения, утверждение 2). Пусть пробная функция $L(x) = q + v^{(1)}$, а функция $g_{R, k}(x)$ -- ступенчатая, такая что
	\begin{align}
	g_{R, k}(x) = \begin{cases}
	1, & v^{(1)} > R,\\
	k, & v^{(1)} \leq R.
	\end{cases}
	\label{step_function_g_stab}
	\end{align}
	Значение $R > 0$ выбирают так, чтобы, при $v_{0}^{(1)} > R$ и произвольном значении $q_{0}$, снос цепи был отрицателен за один шаг. Значение $k \in \mathbf{Z}_{+}$ выбирают таким, чтобы, при достаточно большом $q_{0} \geq \widetilde{q}$, снос цепи был отрицателен за $k$ шагов. Таким образом, внутри компактного множества $\{x \: | \: L(x) \leq \widetilde{q} + R\}$ снос цепи ограничен, а вне -- отрицателен.
	
	Для доказательства нестабильности цепи (\ref{M0'}) в работе \cite{Foss_original} используется схожий метод (см. Приложения, утверждение 3) с пробной функцией Ляпунова $\widetilde{L}(x) = q$ и ступенчатой функцией $g_{\widetilde{R}, \widetilde{k}}(x)$. Значение $\widetilde{R} > 0$ выбирают так, чтобы, при $v_{0}^{(1)} > \widetilde{R}$ и произвольном значении $q_{0}$, снос цепи был положителен за один шаг. Значение $\widetilde{k} \in \mathbf{Z}_{+}$ выбирают таким, чтобы, при $v_{0}^{(1)} \leq \widetilde{R}$ и достаточно большом $q_{0} \geq \widehat{q}$, снос цепи был положителен за $\widetilde{k}$ шагов. Таким образом, вне множества $\{x \: | \: \widetilde{L}(x) \leq \widehat{q}\:\}$ снос цепи (\ref{M0'}) положителен.
	
	В доказательстве следующей вспомогательной теоремы мы будем использовать константы $R$ и $\widetilde{R}$ из рассуждений выше.
	\begin{repeated_theorem}
		Если $\mu(q)$ имеет следующий вид
		\begin{align*}
		\mu(q) = \begin{cases}
		\min(cp^{*}/q, 1), & q \in \mathbb{N}\\
		1, & q = 0
		\end{cases},
		\end{align*}
		где $c>0$, то система (\ref{ms}) стабильна при входной интенсивности $\lambda < ce^{-c}$ и нестабильна при $\lambda > ce^{-c}$.
	\end{repeated_theorem}
	\begin{proof}
		Начнем с доказательства стабильности цепи (\ref{ms}). Выберем пробную функцию $L(x) = q + v^{(1)}$ и функцию $g_{R, k}(x)$, которая определена в (\ref{step_function_g_stab}). Из соотношений (\ref{coupling_consequence}) получим
		\begin{align*}
		\E{}_{x}L(X_{1}(\text{\ref{ms}})) \leq \E{}_{x}L(X_{1}(\text{\ref{M0'}})) \text{ для всех } x \in \mathfrak{X}.
		\end{align*}
		Следовательно, снос цепи (\ref{ms}) за один шаг будет отрицательным в области, где отрицателен снос цепи (\ref{M0'}), то есть при $v^{(1)}_{0}(\text{\ref{M0'}}) > R$. Таким образом, для доказательства стабильности достаточно найти подходящее значение $k \in \mathbf{Z}_{+}$ такое, что снос цепи (\ref{ms}) становится отрицательным за $k$ шагов, стартуя из начального состояния $x$, при котором $v^{(1)}_{0}(\text{\ref{ms}}) \leq R$. Проведем рассуждение в несколько этапов:
		\begin{itemize}
			\item[а)] Покажем, что последовательность $\{v_{n}^{(1)}\}_{n \geq 0}$ мажорируется цепью, имеющей ограниченный снос.\\
			\item[б)] Покажем, что последовательность $\{v_{n}^{(1)}\}_{n \geq 0}$, при достаточно большом значении $q_{0}$, близка к некоторой вспомогательной цепи, сходящейся в метрике полной вариации к случайной величине, имеющей распределение Пуассона.\\
			\item[в)] Подберем $k$ так, чтобы при достаточно большом значении $q_{0}$, снос цепи стал отрицательным за $k$ шагов.
		\end{itemize}
		$ $\\
		а) Пусть $\{Y_{n}\}_{n \geq 0}$ -- последовательность н.о.р. случайных величин, элементы которой не зависят от ${\xi_{n}}$ и имеют следующее распределение
		\begin{equation}
		\Pb(Y_{n} > y) = \underset{q \geq c}{\rm sup}\Pb(B^{(1)}_{1}(q, \cgy{0}{1}{0}{1}{0}{\mu(q)}) > y).
		\label{Y_definition}
		\end{equation}
		Используя неравенство Маркова, можно заключить, что для $y > 0$ и для любого $\alpha > 0$, правая часть равенства (\ref{Y_definition}) не превосходит
		\begin{align*}
		\underset{q \geq c}{\rm sup}\E\frac{e^{\alpha B_{1}(q, c/q)}}{e^{\alpha y}} = \underset{q \geq c}{\rm sup}\Big(1 + (e^{\alpha} - 1)\frac{c}{q}\Big)^{q}e^{-\alpha y} \equiv C_{1}e^{-\alpha y},
		\end{align*}
		где $C_{1}$ конечна, так как $\Big(1 + (e^{\alpha} - 1)\frac{c}{q}\Big)^{q} \xrightarrow{} \exp(c(e^{\alpha}-1)) < \infty$, при $q \xrightarrow{} \infty$.
		\\Таким образом, распределение $Y_{1}$ --- собственное, то есть $\Pb(Y_{n} < \infty) = 1$ для всех $n \geq 0$ и, более того, имеет конечный экспоненциальный момент.
		
		Теперь рассмотрим вспомогательную последовательность
		\begin{align}
		Z_{n}^{(1)} = Y_{n}^{(1)} + \xi_{n}, \:\: W_{n+1}^{(1)} = B_{n}^{(1)}\left(W_{n}^{(1)}, \cgy{p_{1}}{1}{\widehat{p}}{1}{0}{1}\right) + Z_{n}^{(1)},\:\:  W_{0}^{(1)}=v_{0}^{(1)}.
		\label{auxilarry_chain_for_bounds}
		\end{align}
		Из свойств (IV) и (V) утверждения 1 (см. Приложения)
		
		\begin{equation}
		\E\left(v_{n}^{(1)}\:|\:v_{0}^{(1)}\right) \leq \E\left(W_{n}^{(1)}\:|\:W_{0}^{(1)}\right) \leq v_{0}^{(1)} + C^{(1)},
		\label{v_estimation}
		\end{equation}
		где\\
		\begin{equation*}
		C^{(1)} = \frac{E(Y_{1} + \xi_{1})}{1-p(\:1-\widehat{p}\:)} = \frac{EY_{1} + \lambda}{1-p(\:1-\widehat{p}\:)}.
		\end{equation*}
		\\
		
		б) Рассмотрим вспомогательную последовательность 
		\begin{equation}
		\widetilde{V}_{n+1} = B^{(1)}_{n}\left(\widetilde{V}_{n}, \cgy{p_{1}}{1}{\widehat{p}}{1}{0}{1}\right) + \eta_{n},
		\label{auxiliary_chain}
		\end{equation}
		где $\{\eta_{n}\}_{n \geq 0}$ --- семейство н.о.р. случайных величин с распределением Пуассона с параметром $cp^{*}$. Используя (III) и (VI) пункты утверждения 1 (см. Приложения), можем заключить, что последовательность $\widetilde{V}_{n}$ сходится к распределению Пуассона с параметром $cp^{*}/(1-p(1-\widehat{p})) = c/(1-p)$ в метрике полной вариации. Тогда, по определению, мы можем выбрать $l \geq 0$ так, что для всех $n \geq l$ 
		\begin{equation}
		\underset{\rm \widetilde{V}_{0} \leq R}{\rm sup}\left|\Pb{}_{x}\left(B^{(1)}_{n}\left(\widetilde{V}_{n}, \cgy{0}{p_{1}}{0}{1}{0}{1}\right) = 1\right) - ce^{-c}\right| < \delta/2,
		\label{poison_theorem_metrics}
		\end{equation}
		где $\delta > 0$ такая, что $\lambda + \delta < ce^{-c}$. Очевидно, что для любого значения $k$ можно выбрать константу $C$ так, что вероятность события
		\begin{equation*}
		A_{1}(k, C) = \left\{W_{n}^{(1)} \leq C \:\: \text{для всех} \:\: 0 \leq n \leq k\right\}
		\end{equation*}
		не меньше, чем $1 - \delta/2$.
		По известной теореме Пуассона мы можем выбрать $\widetilde{q}$ так, что для любого фиксированного $n$, при $q_{n} \geq \widetilde{q}$, расстояние между $B^{(1)}_{n}\left(q_{n} - v_{n}^{(1)} + \xi_{n}, \cgy{0}{1}{0}{1}{0}{\mu(q_{n})}\right)$ и распределением Пуассона с параметром $cp^{*}$ не превосходит $\delta/2$ в метрике полной вариации равномерно по $v_{n}^{(1)} \in (0, 1, ..., C)$. Более того, мы можем считать, что
		\fontsize{9.5}{10}\selectfont
		\begin{align*}
		\Pb{}_{x}\left(\left\{B^{(1)}_{n}\left(q_{n} - v_{n}^{(1)} + \xi_{n}, \cgy{0}{1}{0}{1}{0}{\mu(q_{n})}\right) = \eta_{n},\: \forall n \in \{l, ..., k\}\right\} \cap A_{1}(k, C)\right) \geq 1 - \delta/2.
		\end{align*}
		\normalsize
		Следовательно
		\begin{align}
		\Pb{}_{x}\left(\{v_{n}^{(1)} = \widetilde{V}_{n},\: \forall n \in \{l,..., k\}\} \cap A_{1}(k, C)\right) \geq 1 - \delta/2.
		\label{charged_poissonised}
		\end{align}
		\\
		
		в) Выберем $k > l$ так, что
		\begin{align}
		-\varepsilon = k\lambda + C^{(1)} - (k-l)(ce^{-c}-\delta) \notag\\= k(\lambda - (ce^{-c} - \delta)) + l(ce^{-c} - \delta) + C^{(1)} < 0.
		\label{stability_epsilon_define}
		\end{align}
		Заметим, что, в силу (\ref{poison_theorem_metrics}) и (\ref{charged_poissonised}), при всех $n \in \{l, l+1,..., k\}$, справедливо неравенство
		\begin{align}
		\underset{v_{0}^{(1)} \leq R}{\sup}\left|\Pb{}_{x}\left(B^{(1)}_{n}\left(v^{(1)}_{n}, \cgy{0}{p_{1}}{0}{1}{0}{1}\right) = 1\right) - ce^{-c}\right| < \delta.
		\label{succes_transmission_poisson}
		\end{align}
		Наконец, из (\ref{stability_epsilon_define}) и (\ref{succes_transmission_poisson}), получим
		\begin{gather*}
		\E{}_{x}(L(X_{k}) - L(x)) = \E{}_{x}(q_{k} - q_{0}) + \E{}_{x}(v_{k} - v_{0}) \notag \\\leq  k\lambda - \sum_{i=l+1}^{k}\Pb{}_{x}\left(B_{i}^{(1)}\left(v_{i}^{(1)}, \cgy{0}{p_{1}}{0}{1}{0}{1}\right) = 1\right) + C^{(1)} \\< k\lambda - \sum_{i=l+1}^{k}(ce^{-c} - \delta) + C^{(1)} = k\lambda - (k - l)(ce^{-c} - \delta) + C^{(1)} < -\varepsilon.
		\end{gather*}
		\\
		
		Для доказательства нестабильности цепи (\ref{ms}), мы будем использовать утверждение 3, сформулированное в Приложении. Пусть $n_{k}$ --- некоторая последовательность натуральных чисел такая, что $n_{k} \xrightarrow{} \infty$, при $k \xrightarrow{} \infty$, а также $|n_{k+1}-n_{k}| \leq C < \infty$ для любого $k \geq 0$. В силу неравенства
		\begin{align}
		q_{n} \geq q_{n_{k}} - C \:\: \text{п.н. для всех} \:\: n_{k} \leq n  \leq n_{k+1} \:\:\text{и}\:\: k \geq 0,
		\label{q_subseq_inequality}
		\end{align}
		можно утверждать, что, если $q_{n_{k}} \xrightarrow{} \infty$, при $k \xrightarrow{} \infty$, то $q_{n} \xrightarrow{} \infty$, при $n \xrightarrow{} \infty$. Таким образом, положим $\widetilde{L}(x) = q$ и $g(x) := g_{\widetilde{k}, \widetilde{R}}(x)$, где константы $\widetilde{k}$, $\widetilde{R}$ будут заданы далее подходящим образом. Следовательно, при заданных в условии утверждения 3 ограничениях, достаточно показать, что марковская цепь имеет положительный снос
		\begin{equation}
		\E{}_{x}(\Delta_{\widetilde{g}(x)}\mathds{1}(\Delta_{\widetilde{g}(x)} \leq M)) \geq \widetilde{\varepsilon},
		\label{instab_cond_1}
		\end{equation}
		где $\Delta_{\widetilde{g}(x)} = \widetilde{L},(X_{\widetilde{g}(x)}) - \widetilde{L}(x)$ и семейство случайных величин
		\begin{equation}
		(\Delta^{-}_{\widetilde{g}(x)})^{2} = (\min(0, \Delta_{\widetilde{g}(x)}))^{2}
		\label{instab_cond_2}
		\end{equation}
		равномерно интегрируемо. Тогда из условий (\ref{q_subseq_inequality}), (\ref{instab_cond_1}), (\ref{instab_cond_2}) и из утверждения 3, будет следовать
		\begin{equation*}
		\Pb{}_{x}(\widetilde{L}(X_{n}) \xrightarrow{} \infty) = 1.
		\end{equation*}
		В силу неравенства (\ref{q_subseq_inequality}), можно утверждать, что, при выбранных функциях $\widetilde{L}$ и $\widetilde{g}$, верно $0 \geq \Delta^{-}_{\widetilde{g}(x)} \geq -\widetilde{k}$ п.н. и, таким образом, условие (\ref{instab_cond_2}) выполнено. В силу того, что $\E\xi_{1} = \lambda < 1$, условие (\ref{instab_cond_1}) эквивалентно
		\begin{equation}
		\E{}_{x}(\Delta_{\widetilde{g}(x)}) \geq \varepsilon',
		\label{instab_cond_3}
		\end{equation}
		для некоторого $\varepsilon' > 0$. Следовательно, для доказательства нестабильности, нужно показать, что выполняется неравенство (\ref{instab_cond_3}).
		
		Дальнейшие рассуждения проведем аналогично доказательству нестабильности цепи (\ref{M0'}). В силу (\ref{coupling_consequence}) и рассуждений, проведенных для случая нестабильности цепи (\ref{M0'}), можно утверждать, что
		\begin{align*}
		\widetilde{R}(\text{\ref{ms}}) = \widetilde{R}(\text{\ref{M0'}})
		\end{align*}
		
		Таким образом, при $v^{(1)}_{0} > \widetilde{R}$
		\begin{equation*}
		\E{}_{x}(q_{1} - q_{0}) > 0.
		\end{equation*}
		Чтобы завершить доказательство нестабильности цепи (\ref{ms}), достаточно выбрать некоторый момент времени $\widetilde{k}$, когда снос цепи становится положительным. Для этого сначала заметим, что из рассуждений, проведенных при доказательстве стабильности цепи справедливо соотношение (\ref{succes_transmission_poisson}). Таким образом, существует некоторый момент времени $l$, когда вспомогательная цепь достаточно близка к своему стационарному распределению. Выберем значение $\widetilde{k}$ так, что выполняется следующее неравенство
		\begin{align}
		\varepsilon' = \widetilde{k}\lambda - l -  (\widetilde{k}-l)(ce^{-c} + \delta) \notag\\= \widetilde{k}(\lambda - (ce^{-c} + \delta)) + l(ce^{-c} - \delta) - l > 0,
		\label{instability_epsilon_define}
		\end{align}
		где $\delta$ такая, что
		\begin{align*}
		0 < \delta < \lambda - ce^{-c}.
		\end{align*}
		
		Таким образом, при $q_{0} > \widetilde{q} + \widetilde{k}$ и $v^{(1)}_{0} \leq \widetilde{R}$, получим
		\begin{gather*}
		\E{}_{x}\left(\widetilde{L}(X_{\widetilde{k}}) - \widetilde{L}(x)\right) \geq \widetilde{k}\lambda - l - \sum_{i=l+1}^{\widetilde{k}}\Pb{}_{x}\left(B_{i}^{(1)}\left(v_{i}^{(1)}, \cgy{0}{p_{1}}{0}{1}{0}{1}\right) = 1\right) \notag\\ > \widetilde{k}\lambda - l - \sum_{i=l+1}^{\widetilde{k}}(ce^{-c} + \delta) \notag\\ = \widetilde{k}\lambda - l - (\widetilde{k} - l)(ce^{-c} + \delta) > \varepsilon',
		\end{gather*}
		где $\varepsilon'$ определена в (\ref{instability_epsilon_define}).
	\end{proof}
	
	\section{Случай неограниченной вместимости}
	Для доказательства теоремы 1 мы будем использовать результаты и рассуждения из работы \cite{Rezler_Chebunin}, где мы рассматривали модель (\ref{M}) без эффекта саморазрядки, то есть модель, в которой $\widehat{p}=0$. Обозначим ее через $(M^{old})$. Мы доказали, что ее области стабильности и нестабильности совпадают с соответствующими областями модели (\ref{M0'}). Для доказательства стабильности использовалась пробная функция
	\begin{align}
	L(x) = q + \sum_{i=1}^{\infty}p^{-i/2}v^{(i)}.
	\label{Lyapunov_function}
	\end{align}
	Мы использовали утверждение 2 (Обобщенный критерий Фостера) с функцией $g(x)$ следующего вида
	\begin{align*}
	g(x) = \begin{cases}
	1,\: L(x) - q > R\\
	k,\: L(x) - q \leq R
	\end{cases}
	\end{align*}
	Значение $R$ определяется в процессе доказательства так, что снос цепи, стартующей из множества
	\begin{align*}
	\left\{x \in \mathfrak{X} \: | \: L(x) - q > R\right\},
	\end{align*}
	отрицателен за один шаг. Значение $k$ определяет количество шагов необходимых, чтобы, при достаточно большом значении $q_{0} \geq \widetilde{q}$, в дополнении к упомянутому множеству, снос цепи становился отрицательным. В итоге, мы имеем множество 
	\begin{align*}
	\{x \in \mathfrak{X} \: | \: L(x) \leq \widetilde{q} + R\},
	\end{align*}
	внутри которого снос цепи ограничен, а вне --- отрицателен. Для доказательства нестабильности цепи $(M^{old})$ мы использовали утверждение 3 (см. Приложения) с функцией Ляпунова
	\begin{align}
	\widetilde{L}(x) = q
	\label{Lyapunov_function_instability_M}
	\end{align}
	и ступенчатой функцией
	\begin{align*}
	g(x) = \begin{cases}
	1, & x \in H,\\
	\widetilde{k}, & x \in \stcomp{H},
	\end{cases}
	\end{align*}
	где $H = \{x \in \mathfrak{X} \:\: | \:\: \Pb_{x}(I_{p}^{0} = 1) < ce^{-c}\}$. Множество $H$ таково, что снос цепи, стартующей из него, положителен за один шаг. Значение $\widetilde{k}$ выбирают так, чтобы, при $x \in \stcomp{H}$ и достаточно большом $q_{0} \geq \widehat{q}$, снос цепи был положителен за $\widetilde{k}$ шагов. Таким образом, вне множества $\{x \in \mathfrak{X} \:\: | \:\: \widetilde{L}(x) \leq \widehat{q}\:\}$ снос цепи $(M^{old})$ положителен.
	
	Далее полагаем, что цепь $(M^{old})$ стартует из множества
	\begin{align*}
	\stcomp{H} \cup \left\{x \in \mathfrak{X} \: | \: L(x) - q \leq R\right\}.
	\end{align*}
	В этом случае общее количество изначально заряженных сообщений ограничено, так как либо ограничен изначальный суммарный заряд в системе, либо ограничена вероятность конфлитка в первом временном слоте.
	
	Остальные рассуждения были посвящены сведению рассматриваемой цепи $(M^{old})$ к ее двумерному частному случаю (\ref{M0'}).
	Во-первых, мы показали, что снос сообщений, заряженных более чем на одну ячейку, может быть сколь угодно близким к 0 путем выбора достаточно большого значения $q_{0}$. Во-вторых, мы определили некоторый момент времени, после которого, при достаточно большом значении $q_{0}$, упомянутые цепи "ведут себя одинаково"$ $ с вероятностью, достаточно близкой к 1, в течение некоторого количества шагов. Таким образом, при достаточно большом значении $q_{0}$, за некоторое количество шагов, снос цепи $(M^{old})$ определяется сносом цепи (\ref{M0'}). 
	
	Проведем аналогичные рассуждения для цепей (\ref{M}) и (\ref{ms}). Основное отличие системы (\ref{M}) от системы $(M^{old})$ заключается в наличии в первой эффекта саморазрядки. Следовательно, если системы стартуют из одного начального состояния, то суммарный заряд всех сообщений в системе (\ref{M}) в конце первого временного слота мажорируется суммарным зарядом всех сообщений в системе $(M^{old})$ в конце первого временного слота. В определении функции $L(x)$ сообщения, имеющие больший заряд, имеют больший вес. Поэтому функция $L(x)$ монотонна по суммарному заряду всех сообщений в системе. Таким образом, снос цепи (\ref{M}) за один шаг мажорируется сносом цепи $(M^{old})$, то есть
	\begin{align*}
	\E{}_{x}\left[L(X_{1}(\text{\ref{M}})) - L(x)\right] \leq \E{}_{x}\left[L(X_{1}(M^{old})) - L(x)\right].
	\end{align*}
	Следовательно, мы можем положить $R(\text{\ref{M}}) = R(M^{old})$. Таким образом, всюду далее будем считать, что 
	\begin{align*}
	L(X_{0}) - q_{0} \leq R.
	\end{align*}
	Более того, так как общее количество сообщений в системе в конце первого временного слота не зависит от наличия в системе эффекта саморазрядки, то
	\begin{align*}
	\E{}_{x}\left[\widetilde{L}(X_{1}(\text{\ref{M}})) - \widetilde{L}(x)\right] = \E{}_{x}\left[\widetilde{L}(X_{1}(M^{old})) - \widetilde{L}(x)\right].
	\end{align*}
	Следовательно, мы можем положить $H(\text{\ref{M}})=H(M^{old})$. Заметим, что найдется такое значение $\widetilde{R}$, что справедливо следующее включение
	\begin{align*}
	\{x \in \mathfrak{X} \:\: | \:\: \norm{v} > \widetilde{R}\} \subseteq H,
	\end{align*}
	так как при большом количестве заряженных сообщений высока вероятность конфликта. Всюду далее будем считать, что
	\begin{align*}
	X_{0}=x \in \stcomp{H} \cup \{x \in \mathfrak{X} \:\: | \:\: L(x)-q \leq R\}.
	\end{align*}
	Перейдем к сведению цепи (\ref{M}) к (\ref{ms}). Покажем, что
	\begin{itemize}
		\item[а)] снос сообщений, заряженных более чем на одну ячейку, стремится к нулю с ростом значения $q_{0}$,
		\\
		\item[б)] при достаточно большом значении $q_{0}$, модели (\ref{M}) и (\ref{ms}) совпадают с вероятностью, сколь угодно близкой к 1.
	\end{itemize}
	$ $\\
	а) Заметим, что $1-I_{p}^{n} \leq 1$. Следовательно
	\begin{gather}
	v_{n+1}^{(i)} \leq B_{n}^{(i)}\left(v_{n}^{(i)}, \cgy{p_{i}}{1}{\widehat{p}}{1}{\mu(q_{n})}{1}\right) + B_{n}^{(i-1)}\left(v_{n}^{(i-1)}, \cgy{p_{i-1}}{1}{\widehat{p}}{1}{0}{\mu(q_{n})}\right)\notag\\ + B_{n}^{(i+1)}\left(v_{n}^{(i+1)}, \cgy{p_{i+1}}{1}{0}{\widehat{p}}{0}{1}\right) + B_{n}^{(i+1)}\left(v_{n}^{(i+1)}, \cgy{0}{p_{i+1}}{0}{1}{0}{1}\right).
	\label{Always_collision}
	\end{gather}
	Рассмотрим снос цепи за $n$ шагов. Воспользуемся неравенством (\ref{Always_collision}) и внесем математическое ожидание под знак суммы, так как $x \in \mathfrak{X}$ и $\norm{v_{n}} \leq q_{n} < \infty \text{ п.н.}$,
	\fontsize{9.5}{10}\selectfont
	\begin{gather*}
	\E{}_{x}\Bigg[\sum_{i=2}^{\infty}p^{-i/2}(v_{n}^{(i)} - v_{0}^{(i)})\Bigg] = \E{}_{x}\Bigg[\sum_{i=2}^{\infty}p^{-i/2}\E\left(v_{n}^{(i)} - v_{0}^{(i)} \:\Big|\: v^{(i)}_{n-1}\right)\Bigg] \\\notag\leq \E{}_{x}\Bigg[\sum_{i=2}^{\infty}p^{-i/2}\Big(p^{i}(1 - \widehat{p}\:)(1 - \mu(q_{n-1}))v_{n-1}^{(i)} + p^{i-1}(1-\widehat{p}\:)\mu(q_{n-1})v_{n-1}^{(i-1)} \\+ p^{i+1}\widehat{p}v_{n-1}^{(i+1)} + (1-p^{i+1})v_{n-1}^{(i+1)}\Big) -  \sum_{i=2}^{\infty}p^{-i/2}v_{0}^{(i)}\Bigg] = 
	\E{}_{x}\Bigg[\sum_{i=2}^{\infty}p^{-i/2}\left(v_{n-1}^{(i)} - v_{0}^{(i)}\right) \\- \sum_{i=2}^{\infty}p^{-i/2}(1 - p^{i})v_{n-1}^{(i)} + \sum_{i=2}^{\infty}p^{-i/2}(1 - p^{i+1})v_{n-1}^{(i+1)} \\- \sum_{i=2}^{\infty}p^{i/2}\widehat{p}v_{n-1}^{(i)} + \sum_{i=2}^{\infty}p^{i/2+1}\widehat{p}v_{n-1}^{(i+1)} \\+ \sum_{i=2}^{\infty}p^{i/2-1}(1-\widehat{p})v_{n-1}^{(i-1)}\mu(q_{n-1}) - \sum_{i=2}^{\infty}p^{i/2}(1-\widehat{p})v_{n-1}^{(i)}\mu(q_{n-1})\Bigg].
	\end{gather*}
	\normalsize
	Заметим, что
	\begin{gather*}
	- \sum_{i=2}^{\infty}p^{-i/2}(1 - p^{i})v_{n-1}^{(i)} + \sum_{i=2}^{\infty}p^{-i/2}(1 - p^{i+1})v_{n-1}^{(i+1)} \leq 0,\\
	- \sum_{i=2}^{\infty}p^{i/2}\widehat{p}v_{n-1}^{(i)} + \sum_{i=2}^{\infty}p^{i/2+1}\widehat{p}v_{n-1}^{(i+1)} \leq 0.
	\end{gather*}
	Следовательно, выполняется неравенство
	\begin{align*}
	\E{}_{x}\Bigg[\sum_{i=2}^{\infty}p^{-i/2}(v_{n}^{(i)} - v_{0}^{(i)})\Bigg] \leq \E{}_{x}\left[\sum_{i=2}^{\infty}p^{-i/2}\left(v_{n-1}^{(i)} - v_{0}^{(i)}\right)\right] + \sum_{i=1}^{\infty}\E{}_{x}v_{n-1}^{(i)}\mu(q_{n-1}).
	\end{align*}
	Таким образом, получим следующую оценку
	\begin{align}
	\E{}_{x}\left[\sum_{i=2}^{\infty}p^{-i/2}\left(v_{n}^{(i)} - v_{0}^{(i)}\right)\right] \leq \E{}_{x}\sum_{l=0}^{n-1}\mu(q_{l})\sum_{i=1}^{\infty}v_{l}^{(i)}.
	\label{Drift_inequality_i2}
	\end{align}
	Заметим, что за один временной слот, скажем $(l+1)$-ый, общее количество заряженных сообщений в среднем вырастет не более чем на $cp^{*} + \lambda\mu(q_{l})$. В начальном состоянии цепи общее количество заряженных сообщений не превышает $\max(R, \widetilde{R})$, следовательно за $n$ шагов общее количество заряженных сообщений не превысит
	\begin{align*}
	\max(R, \widetilde{R}) + (cp^{*} + \lambda\mu(q_{0})) + (cp^{*} + \lambda\mu(q_{1})) + ... + (cp^{*} + \lambda\mu(q_{n-1})).
	\end{align*}
	За один временной слот из системы может уйти не более одного сообщения, поэтому $q_{l} \geq q_{l-1}-1$ п.н. Другими словами, справедлива следующая оценка
	\begin{align*}
	\mu(q_{l}) \leq cp^{*}/(q_{0}-n+1) \text{ п.н.}, \text{ при } l \leq n-1 \text{ и } q_{0} \geq n.
	\end{align*}
	Таким образом, правая часть неравенства (\ref{Drift_inequality_i2}) не превосходит
	\begin{align*}
	\frac{cp^{*}n\Big(\max(R, \widetilde{R}) + n\big(cp^{*} + \lambda\mu(q_{0}-n+1)\big)\Big)}{q_{0}-n+1}.
	\end{align*}
	Следовательно, с ростом значения $q_{0}$ (при фиксированном $n$) снос сообщений, заряженных более чем на одну ячейку, стремится к нулю.
	\\
	$ $
	\\
	б) Рассмотрим следующие события
	\begin{gather*}
	A_{0}(n) = \big\{\text{после ($n-1$)-ого шага все изначально заряженные сообщения}\\ \text{потеряли весь свой заряд или покинули систему}\big\},\\
	A_{2}(q_{0}, k) = \Big\{B^{(i)}_{n}\Big(v^{(i)}_{n}, \cgy{p_{i}}{1}{\widehat{p}}{1}{0}{\mu(q_{n})}\Big) = 0 \\\:\:\text{для всех} \:\: i \geq 1 \:\: \text{и} \:\: 0 \leq n \leq k\Big\}.
	\end{gather*}
	Заметим, что, при некоторых $k$ и $n_{0} \leq k$, внутри события $A_{0}(n_{0}) \cap A_{2}(q_{0}, k)$ цепь (\ref{M}) ведет себя как цепь (\ref{ms}) на временном отрезке $[n_{0}, k]$, так как начальные сообщения до момента времени $n_{0}$ потеряли весь свой заряд и за $k$ шагов не было заряжено на более чем одно деление ни одного сообщения. Следовательно, с момента времени $n_{0}$ по момент времени $k$ в системе не было сообщений, заряженных более чем на одно деление. Таким образом, для доказательства данного пункта необходимо показать, что
	\begin{align}
	\Pb{}_{x}\big(A_{0}(n_{0}) \cap A_{2}(q_{0}, k)\big) \xrightarrow{} 1, \text{ при } q_{0} \xrightarrow{} \infty.
	\label{Merging_chains}
	\end{align}
	Покажем, что заряженные на одну ячейку сообщения $\{v^{(1)}_{n}\}_{n \geq 0}$ ограничены эргодической последовательностью
	\begin{align*}
	\{W_{n}^{(1)} + \max(R, \widetilde{R})\}_{n \geq 0}, \:\: W_{0}^{(1)} = v^{(1)}_{0}(\text{\ref{M}}),
	\end{align*}
	где последовательность $\{W_{n}^{(1)}\}_{n \geq 0}$ определена в (\ref{auxilarry_chain_for_bounds}). Для этого достаточно заметить, что вследствие конфликтов и саморазрядок сообщений, заряженных на 2 и более ячейки, общее количество сообщений, заряженных на одну ячейку, увеличится не более чем на $\max(R, \widetilde{R})$. Тогда ясно, что вероятность события
	\begin{align*}
	A_{1}(C, k) = \{v_{n}^{(1)} \leq C \text{ для всех } 0 \leq n \leq k\}
	\end{align*}
	при любом фиксированном $k$ и достаточно большом $C = C(k)$ сколь угодно близка к 1. Выберем некоторое произвольное значение $0 < \delta < 1$ и параметры $C$, $k$ такие, что
	\begin{align*}
	\Pb{}_{x}\big(A_{1}(C, k)\big) \geq 1 - \delta/4.
	\end{align*}
	Заметим, что верна следующая цепочка неравенств
	\begin{align*}
	\Pb{}_{x}\big(A_{2}(q_{0}, k) \cap A_{1}(C, k)\big) \geq \Pb{}_{x}\big(A_{2}(q_{0}, k) \: | \: A_{1}(C, k)\big)(1 - \delta/4) \\\geq \Pb{}_{x}\left(\left\{B^{(1)}_{n}(\max(R, \widetilde{R}) + C, \cgy{0}{1}{0}{1}{0}{\mu(q_{n})}) = 0 \:\: \text{для всех} \:\: 0 \leq n \leq k \right\}\right)(1 - \delta/4), 
	\end{align*}
	где последнее неравенство справедливо в силу того, что в начальном состоянии не более, чем $\max(R, \widetilde{R})$ заряженных сообщений, а также вероятность подзарядки одного сообщения в произвольный момент времени не зависит от заряда данного сообщения. Ясно, что выражение сверху больше, чем
	\begin{align*}
	\big(1 - \mu(q_{0} - k)\big)^{(\max(R, \widetilde{R}) + C)k}(1 - \delta/4).
	\end{align*}
	Таким образом, путем выбора достаточно большого значения $q_{0}$, получим
	\begin{align*}
	\Pb{}_{x}\big(A_{2}(q_{0}, k) \cap A_{1}(C, k)\big) \geq 1 - \delta/2.
	\end{align*}
	Осталось заметить, что с ростом $n_{0}$, вероятность события $A_{0}(n_{0})$ стремится к 1. Действительно, в случае $x \in \{x \in \mathfrak{X} \:\: | \:\: L(x)-q \leq R\}$ утверждение очевидно, так как начальный суммарный заряд в системе ограничен. Значит, существует некоторое заданное количество временных слотов $n_{1}$, необходимых, чтобы изначально заряженные сообщения потеряли весь заряд с вероятностью, сколь угодно близкой к 1. В случае $x \in \stcomp{H}$ можно заметить, что начальный заряд каждого сообщения, за исключением возможно лишь одного, не превышает некоторого значения $b = b(p)$. Таким образом, существует некоторое заданное количество временных слотов $n_{2}$, необходимых для того, чтобы с вероятностью, сколь угодно близкой к 1, одно сообщение, изначально заряженное (много) более чем на $b$ ячеек, покинуло систему и $\widetilde{R}-1$ сообщений потеряли заряд. Пусть $n_{0} = \max(n_{1}, n_{2})$, тогда
	\begin{align*}
	\Pb{}_{x}(A_{0}(n_{0})) \geq 1 - \delta/2, \:\: \text{где } x \in \stcomp{H} \cup \{x \in \mathfrak{X} \:\: | \:\: L(x)-q \leq R\}.
	\end{align*}
	Следовательно выполняется следующая цепочка неравенств
	\begin{align*}
	\Pb{}_{x}\big(A_{0}(n_{0}) \cap A_{2}(q_{0}, k)\big) \geq \Pb{}_{x}\big(A_{0}(n_{0}) \cap A_{1}(C, k) \cap A_{2}(q_{0}, k)\big) \geq 1 - \delta.
	\end{align*}
	В силу произвольности значения $\delta$, (\ref{Merging_chains}) выполнено.\\
	
	Таким образом, снос цепи (\ref{M}) определяется сносом цепи (\ref{ms}). Следовательно, области стабильности и нестабильности цепи (\ref{M}) совпадают с соответствующими областями цепи (\ref{ms}).
	
	\section{Замечание об ограниченной вместимости}
	Представляют интерес модели, в которых у каждого пользователя предполагается наличие батарейки лишь с ограниченным числом ячеек для хранения энергии. При этом модель (\ref{M}), в случае наличия батарейки с $m$ ячейками, будет выглядить следующим образом:
	\fontsize{8.5}{10}\selectfont
	\[
	\begin{cases}
	q_{n+1} = q_{n} - I_{p}^{n} + \xi_{n}, \\\\
	v_{n+1}^{(1)} = B_{n}^{(1)}\left(v_{n}^{(1)}, \cgy{p_{1}}{1}{\widehat{p}}{1}{\mu(q_{n})}{1}\right) + B_{n}^{(0)}\left(v_{n}^{(0)} + \xi_{n}, \cgy{0}{1}{0}{1}{0}{\mu(q_{n})}\right) \\+ B_{n}^{(2)}\left(v_{n}^{(2)}, \cgy{p_{2}}{1}{0}{\widehat{p}}{0}{1}\:\right) + B_{n}^{(2)}\left(v_{n}^{(2)}, \cgy{0}{p_{2}}{0}{1}{0}{1}\right)\cdot\left(1-I_{p}^{n}\right)\\\\
	v_{n+1}^{(2)} = B_{n}^{(2)}\left(v_{n}^{(2)}, \cgy{p_{2}}{1}{\widehat{p}}{1}{\mu(q_{n})}{1}\right) + B_{n}^{(1)}\left(v_{n}^{(1)}, \cgy{p_{1}}{1}{\widehat{p}}{1}{0}{\mu(q_{n})}\right) \\+ B_{n}^{(3)}\left(v_{n}^{(3)}, \cgy{p_{3}}{1}{0}{\widehat{p}}{0}{1}\:\right) + B_{n}^{(3)}\left(v_{n}^{(3)}, \cgy{0}{p_{3}}{0}{1}{0}{1}\right)\cdot\left(1-I_{p}^{n}\right)\\
	...\\
	v_{n+1}^{(m)} = B_{n}^{(m)}\left(v_{n}^{(m)}, \cgy{p_{m}}{1}{\widehat{p}}{1}{0}{1}\right) + B_{n}^{(m-1)}\left(v_{n}^{(m-1)}, \cgy{p_{m-1}}{1}{\widehat{p}}{1}{0}{\mu(q_{n})}\right)
	\end{cases}
	\tag{\(M_{m}\)}
	\label{Mm}
	\]
	\normalsize
	
	Заметим, что теорема 1 верна и для данной модели. Действительно, аналогично рассуждениям в доказательстве для цепи (\ref{M}), выберем пробные функции (\ref{Lyapunov_function}), (\ref{Lyapunov_function_instability_M}) и покажем, что цепь (\ref{Mm}) сводится к цепи (\ref{M}). Для этого достаточно "запустить"$ $ упомянутые цепи из одного начального состояния и заметить, что из пункта (а) доказательства основной теоремы, снос сообщений, заряженных более чем на $m$ ячеек, стремится к 0 с ростом значения $q_{0}$ и из пункта (б) все сообщения, изначально заряженные более чем на $m$ ячеек потеряют весь заряд или покинут систему с вероятностью, сколь угодно близкой к 1, а также, при достаточно большом значении $q_{0}$, сообщения не будут заряжаться более чем на одну ячейку с вероятностью, сколь угодно близкой к 1. Таким образом, на некотором временном отрезке цепь (\ref{M}) будет "вести себя"$ $ как цепь (\ref{Mm}) с вероятностью, сколь угодно близкой к 1, и снос цепи (\ref{Mm}) будет определяться сносом цепи (\ref{M}).\\
	
	Авторы выражают благодарность за постановку задачи Фоссу С.Г., а также анонимному рецензенту за конструктивные замечания и рекомендации.
	
	\section{Приложения}
	Сформулируем вспомогательные утверждения, используемые при доказательстве основной теоремы. Приведем лемму 1 из работы \cite{Foss_original}. Мы будем далее использовать следующие обозначения
	\begin{gather*}
	D_{n}(k, p) := k - B_{n}(k, 1-p) = \sum_{i=1}^{k}\mathds{1}(U_{n,i} > 1-p),
	\end{gather*}
	где $\{U_{n,i} \: | \: n \in \mathbb{Z}, i \geq 1\}$ семейство независимых равномерно распределенных на отрезке [0, 1] случайных величин. Ясно, что $D_{n}(k, p)$ имеет биномиальное распределение с параметрами $k$ и $p$.
	
	\begin{numbered_theorem}
		Пусть $\{Z_{n}\}_{n \geq 0}$ последовательность н.о.р. неотрицательных целочисленных случайных
		величин с конечным математическим ожиданием $\E{}Z_{0} < \infty$. Предположим, что она не зависит от семейства н.о.р. случайных величин $\{U_{n,i} \: | \: n \in \mathbb{Z}, i \geq 1\}$.
		\\
		\\
		(I) Для любого начального значения $W_{0}$ и для любого параметра $p \in (0, 1)$, последовательность
		\\
		\begin{equation}
		W_{n+1} = W_{n} - B_{n}(W_{n}, 1-p) + Z_{n} \equiv D_{n}(W_{n}, p) + Z_{n}
		\end{equation}
		\quad эргодична.
		\\\\
		(II) Для $m \leq n$ определим случайные величины
		\begin{equation}
		D_{m:n}(k, p) = D_{n}(D_{n-1}(...(D_{m+1}(D_{m}(k, p), p)..., p)
		\end{equation}
		и заметим, что случайная величина $D_{m:n}(k, p)$ имеет биномиальное распределение с
		параметрами $k$ и $p^{n-m+1}$. Тогда стационарная последовательность {$W^{(n)}$}, определенная следующим образом
		\begin{equation}
		W^{(n)} = Z_{n-1} + \sum_{j=1}^{\infty} D_{(n-j):(n-1)}(Z_{n-j-1}, p),
		\label{stationary_solution_of_rec_eq}
		\end{equation}
		имеет конечное математическое ожидание $EW^{(n)} = EZ_{0} / (1-p)$ и образует стационарное решение для рекурсивного уравнения,
		\begin{equation}
		W^{(n+1)} = D_{n}(W^{(n)}, p) + Z_{n}.
		\label{recursive_equation}
		\end{equation}
		(III) Пусть Q --- распределение $W^{(0)}$. Тогда, для любого начального значения $W_{0}$
		\begin{equation}
		\Pb(W_{n} = W^{(n)}) = \Pb(W_{l} = W^{(l)}, \forall l \geq n) \xrightarrow[]{} 1
		\end{equation}
		и, в частности,
		\begin{equation}
		\underset{\rm A \subseteq \mathbf{Z}_{+}}{\rm sup}|\Pb(W_{n} \in A) - Q(A)| \leq \Pb(W_{n} \neq W^{(n)}) \xrightarrow{} 0, \:\: \text{при} \:\: n \xrightarrow{} \infty.
		\end{equation}
		В частности, если $W_{0}$ и $Z_{0}$ имеют конечные экспоненциальные моменты, то
		\begin{equation}
		\Pb(W_{n} \neq W^{(n)}) \leq K_{1}e^{-K_{2}n},
		\end{equation}
		для некоторых $K_{1}, K_{2} > 0$ и для всех $N \geq 0$.
		\\
		(IV) Для любого $n \geq 0$,
		\begin{equation}
		W_{n} \leq W_{0} + W^{(n)} \:\: \text{п.н.}
		\end{equation}
		и
		\begin{equation}
		\E{}W_{n} \leq \E{}W_{0} + \frac{\E{}Z_{0}}{1-p}.
		\end{equation}
		(V) Пусть $\widetilde{Z}_{n}$ --- любая другая последовательность независимых неотрицательных целочисленных случайных величин, таких что $0 \leq \widetilde{Z}_{n} \leq Z_{n}$ п.н., для всех $n$. Рассмотрим рекурсию
		\begin{equation}
		\widetilde{W}_{n+1} = D_{n}(\widetilde{W}_{n}, p) + \widetilde{Z}_{n}
		\end{equation}
		с целочисленным начальным значением $0 \leq \widetilde{W}_{0} \leq W_{0}$. Тогда
		\begin{equation}
		\widetilde{W}_{n} \leq W_{n} \:\: \text{п.н.}, \:\: \text{для всех} \:\: n \geq 0.
		\end{equation}
		(VI) В частности, если $Z_{0}$ пуассоновская случайная величина с параметром $c$, то каждый $W^{(n)}$ имеет пуассоновское распределение с параметром $c/(1-p)$.
	\end{numbered_theorem}
	Сформулируем второе вспомогательное утверждение из работы \text{\cite{Foss_Konstantinopolous}}. Пусть $X_{n}$ --- однородная по времени цепь Маркова, принимающая значения в некотором польском пространстве $\mathfrak{X}$. Пусть $L:\mathfrak{X} \to \mathbb{R}_{+}$ --- некоторая измеримая функция Ляпунова. Пусть $g:\mathfrak{X} \to \mathbb{N}$ и $h:\mathfrak{X} \to \mathbb{R}$ --- измеримые функции такие, что:\\
	1) $h$ ограничена снизу: $\underset{x \in \mathfrak{X}}{\inf}h(x) > -\infty$;\\
	2) $h$ асимптотически положительна: $\underset{K > 0}{\sup}$ $\underset{L(x) > K}{\inf}h(x) > 0$;\\
	3) $g$ локально ограничена сверху: $\underset{L(x) \leq N}{\sup}g(x) < \infty$ для всех $N \geq 0$;\\
	4) $g$ асимптотически ограничена функцией $h$: $\underset{K > 0}{\inf}$ $\underset{L(x) > K}{\sup}\frac{g(x)}{h(x)} < \infty$.\\
	Для измеримого множества $B \subseteq \mathfrak{X}$ определим $\tau_{B} = \inf\{n \geq 1: X_{n} \in B\}$. Множество $B$ называется \textit{возвратным}, если $\Pb{}_{x}(\tau_{B} < \infty) = 1$ и \textit{положительно возвратным}, если $\underset{x \in \mathfrak{X}}{\sup}\E{}_{x}\tau_{B} < \infty$. Сформулируем утверждение.
	\begin{numbered_theorem}
		(обобщенный критерий Фостера)
		Предположим, что существуют тестовая функция (<<функция Ляпунова>>) $L(x) \geq 0$, и функции $g$ и $h$, удовлетворяющие условиям $1)-4)$ такие, что
		\begin{equation}
		\E(L(X_{g(X_{0})}) - L(X_{0}) | X_{0}=x) \leq -h(x).
		\label{foster_property_2_app}
		\end{equation}
		Тогда существует $N_{0} \in \mathbb{N}$ такая, что для всех $N > N_{0}$ и всех $x \in \mathfrak{X}$ имеем $\E{}_{x}\tau < \infty$ и $\underset{L(x) \leq N}{\sup}\E{}_{x}\tau < \infty$, где $\tau \equiv \tau(N) = \inf\{n \geq 1 : L(x) \leq N\}$.
	\end{numbered_theorem} 
	
	${}$\\ Сформулируем третье вспомогательное утверждение из работы \cite{Foss_theorem_for_instability}. Данное утверждение более аккуратно изложено, а также доказано при более общих условиях в работе \cite{Denisov_instability}. Для простоты изложения мы приведем только частный случай для однородных цепей Маркова. Пусть последовательность $\{X_{n}\}_{n \geq 0}$ образует цепь Маркова такую, что
	\begin{equation*}
	X_{n+1} = f(X_{n}, \alpha_{n})
	\end{equation*}
	с начальным значением $X_{0} = x$, где $\{\alpha_{n}\}_{n \geq 0}$ образует последовательность независимых равномерно распределенных на отрезке $[0, 1]$ случайных величин, а $f$ --- измеримая функция. Пусть далее $\Delta = L(X_{1}) - L(X_{0})$, где $L$ --- измеримая функция. Определим
	\begin{equation*}
	\tau(N) = \inf\{n \geq 0\: : \: L(X_{n}) \geq N \}.
	\end{equation*}
	Далее полагаем, что $h(t)$ --- некоторая вещественная функция такая, что $(h(t))^{-1}$ интегрируема на промежутке $(1, \infty)$.\\
	\begin{numbered_theorem}
		Пусть существуют такие числа $N > 0$, $\varepsilon > 0$, $M > 0$ и такая функция $h(t)$, что\\
		1) $\tau(N) < \infty$ п.н. для произвольного начального состояния цепи;\\ 
		2) Для всех $x \in \mathfrak{X}$ таких, что $L(x) \geq N$, выполняется:
		\begin{equation*}
		\E{}_{x}(\Delta \cdot \mathds{1}(\Delta \leq M)) \geq \varepsilon;
		\end{equation*}
		3) Семейство случайных величин $\{h(-min(0, \Delta)),\: X_{0}=x, \:L(x) \geq N\}$ равномерно интегрируемо.
		
		Тогда для всех $x \in \mathfrak{X}$
		\begin{equation*}
		\Pb{}_{x}(\lim_{n\to\infty}L(X_{n}) = \infty) = 1.
		\end{equation*}
	\end{numbered_theorem}
	
	\bigskip
	\begin{thebibliography}{1} % Ссылки на литературу приводятся только на английском языке (даже если у источника нет англоязычной версии).
		
		\bibitem{Harb_Adnan} Harb, Adnan. 
		(2011). Energy harvesting: State-of-the-art. Renewable Energy. 36. 2641-2654. 10.1016/j.renene.2010.06.014.
		
		\bibitem{Sudevalayam_Kulkarni} S. Sudevalayam and P. Kulkarni, 
		"Energy Harvesting Sensor Nodes: Survey and Implications",$ $ in IEEE Communications Surveys \& Tutorials, vol. 13, no. 3, pp. 443-461, Third Quarter 2011, doi: 10.1109/SURV.2011.060710.00094.
		
		\bibitem{Example_of_applying_Xun_Zhou} Xun Zhou, Rui Zhang, Chin Keong Ho, 
		Wireless Information and Power Transfer in Multiuser OFDM Systems, IEEE Transactions on Wireless Communications, 13:4 (2014), 2282–2294.
		
		\bibitem{Jeon_finite_users} J. Jeon and A. Ephremides, 
		The stability region of random multiple access under stochastic energy harvesting, Proceedings of the IEEE International Symposium on Information Theory (ISIT), (2011), 1796–1800.
		
		\bibitem{Efficiency_protocols} A. Bergman, M. Sidi, 
		Energy efficiency of collision resolution protocols, Computer Communications, 29 (2006), 3397–3415.
		
		\bibitem{Abramson_dev_of_aloha_net} N. Abramson, 
		Development of the ALOHANET, IEEE Trans. Info. Theory, 31 (1985), 119– 123. Zbl 0563.94001
		
		\bibitem{FGL_1977} G. Fayolle, E. Gelenbe, J. Labetoulle, 
		Stability and optimal control of the packet switching broadcast channel, Journal of the ACM (JACM), 24:3 (1977), 375–386. MR0445639
		
		\bibitem{Kelly_classical_aloha_instability} J. P. Kelly and I. M. McPhee, 
		The Number of Packets Transmitted by Collision Detect Random Access Schemes, Annals of Probability, 15:4 (1987), 1557–1568. MR0905348
		
		\bibitem{Vvedenskaya_metastability} N. Vvedenskaya, Yu. Suhov, 
		Multi-access system with many users: Stability and metastability, Problems of Information Transmission, 43:3 (2007), 263–269. MR2360021
		
		\bibitem{Foss_2014} D. Kim, A. Turlikov, S. Foss, 
		Random multiple access with common energy harvesting mechanism, Siberian Electronic Mathematical Reports, 11 (2014), 896–905. MR3488468
		
		\bibitem{Foss_original} S. Foss, D. Kim, A. Turlikov, 
		Stability and instability of a random multiple access model with adaptive energy harvesting, Siberian Electronic Mathematical Reports, 13 (2016), 16–25. MR3506879
		
		\bibitem{Rezler_Chebunin} Rezler A., Chebunin M., 
		Stability and instability of a random multiple access system with an energy harvesting mechanism, Siberian Electronic Mathematical Reports, 19:1 (2022), pp. 1-17. MR4377429
		
		\bibitem{Foss_Konstantinopolous} S. Foss and T. Konstantopoulos, 
		An overview of some stochastic stability methods, Journal of Operation Research Society Japan, 47:4 (2004), 275–303. Zbl 1134.93412
		
		\bibitem{Foss_theorem_for_instability} Foss S. G. and Denisov D. E., 
		On transience conditions for Markov chains, Siberian Math. J., 42, No. 2, 364–371 (2001). MR183316
		
		\bibitem{Denisov_instability} Denisov D. E., 
		Markov chains and random walks with heavy-tailed increments, PhD thesis, Heriot-Watt University, Edinburgh, 2004
		
	\end{thebibliography}
\end{document}
