# Multi-channel ALOHA and CSMA medium-access protocols:
Markovian description and large deviations

###### Abstract.

We consider a multi-channel communication system under ALOHA and CSMA
protocols, resepctively, in continuous time. We derive probabilistic formulas
for the most important quantities: the numbers of sending attempts and the
number of successfully delivered messages in a given time interval. We derive
(1) explicit formulas for the large-time limiting throughput, (2) introduce an
explicit and ergodic Markov chain for a deeper probabilistic analysis, and use
this to (3) derive exponential asymptotics for rare events for these
quantities in the limit of large time, via large-deviation principles.

Wolfgang König111TU Berlin and WIAS Berlin, Mohrenstraße 39, 10117 Berlin,
Germany<EMAIL_ADDRESS>and Helia Shafigh222WIAS Berlin, Mohrenstraße
39, 10117 Berlin, Germany<EMAIL_ADDRESS>
WIAS Berlin and TU Berlin, and WIAS Berlin

(16 December 2022)

MSC 2010. 60K35, 82C21;

Keywords and phrases. Communication system, random medium access strategies,
throughput, multi-channel ALOHA protocol, CSMA, Markov chains, Markov renewal
process, large deviations.

##  1\. Introduction and main results

Protocols for medium access control (MAC) are fundamental and ubiquitous in
any telecommunication system. Here we are particularly interested in multi-
channel systems, where a fixed number of channels is available. Our goal is to
develop a probabilistic model for the ALOHA and the CSMA protocol, which can
be easily realised on a computer and be mathematically analysed in explicit
terms. We will describe the stochastic process of arrival times of incoming
and successfully delivered messages and the times that elapse in between in
terms of a Markov renewal process that is explicit and has very good ergodic
properties.

###  1.1. Medium access protocols; our goals

We consider the ALOHA protocol, where no infrastructure is given and
collisions are possible, and the Carrier Sense Multiple Access (CSMA)
protocol, where a message is delivered only if there is an idle channel at the
time when the message arrives. We work in continuous time and assume that the
messages arrive at random times that are given by a Poisson point process
(PPP). To keep things simple, we assume that the service times (delivery
times) are all equal to one.

We are interested in a multi–channel system, i.e., we assume that at most
$\kappa$ messages can be processed at any given time, where
$\kappa\in\mathbb{N}$ is a parameter. We think of two interpretations of this
restriction: Either there are $\kappa$ channels available in our system that
can be used independently all the time, or there are interference constraints
that make it impossible that more than $\kappa$ messages can be transmitted at
the same time, and any additional message is refused from the system.

Our interest lies on important quantities like the total number of messages in
the system, the number of incoming messages and the number of successfully
delivered messages in a given fixed time interval. We strive to calculate
expected values (in the limit of large time intervals), which follows
elementary ideas, but also to analyse more detailed questions, like
probabilities of certain events, which needs a deeper understanding of the
communication system.

To this sake, as one of our main novelties, we develop a description in terms
of an explicit Markov chain (in discrete time) that admits a description of
the mentioned quantities as functionals of this chain in terms of a kind of a
Markov renewal process. To the best of our knowledge, such a Markov chain was
not yet known in comparable situations, even though there are a number of
ansatzes with queues and the related theory; however these stochastic
processes are not able to give information about the real time, but only about
certain quantities (i.e., number of messages in the system) at the (random)
arrival times or the (random) delivery times of the messages. Our Markov chain
makes the application of a number of well-known probabilistic tools available,
like invariant initial distributions, ergodic theory and large deviations
theory. We give explicit formulas for the transition probabilities and prove
that this chain is uniformly ergodic, hence this Markov chain is also useful
for making computer simulations.

Our Markov chain in particular opens the possibility to describe (the
probabilities of) rare events, which is for example helpful if one wants to
understand ubiquitous situations in which the system underachieves by
producing a smaller throughput than is expected over a long time stretch. The
probabilistic theory of large deviations provides mathematical tools for
deriving formulas for the exponential decay of the probability, and it
provides also tools for characterising the most likely behaviour of the system
in this unlikely situation. For the application of this theory, one needs a
powerful description and a high degree or ergodicity, and this is provided by
our Markov chain. Unfortunately, our description does not allow for the
determination of sharp exponential lower bounds for the probabilities of large
deviations, but only exponential upper bounds. But we believe it is the
exponential upper bounds that shows the value of the large-deviation theory
for understanding such communication system.

The most important parameters in the system will be the number of channels,
$\kappa\in\mathbb{N}$, and the density parameter of the incoming messages,
$\lambda\in(0,\infty)$. We assume that the arrival times follow a standard
Poisson point process with parameter $\lambda$. We will conceive the situation
from the user’s perspective and will discuss the optimal value of $\lambda$
for achieving a maximal throughput. The idea behind this is that each user has
the knowledge about the number of users in a vicinity of the $\kappa$ channels
and assumes that each of them makes message sending attempts at a certain rate
that amounts to the total rate $\lambda$ of all the message attempts. Under
these assumptions, the optimal value of $\lambda$, divided by the number of
users, should then be the probability parameter for making sending attempts.

In the CSMA setting, it will be clear that the throughput is an increasing
function of $\lambda$, and the optimisation is trivial (ignoring a potential
trade-off coming from a huge number of unsuccessful messages). However, for
the ALOHA setting, it will be interesting to identify the optimal density
$\lambda$ (depending on $\kappa$) for having a maximal throughput; this will
be one of our results.

Summarizing, the main contributions of this paper are the following.

  * •

An explicit probabilistic description (in terms of a Markov renewal process)
of the number of messages and the number of successfully delivered messages
and more quantities at a deterministic time,

  * •

explicit formulas for limiting expected values of these quantities and optimal
values of parameters,

  * •

a large-deviations analysis of rare events involving these quantities.

###  1.2. Description of the models

We consider a system with a steady flow of incoming messages that require
access to the system at random times. The time lags between any two subsequent
arrivals of two messages are independent exponentially distributed times with
density parameter $\lambda\in(0,\infty)$. That is, the sequence of arrival
times forms a standard Poisson point process (PPP) with parameter $\lambda$.
Any successful message transmission has a duration of precisely one time unit;
i.e., each service time is equal to one.

We assume that $\kappa$ channels are available. On arrival, each message asks
for access to some of them. Now we consider two different algorithms (medium
access protocols) according to which this request is handled:

  * $\bullet$

ALOHA: For the message, one of the $\kappa$ channels is picked uniformly at
random. All these channel choices are independent over all messages.

    * –

If the channel is already busy i.e., if the transmission of another message in
this channel is still running, then the new incoming message collides with the
old one, causing the cancellation of both messages.

    * –

If the channel is idle, the new message is admitted immediately. If not
cancelled by another message that arrives later during the delivery time, it
will be successfully delivered after one time unit.

  * $\bullet$

CSMA: The message is admitted to the system only if there is an empty channel;
then it will be successfully delivered via one of these channels after one
time unit. Otherwise, the message attempt is canceled.

In the case of a successful delivery after one time unit, we say that the
message has gained access to the medium.

Advantages of pure ALOHA are that it does not need any infrastructure and is
therefore cheap to install and run. However, a drawback is that on each
arrival of a message might destroy another message that has been already
admitted to the system. In turn, this means that each message can be sure to
be successfully delivered only one time unit after it has picked an empty
channel, namely if has not itself been killed by a later arriving message
during its delivery. This means that too large a number of incoming messages
(i.e., too large a large value of $\lambda$) decreases on an average the
amount of successful deliveries in the system on a long time. We will specify
this in terms of a law of large numbers and will see that only a certain
percentage of all the channels are typically busy in order to achieve an
optimal throughput in this protocol, and we will identify this value.

In CSMA, every admitted message will definitely be successfully delivered
after its delivery time. However, in contrast with the ALOHA protocol, some
extra information (namely the information about free channels) needs to be
constantly provided. Hence, increasing the message density $\lambda$ increases
the number of busy channels on an average and hence the throughput (which we
quantify below), but also the average number of refused messages (which we
neglect in this paper).

###  1.3. Our results

Introduce $A(t)$ as the number of sending attempts in the time interval
$[0,t]$ and $S(t)$ as the number of successful transmissions during this time
interval. Then $(A(t))_{t\in[0,\infty)}$ is the counting process for the
PPP$(\lambda)$, but $(S(t))_{t\in[0,\infty)}$ is highly non-trivial and is the
main objective. We formulate our results on the limiting expectation in
Section 1.3.1, on a crucial Markov chain in Section 1.3.2 and on the
probabilities of large deviations in Section 1.3.3.

####  1.3.1. Limiting expectation

Let us calculate the limiting expectation of the number of successfully
delivered messages:

######  Lemma 1.1 (Expected throughput).

For both models, $*\in\\{{\rm ALOHA,CSMA}\\}$, and for any
$\lambda\in(0,\infty)$ and $\kappa\in\mathbb{N}$,

$s_{*}(\lambda,\kappa)=\lim_{t\to\infty}\frac{1}{t}S(t)$ (1.1)

exists and is equal to

$\displaystyle s_{\rm CSMA}(\lambda,\kappa)$ $\displaystyle=$
$\displaystyle\lambda\frac{\sum_{n=0}^{\kappa-1}\frac{\lambda^{n}}{n!}}{\sum_{n=0}^{\kappa}\frac{\lambda^{n}}{n!}}=\lambda\frac{{\operatorname{Poi}}_{\lambda}([0,\kappa-1])}{{\operatorname{Poi}}_{\lambda}([0,\kappa])},$
(1.2) $\displaystyle s_{\rm ALOHA}(\lambda,\kappa)$ $\displaystyle=$
$\displaystyle\lambda{\operatorname{e}}^{-\frac{\kappa+1}{\kappa}\lambda}\sum_{n=0}^{\kappa-1}\frac{\lambda^{n}}{n!}\frac{\kappa-n}{\kappa}=\lambda{\operatorname{e}}^{-\frac{\lambda}{\kappa}}{\operatorname{e}}^{-\lambda}\Big{[}\sum_{n=0}^{\kappa-1}\frac{\lambda^{n}}{n!}-\frac{\lambda}{\kappa}\sum_{n=0}^{\kappa-2}\frac{\lambda^{n}}{n!}\Big{]}$
(1.3) $\displaystyle=$
$\displaystyle\lambda{\operatorname{e}}^{-\frac{\lambda}{\kappa}}\Big{[}{\operatorname{Poi}}_{\lambda}([0,\kappa-1])-\frac{\lambda}{\kappa}{\operatorname{Poi}}_{\lambda}([0,\kappa-2])\Big{]}.$
(1.4)

We wrote ${\operatorname{Poi}}_{\lambda}$ for the Poisson-distribution with
parameter $\lambda$ on $\mathbb{N}_{0}$. The proof of Lemma 1.1 is in Section
2.2 for the ALOHA case and in Section 2.1 for the CSMA case.

In contrast with CSMA, for the ALOHA protocol the question for the optimal
value of $\lambda$ for maximizing $s_{\rm ALOHA}(\lambda,\kappa)$ is
interesting. An explicit calculation does not seem possible for general
$\kappa$. However, using the exponential series approximation for the two
sums, we see that for $\kappa\to\infty$ the throughput is asymptotically
equivalent to

$\displaystyle\lim_{\lambda,\kappa\to\infty,\frac{\lambda}{\kappa}\to
x}\frac{1}{\kappa}s_{\rm
ALOHA}(\lambda,\kappa)=x(1-x){\operatorname{e}}^{-x},\qquad x\in[0,\infty),$

which is easily seen to have a unique maximum for
$x=\frac{3-\sqrt{5}}{2}\approx 0.38$ by considering the derivatives. Hence,
the optimal throughput is roughly $\sup_{\lambda}s_{\rm
ALOHA}(\lambda,\kappa)\approx 0.38\,\kappa$ for large $\kappa$. Simulations
show that for $\kappa=2$ resp. $\kappa=3$ we already have an optimum value for
$\lambda\approx 0.43\,\kappa$ resp. $\lambda\approx 0.41\,\kappa$; the above
approximation seems to converge extremely fast.

####  1.3.2. A crucial Markov chain

We are going to introduce now the main object of our ansatz, a certain Markov
chain in discrete time that is able to describe the main quantities $A(t)$ and
$S(t)$. This Markov chain is not only suitable for describing large-deviation
events and their probabilities (see Section 1.3.3), but can generally also be
used to derive explicit computer simulations for the entire process of
messages and their deliveries.

In both models, we denote by
$0<\widetilde{T}_{1}<\widetilde{T}_{2}<\widetilde{T}_{3}<\dots$ all the times
at which a message is admitted to a channel. For $i\in\mathbb{N}$ put

$\sigma_{i}=\widetilde{T}_{i}-\widetilde{T}_{i-1}\qquad\mbox{and}\qquad
A_{i}=\\#\\{j\colon T_{j}\in(\widetilde{T}_{i-1},\widetilde{T}_{i}]\\}.$

In words, $\sigma_{i}$ is the length of the time lag between the $(i-1)$st and
$i$th admittance of a message to some channel, and $A_{i}-1$ is the number of
refused messages during that time interval. Recall that, for CSMA,
$\widetilde{T}_{i}$ is the time of the beginning of the $i$-th successful
message transmission, but for ALOHA this is only the time of the start of some
message transmission attempt; whether or not it will be successful will turn
out only at time $\widetilde{T}_{i}+1$. Nevertheless, we will show that the
sequence $(A_{i},\sigma_{i})_{i\in\mathbb{N}}$ is suitable to derive precise
information about our quantities of interest, $(A(t),S(t))$.

As our first main result, we identify the distribution of the sequence as a
kind of Markov renewal process:

######  Proposition 1.2 (Markovian structure of
$(A_{i},\sigma_{i})_{i\in\mathbb{N}}$).

In both models, ALOHA and CSMA, the sequence
$(A_{i},\sigma_{i})_{i\in\mathbb{N}}$ is a $(\kappa-1)$-Markov chain with
kernel $W_{\rm CSMA}$ and $W_{\rm ALOHA}$, respectively, from
$[\mathbb{N}\times(0,\infty)]^{\kappa-1}$ to $\mathbb{N}\times(0,\infty)$
defined by

$\displaystyle W_{\rm CSMA}\big{(}(a,t),(k,{\rm d}s)\big{)}$ $\displaystyle=$
$\displaystyle\frac{\gamma^{k-1}}{(k-1)!}\lambda^{k}{\operatorname{e}}^{-\lambda
s}{\mathchoice{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.5mu\mathrm{l}}{1\mskip-5.0mu\mathrm{l}}}_{[\gamma,\infty)}(s)\,{\rm
d}s,$ (1.5) $\displaystyle W_{\rm ALOHA}\big{(}(a,t),(k,{\rm d}s)\big{)}$
$\displaystyle=$
$\displaystyle\frac{\big{(}\gamma+\frac{B(s)}{\kappa}\big{)}^{k-1}}{(k-1)!}\left(1-\frac{\beta(s)}{\kappa}\right)\lambda^{k}{\operatorname{e}}^{-\lambda
s}{\mathchoice{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.5mu\mathrm{l}}{1\mskip-5.0mu\mathrm{l}}}_{[\gamma,\infty)}(s)\,{\rm
d}s,$ (1.6)

for $(a,t)=\big{(}(a_{1},t_{1}),\cdots,(a_{\kappa-1},t_{\kappa-1})\big{)}$,
where $\gamma:=[1-\sum_{i=1}^{\kappa-1}t_{i}]_{+}$, and, for the ALOHA case,

$\displaystyle\beta(s):=\max\Big{\\{}m\in\mathbb{N}\colon
s+\sum_{j=0}^{m-2}t_{\kappa-1-j}\leq
1\Big{\\}}\wedge\kappa\in\\{0,1,\dots,\kappa\\}\qquad\mbox{and}\qquad
B(s)=\int_{0}^{s}\beta(r)\,{\rm d}r.$

Both $(\kappa-1)$-Markov chains are uniformly ergodic in the sense that
Condition (U) holds (see (3.5)).

The proofs are in Section 3.1 for the CSMA case and in Section 3.2 for the
ALOHA case.

######  Remark 1.3 (Interpretation of the ALOHA kernel).

In the kernel $W_{\rm ALOHA}$, the parameter $\beta(s)$ plays the role of the
number of busy channels at time $\widetilde{T}_{i}+s$, conditioned on the
process of message arrivals before time $\widetilde{T}_{i}$. Therefore
$1-\frac{\beta(s)}{\kappa}$ is the probability that a message that arrives at
that time picks an idle channel. The remaining terms on the right of (1.6)
express the probability that all the messages arriving during
$[\widetilde{T}_{i},\widetilde{T}_{i}+\gamma)$ and during
$[\widetilde{T}_{i}+\gamma,\widetilde{T}_{i}+s)$ pick a busy channel and are
therefore not admitted to the system. We will specify this in the proof.
$\Diamond$

######  Remark 1.4 (Markov renewal process).

We see that in both cases $(\sigma_{i})_{i\in\mathbb{N}}$ is autonomously a
$(\kappa-1)$-Markov chain (with a kernel that can easily be deduced from (1.5)
and (1.6), respectively), and $A_{i}$ is a random function of
$\sigma_{i-1},\sigma_{i-2},\dots,\sigma_{i-\kappa+1}$. More precisely, given
the sequence $(\sigma_{i})_{i\in\mathbb{N}}$, the variables $A_{i}$ are
independent over $i$ and are Poisson-distributed with a certain parameter
depending on $\sigma_{i-1},\sigma_{i-2},\dots,\sigma_{i-\kappa+1}$. Because of
this Markovian structure, $(A_{i},\sigma_{i})_{i\in\mathbb{N}}$ (more
precisely,
$(A_{i},(\sigma_{i-1},\dots,\sigma_{i-\kappa+1}))_{i\in\mathbb{N}}$) is often
called a Markov renewal process. $\Diamond$

######  Remark 1.5 (Deriving $S(t)$ and $A(t)$).

In the CSMA case, $t\mapsto S(t)$ is nothing but the time-inverse of the
partial sum sequence of the $\sigma_{i}$ via the formula

$S(t)=\sup\Big{\\{}m\in\mathbb{N}\colon\sum_{i=1}^{m}\sigma_{i}\leq
t\Big{\\}}$ (1.7)

and can therefore be fully described in terms of
$(\sigma_{i})_{i\in\mathbb{N}}$. A similar assertion applies to $A(t)$; see
(4.14). However, in the ALOHA case one needs additionally
$(A_{i})_{i\in\mathbb{N}}$ for the description of $S(t)$ (see (4.15)).
Certainly, one can also describe other interesting quantities as functionals
of the Markov chain, for example the number of unsuccessful messages or (in
the ALOHA case) the number of messages that are admitted to some channel, but
are canceled later during the service time. $\Diamond$

####  1.3.3. Large deviations

Now we turn to our results concerning the large deviations for $(A(t),S(t))$
in the limit $t\to\infty$. Our goal is to quantify the exponential decay rate
of the probability of rare events of the form $\\{\frac{1}{t}(A(t),S(t))\in
B\\}$ for many sets $B\subset(0,\infty)^{2}$.

Let us recall the notion of a large-deviation principle (LDP). Indeed, a
sequence $(X_{n})_{n\in\mathbb{N}}$ of ${\mathcal{X}}$-valued random variables
(where ${\mathcal{X}}$ is a Polish space) is said to satisfy an LDP with lower
semicontinuous rate function $I\colon{\mathcal{X}}\to[0,\infty]$ if for any
closed set $F\subset{\mathcal{X}}$ and any open set $G\subset{\mathcal{X}}$,

$\limsup_{n\to\infty}\frac{1}{n}\log\mathbb{P}(X_{n}\in
F)\leq-\inf_{F}I\qquad\mbox{and}\qquad\liminf_{n\to\infty}\frac{1}{n}\log\mathbb{P}(X_{n}\in
G)\geq-\inf_{G}I.$

The first statement is called the large-deviations upper bound (or LDP upper
bound), the latter the large-deviations lower bound. These together can be
very roughly summarized by saying that $\mathbb{P}(X_{n}\approx
x)\approx{\operatorname{e}}^{-nI(x)}$ for any $x\in\mathcal{X}$ as
$n\to\infty$. However, topological subtleties are always present in an LDP.
See [DZ10] for an account on LDP theory.

Indeed, with the help of the Markov renewal process
$(A_{i},\sigma_{i})_{i\in\mathbb{N}}$ we are in an excellent position to find
and prove such an LDP and to identify the rate functions for the two cases;
indeed there are very obvious candidates, which are based on the sequence of
empirical pair measures of $(A_{i},\sigma_{i})_{i\in\mathbb{N}}$. However,
there is a problem that we could not overcome, and hence we are only able to
derive the LDP upper bound. This problem does not seem to be only technical;
it is the fact that $(A(t),S(t))$ is not a continuous functional of the
empirical measure. This makes it impossible to use standard arguments, and we
found no way around it; hence we state only the LDP upper bound below. It is
not clear to us whether or not the corresponding lower bound holds as well.

The rate functions will be identified in terms of certain entropies, which are
well-known in the LDP-theory for Markov chains. Indeed, we write
$H(\mu\mid\nu)=\int{\rm d}\mu\log\frac{{\rm d}\mu}{{\rm d}\nu}$ for the
relative entropy of a probability measure $\mu$ with respect to another one,
$\nu$ (if the density exists, otherwise $H(\mu\mid\nu)=\infty$). Furthermore,
for a measure $\mu$ on ${\mathcal{X}}^{\kappa}$, we write
$\mu^{{\scriptscriptstyle{({\kappa-1})}}}$ for the projection of $\mu$ on the
vector of the first $\kappa-1$ components, and we say that $\mu$ lies in
${\mathcal{M}}_{1}^{{\scriptscriptstyle{({\rm s})}}}({\mathcal{X}}^{\kappa})$
if $\mu$ is a probability measure on ${\mathcal{X}}^{\kappa}$ whose projection
on the vector of the first $\kappa-1$ components is equal to its projection on
the vector of the last $\kappa-1$ components. We abbreviate
$\Sigma:=\mathbb{N}\times(0,\infty)$ and define the projections
$\pi_{1}\colon\Sigma^{\kappa}\to\mathbb{N}$ and
$\pi_{2}\colon\Sigma^{\kappa}\to(0,\infty)$ by
$\pi_{1}((a_{1},r_{1}),\dots,(a_{\kappa},r_{\kappa}))=a_{\kappa}$ and
$\pi_{2}((a_{1},r_{1}),\dots,(a_{\kappa},r_{\kappa}))=r_{\kappa}$. We write
$\langle f,\mu\rangle$ for the integral of a function $f$ with respect to a
measure $\mu$.

Our main asymptotic large-deviation results as $t\to\infty$ are as follows.

######  Theorem 1.6 (Large-deviation upper bound for $(A(t),S(t))$).

In both cases, ALOHA and CSMA, as $t\to\infty$, the pair
$\frac{1}{t}(A(t),S(t))$ satisfies an LDP upper bound on $(0,\infty)^{2}$,
i.e., for any closed set $F\subseteq(0,\infty)^{2}$ we have

$\displaystyle\limsup_{t\to\infty}\frac{1}{t}\log\mathbb{P}\Big{(}\frac{1}{t}\big{(}S(t),A(t)\big{)}\in
F\Big{)}\leq-\inf_{F}I_{*},$

where, for $a,s\in[0,\infty)$,

$I_{\rm
CSMA}(a,s)=\sup_{A\in\mathbb{R},B\in(-\infty,\lambda)}\inf_{\mu\in{\mathcal{M}}_{1}^{{\scriptscriptstyle{({\rm
s})}}}(\Sigma^{\kappa})}\big{[}A\left(a-s\left<\pi_{1},\mu\right>\right)+B\left(1-s\left<\pi_{2},\mu\right>\right)+H(\mu\mid\mu^{{\scriptscriptstyle{({\kappa-1})}}}\otimes
W_{\rm CSMA})\big{]}$

for the CSMA protocol and

$\displaystyle I_{\rm
ALOHA}(a,s)=\sup_{A\in\mathbb{R},B\in(-\infty,\lambda)}\inf_{\mu\in{\mathcal{M}}_{1}^{{\scriptscriptstyle{({\rm
s})}}}(\Sigma^{\kappa})}\Big{[}A\big{(}a-\textstyle{\frac{a+s}{2}}\left<\pi_{1},\mu\right>\big{)}$
$\displaystyle+B\big{(}1-\textstyle{\frac{a+s}{2}}\left<\pi_{2},\mu\right>\big{)}$
$\displaystyle+H(\mu\mid\mu^{{\scriptscriptstyle{({\kappa-1})}}}\otimes W_{\rm
ALOHA})\Big{]}$

in the case of ALOHA protocol. Both rate functions have precisely one
minimizer and are convex on $(0,\infty)^{2}$ and are good (i.e., their level
sets $\\{(a,s)\colon I_{*}(a,s)\leq C\\}$ are compact for any $C$). The family
$(\frac{1}{t}(A(t),S(t)))_{t>0}$ is exponentially tight (i.e., for any $M>0$
there is a $K>0$ such that
$\mathbb{P}(\frac{1}{t}(A(t),S(t))\notin[0,K]^{2})\leq{\operatorname{e}}^{-tM}$
for any $t$).

The proof is in Section 4. By the well-known contraction principle (saying
that LDPs are obtained under continuous images and gives an explicit formula
for the rate function), we obtain without work:

######  Corollary 1.7 (LDP upper bound for number of successfully delivered
messages).

As $t\to\infty$, $\frac{1}{t}S(t)$ satisfies an LDP upper bound with rate
function

$I^{S}_{\rm
CSMA}(s)=\sup_{B\in(-\infty,\lambda)}\inf_{\mu\in{\mathcal{M}}_{1}^{{\scriptscriptstyle{({\rm
s})}}}(\Sigma^{\kappa})}\left\\{B\left(1-s\left<\pi_{2},\mu\right>\right)+H(\mu\mid\mu^{{\scriptscriptstyle{({\kappa-1})}}}\otimes
W_{\rm CSMA})\right\\}$ (1.8)

for the CSMA protocol resp.

$I^{S}_{\rm
ALOHA}(s)=\sup_{B\in(-\infty,\lambda)}\inf_{\mu\in{\mathcal{M}}_{1}^{{\scriptscriptstyle{({\rm
s})}}}(\Sigma^{\kappa})}\left\\{B\left(1-\frac{\left<\pi_{2},\mu\right>s}{2-\left<\pi_{1},\mu\right>}\right)+H(\mu\mid\mu^{{\scriptscriptstyle{({\kappa-1})}}}\otimes
W_{\rm ALOHA})\right\\}$ (1.9)

for the ALOHA protocol.

The proof of Corollary 1.7 is immediate from the contraction principle, noting
that the canonical projection $\mathbb{N}\times(0,\infty)\to\mathbb{N}$ is
continuous.

######  Remark 1.8 (Expected throughput and rate function).

Let us mention that the expected throughput $s_{*}(\lambda,\kappa)$ that we
identified in Lemma 1.1 can also be characterized in a standard way as the
minimizer of the rate function $I^{S}_{*}$ for $*\in\\{{\rm ALOHA,CSMA}\\}$.
However, it is rather difficult to identify it from this reasoning since we
have no closed formula for the invariant distribution of the Markov chain
$(A_{i},\sigma_{i})_{i\in\mathbb{N}}$, such that we do not have any results in
this respect. $\Diamond$

######  Remark 1.9 (Contracting to $A(t)$).

Instead of contracting the pair $(A(t),S(t))$ to $S(t)$, we could do this also
with $A(t)$ and obtain an analogue of Corollary 1.7. However, since $A(t)$ is
nothing but the PPP, one can derive an LDP for $\frac{1}{t}A(t)$ also with
much simpler means and obtains the rate function
$I^{A}_{*}(a)=\lambda-a+a\log\frac{a}{\lambda}$. $\Diamond$

######  Remark 1.10 (An application).

We think that exponential estimates for the probabilities of rare events like
in Corollary 1.7 are very relevant for the understanding of the strengths and
shortcomes of such telecommunication systems. Indeed, they give us not only
extremely good estimates for such probabilities, but also an analytic starting
point for getting more information about the most likely situation that
governs the rare event: the variational formula for the rate function.

As an example, the probability of the event $\\{S(t)\leq
t[s_{*}(\lambda,\kappa)-\varepsilon]\\}$ that the number of successfully
delivered messages in the time interval $[0,t]$ is not larger than
$t[s_{*}(\lambda,\kappa)-\varepsilon]$ is upper bounded by
$\exp\\{-t\inf_{s\in[0,s_{*}(\lambda,\kappa)-\varepsilon]}I_{*}^{S}(s)\\}$ as
$t\to\infty$, for any $\varepsilon>0$. This means that this probability decays
exponentially fast with rate at least
$\inf_{[0,s_{*}(\lambda,\kappa)-\varepsilon]}I_{*}^{S}=I_{*}^{S}(s_{*}(\lambda,\kappa)-\varepsilon)>0$.
$\Diamond$

######  Remark 1.11 (Why not a full LDP?).

It would be rather desirable to have a full LDP for $(A(t),S(t))$ with rate
function $I_{*}$, but there is an obstacle that we could not overcome: the
lack of continuity of the map $\mu\mapsto\langle\pi_{2},\mu\rangle$, since
$\pi_{2}$ is unbounded. This makes an application of the crucial Gärtner–Ellis
theorem impossible, since it prevents us from proving that $I_{*}$ is strictly
convex, and therefore from proving that its Legendre transform is
differentiable. It also prevents us from using the contraction principle,
since $(A(t),S(t))$ is not a continuous functional of the empirical measures
of $(A_{i},\sigma_{i})_{i\in\mathbb{N}}$ (see Section 4). With a lot of more
work, we would be able to derive LDP lower bounds that are severely
restricted, and the restriction would not be easy to understand, so we
abstained from formulating any lower bound. $\Diamond$

###  1.4. Related literature

In [B48] and [K53] the CSMA model in continuous time is modeled with the help
of a queue that expresses the number of messages that are present in the
$\kappa$ channels as a function of the time parameter. Both restricted to the
case of exponential distributed service times, which lead to a Markov model,
whose invariant distribution can be calculated easily and explicitly. More
general results involving arbitrary service time distributions can be found in
[B76]. Here the process $(Q_{n})_{n\in\mathbb{N}}$ of the numbers $Q_{n}$ of
messages in the channels at the time of the arrival of the $n$-th message is
considered and its limiting distribution is calculated explicitly depending on
the arrival and service time distributions. This and additional ad-hoc methods
make it possible to obtain information about the number of successes at a late
time, e.g., a law of large numbers. Unfortunately, the process
$(Q_{n})_{n\in\mathbb{N}}$ does not have the Markov property, but an
infinitely long memory. Hence, probabilistic formulas could not be derived,
and large deviations for the throughput of the system could not be considered.

In [RS90] one finds the throughput of the single-channel continuous time CSMA,
which is $\frac{\lambda}{\lambda+1}$ and coincides with our formula for
$s_{\rm CSMA}(\lambda,1)$ in the case $\kappa=1$. Another version of CSMA,
namely slotted (single channel) CSMA, has been studied more intensively than
the continuous time model (see [RS90], [GD11], [WLZ10] and [LST19]), and
provides also the same limiting throughput as the continuous time model in the
single channel case. Let us mention that an analogous large-deviation analysis
of multi-channel discrete-time versions of ALOHA and slotted ALOHA and CSMA is
carried out in [KK22].

Since [A77], the single-channel pure ALOHA has been studied intensely (for a
general overview see [LST19], [RS90] and [SBBB08]). The throughput is
identified there as $\lambda{\operatorname{e}}^{-2\lambda}$, which also
coincides with our result for $s_{\rm ALOHA}(\lambda,1)$ in the special case
$\kappa=1$. In [SW95], [LST19], [RS90] and [SBBB08] one can also read about
another, more popular and better known, single channel version of ALOHA,
namely the slotted ALOHA, with the higher throughput
$\lambda{\operatorname{e}}^{-\lambda}$. The multichannel case of this model
has also been studied, e.g., in [SL12], where the throughput
$\lambda{\operatorname{e}}^{-\frac{\lambda}{\kappa}}$ has been calculated. See
[KK22] for a derivation of this value via a large-deviation analysis with
explicit rate functions. To the best of our knowledge, there are no similar
results for the multichannel model in continuous time in the literature yet,
hence we think that our Lemma 1.1 is novel.

##  2\. Expectation of the throughput

Let us derive formulas for the expected throughput in the two protocols, i.e.,
formulas for the expectation of the large-$t$ limit of $\frac{1}{t}S(t)$. In
Section 2.1 and Section 2.2, respectively, we consider CSMA and ALOHA. This
section has nothing to do with the Markov chains introduced in Section 1.3.2.

###  2.1. CSMA

We borrow some knowledge that was gained in [B76]. We pointed out in Section
1.4 that the CSMA system was analysed in [B76] with the help of a stochastic
process $Q=(Q_{n})_{n\in\mathbb{N}}$, where $Q_{n}$ denotes the number of
messages in the $\kappa$ channels (the number of busy channels) at the arrival
time of the $n$-th message. The limiting distribution $\nu_{Q}$ of $Q_{n}$, as
$n$ goes to infinity, has been calculated there as

$\displaystyle\nu_{Q}(i)=\frac{\frac{\lambda^{i}}{i!}}{\sum_{k=0}^{\kappa}\frac{\lambda^{k}}{k!}}={\operatorname{Poi}}_{\lambda}|_{[0,\kappa]}(i),\qquad
i\in\\{0,1,\dots,\kappa\\},$

where we wrote ${\operatorname{Poi}}_{\lambda}|_{[0,\kappa]}$ for the Poisson
distribution with parameter $\lambda$, conditioned on being $\leq\kappa$. It
was also proved there that the limiting distribution of $Q_{n}$ as
$n\to\infty$ coincides with the limiting distribution of the number of busy
channels at a deterministic time $t$ as $t\to\infty$. Using this result, we
obtain

$\displaystyle s_{\rm
CSMA}(\lambda,\kappa)=\lambda\frac{\sum_{n=0}^{\kappa-1}\frac{\lambda^{n}}{n!}}{\sum_{n=0}^{\kappa}\frac{\lambda^{n}}{n!}}=\lambda\frac{{\operatorname{Poi}}_{\lambda}([0,\kappa-1])}{{\operatorname{Poi}}_{\lambda}([0,\kappa])},$
(2.1)

since the average number of the number of successes is equal to the arrival
rate $\lambda$, multiplied by the success probability, which is given by the
second factor, as every new arriving message can only be delivered
successfully, if there are at most $\kappa-1$ busy channels.

In (2.1) one sees that $s_{\rm CSMA}(\lambda,\kappa)$ is increasing in
$\lambda$ and converges to $\kappa$ as $\lambda\to\infty$, which is
intuitively clear, because most of the channels are likely to be busy if the
arrival rate is high. Therefore, there is no interesting optimisation task
over $\lambda$, since the throughput get always better if the density of
message is increased. Taking into account also the number of unsuccessful
messages (which explodes as $\lambda\to\infty$) makes this issue more
interesting, but we do not strive on this here.

Let us finally mention that in the special case $\kappa=1$ our expression
(2.1) yields $s_{\rm CSMA}(\lambda,1)=\frac{\lambda}{\lambda+1}$, which was
formerly known (see e.g., [RS90]).

###  2.2. ALOHA

Let us calculate the expected limiting throughput in the ALOHA protocol by
hand. The expression that we obtain is good enough for also finding the
optimal value of the density $\lambda$, at least for large $\kappa$.

Since we are looking at the limit of late times, we need to analyse the ALOHA
process in equilibrium. This can be realised by extending the PPP from
$[0,\infty)$ to $\mathbb{R}$ and to consider its Palm measure given that one
message arrives at time $0$. Write $A([a,b))$ for the number of incoming
messages during the time interval $[a,b)$. Fortunately, the number of busy
channels at time $0$ depends only on the PPP during the time interval
$[-1,0)$, i.e., on $A([-1,0))$. Indeed, the probability of having at least one
available channel and taking one of those is equal to

$\sum_{n=0}^{\kappa-1}\mathbb{P}\left(A([-1,0))=n\right)\cdot\left(1-\frac{n}{\kappa}\right)=\sum_{n=0}^{\kappa-1}\frac{\lambda^{n}}{n!}{\operatorname{e}}^{-\lambda}\frac{\kappa-n}{\kappa}.$
(2.2)

Note that the PPP has the property that $A([-1,0))$ does not depend on the
incoming messages after time $0$; these are the only ones that might influence
the transmission success of the message that arrived at time $0$. Hence, for
the success probability we have to multiply the term in (2.2) with the
probability that the message that arrived at time $0$ does not get destroyed
afterwards during its service time $(0,1]$, which is equal to

$\displaystyle\sum_{n=0}^{\infty}\mathbb{P}\left(A((0,1])=n\right)\left(\frac{\kappa-1}{\kappa}\right)^{n}=$
$\displaystyle\sum_{n=0}^{\infty}\frac{\lambda^{n}}{n!}{\operatorname{e}}^{-\lambda}\left(\frac{\kappa-1}{\kappa}\right)^{n}={\operatorname{e}}^{\lambda\left(\frac{\kappa-1}{\kappa}\right)-\lambda}={\operatorname{e}}^{-\frac{\lambda}{\kappa}}.$

Hence,

$s_{\rm
ALOHA}(\lambda,\kappa)=\lambda{\operatorname{e}}^{-\frac{\kappa+1}{\kappa}\lambda}\sum_{n=0}^{\kappa-1}\frac{\lambda^{n}}{n!}\frac{\kappa-n}{\kappa}=\lambda{\operatorname{e}}^{-\frac{\lambda}{\kappa}}{\operatorname{e}}^{-\lambda}\Big{[}\sum_{n=0}^{\kappa-1}\frac{\lambda^{n}}{n!}-\frac{\lambda}{\kappa}\sum_{n=0}^{\kappa-2}\frac{\lambda^{n}}{n!}\Big{]}.$
(2.3)

In the case $\kappa=1$ this is equal to
$\lambda{\operatorname{e}}^{-2\lambda}$, which was already known; see Section
1.4. This is optimized at $\lambda=\frac{1}{2}$ with value
$s_{1/2,1}=\frac{1}{2{\operatorname{e}}}\approx\,.18$.

##  3\. Markov approach

In this section, we introduce suitable Markov chains for both protocols, CSMA
and ALOHA, that are able to describe the number of successful and unsuccessful
sending attempts by time $t$. Again, we keep $\lambda\in(0,\infty)$ and
$\kappa\in\mathbb{N}$ fixed.

###  3.1. Markov approach to CSMA

Let us model the CSMA protocol in terms of a stochastic process in discrete
time. Recall that $0<T_{1}<T_{2}<T_{3}<\dots$ denotes all the times at which a
message comes in and asks for being admitted to one of the $\kappa$ channels.
According to our assumptions, $(T_{i})_{i\in\mathbb{N}}$ is a standard Poisson
point process (PPP) in $[0,\infty)$ with parameter $\lambda$, and we denote
$\tau_{i}=T_{i}-T_{i-1}$. It is convenient to introduce the counting process
${\mathcal{N}}$ defined by ${\mathcal{N}}(I)=\\#\\{i\in\mathbb{N}\colon
T_{i}\in I\\}$ (the number of sending attempts during the time interval $I$)
for intervals $I$. Then $A(t)={\mathcal{N}}([0,t])$ is the number of attempts
by time $t$.

By $(\widetilde{T}_{i})_{i\in\mathbb{N}}$ we denote the subsequence
$(T_{k(i)})_{i\in\mathbb{N}}$ of $(T_{i})_{i\in\mathbb{N}}$ of all those times
$T_{j}$ at which the incoming message is admitted to a channel (i.e., at which
not all the $\kappa$ channels are busy); then the delivery takes place during
the time interval $[T_{k(i)},T_{k(i)}+1]$, and at time $T_{k(i)}+1$ the
message is successfully delivered. We introduce the counting process
${\mathcal{N}}^{{\scriptscriptstyle{({\rm s})}}}$ defined by
${\mathcal{N}}^{{\scriptscriptstyle{({\rm
s})}}}(I)=\\#\\{j\in\mathbb{N}\colon\widetilde{T}_{j}\in I\\}$ for measurable
sets $I\subset[0,\infty)$. Then $S(t)={\mathcal{N}}^{{\scriptscriptstyle{({\rm
s})}}}([0,t])$ is the number of successfully delivered messages during the
time interval $[0,t]$. We put
$\sigma_{i}=\widetilde{T}_{i}-\widetilde{T}_{i-1}$, and we register the number

$A_{i}=\\#\\{\text{attempts
during}\;(\widetilde{T}_{i-1},\widetilde{T}_{i}]\\}=\sum_{j\in\mathbb{N}}{\mathchoice{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.5mu\mathrm{l}}{1\mskip-5.0mu\mathrm{l}}}\\{T_{j}\in(\widetilde{T}_{i-1},\widetilde{T}_{i}]\\}={\mathcal{N}}\big{(}(\widetilde{T}_{i-1},\widetilde{T}_{i}]\big{)}\in\mathbb{N}$

of sending attempts in the time interval
$(\widetilde{T}_{i-1},\widetilde{T}_{i}]$. Then we have, for any
$k\in\mathbb{N}$ and $t\in[0,\infty)$,

$\mbox{on the event }\\{\widetilde{T}_{k}\leq t<\widetilde{T}_{k+1}\\},\qquad
S(t)=k\quad\mbox{and}\quad\sum_{i=1}^{k}A_{i}\leq A(t)<\sum_{i=1}^{k+1}A_{i}.$
(3.1)

Hence, we are able to express the main quantities, $A(t)$ and $S(t)$, in terms
of the sequence $(A_{i},\sigma_{i})_{i\in\mathbb{N}}$ whose state space is
equal to

$\Sigma=\mathbb{N}\times(0,\infty).$

Therefore, we want to describe its distribution. It turns out that it is in
general not a Markov chain, but a $(\kappa-1)$-Markov chain, i.e., a
stochastic process with a memory of length $\leq\kappa-1$:

######  Lemma 3.1 (Markovian structure of
$(A_{i},\sigma_{i})_{i\in\mathbb{N}}$ in CSMA case).

The sequence $(A_{i},\sigma_{i})_{i\in\mathbb{N}}$ is a time-homogeneous
$(\kappa-1)$-Markov chain with kernel $W_{\rm CSMA}$ from $\Sigma^{\kappa-1}$
to $\Sigma$ defined by

$W_{\rm
CSMA}\big{(}\big{(}(a_{1},t_{1}),\cdots,(a_{\kappa-1},t_{\kappa-1})\big{)},(k,{\rm
d}s)\big{)}=\frac{(\lambda\gamma)^{k-1}}{(k-1)!}\lambda{\operatorname{e}}^{-\lambda
s}{\mathchoice{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.5mu\mathrm{l}}{1\mskip-5.0mu\mathrm{l}}}_{[\gamma,\infty)}(s)\,{\rm
d}s,$

where $\gamma=[1-\sum_{k=1}^{\kappa-1}t_{k}]_{+}$.

###### Proof.

Let us fix $i\in\mathbb{N}$ and identify the conditional distribution of
$(A_{i+1},\sigma_{i+1})$ given $(A_{j},\sigma_{j})_{j\leq i}$. This will turn
out to be the same as the conditional distribution given the $(\kappa-1)$-past
$(A_{j},\sigma_{j})_{j\in\\{i-\kappa+2,\dots,i\\}}$, and $W_{\rm CSMA}$ will
turn out to be a version of this conditional distribution; this will finish
the proof of the lemma.

Conditioning on $(A_{j},\sigma_{j})_{j\leq i}$ includes conditioning on
$(\widetilde{T}_{j})_{j\leq i}=(T_{k(j)})_{j\leq i}$. The next arrival time
$T_{j}$ with an idle channel after time $\widetilde{T}_{i}$ is the first
$T_{j}$ after $\widetilde{T}_{i}$ such that no more than $\kappa-1$ messages
are in the $\kappa$ channels at this time. Since all the messages that are
currently in the system have arrived in the last time unit before, we can say
that this next $T_{j}$ is the first $T_{j}$ after $\widetilde{T}_{i}$ such
that in the time interval $(T_{j}-1,T_{j})$ the number of the
$\widetilde{T}_{k}$ is smaller than $\kappa$. In formulas,

$\displaystyle\widetilde{T}_{i+1}=T_{k(i+1)}$
$\displaystyle=\inf\\{T_{j}\colon
j>k(i),{\mathcal{N}}^{{\scriptscriptstyle{({\rm
s})}}}((T_{j}-1,T_{j}))<\kappa\\}$ $\displaystyle=\inf\\{T_{j}\colon
j>k(i),T_{j}-\widetilde{T}_{i-\kappa+1}>1\\}.$

In terms of the time differences, we see that
$\sigma_{i+1}=\tau_{k(i)+1}+\tau_{k(i)+2}+\dots+\tau_{k(i+1)}$ with

$k(i+1)=\inf\Big{\\{}j>k(i)\colon\tau_{k(i)+1}+\tau_{k(i)+2}+\dots+\tau_{j}>\gamma_{i}\Big{\\}},\quad\mbox{where
}\gamma_{i}=\Big{[}1-\sum_{k=0}^{\kappa-2}\sigma_{i-k}\Big{]}_{+}.$

In other words, given $(\sigma_{j})_{j\leq i}$, the conditional distribution
of $\sigma_{i+1}$ is equal to the first point of a PPP$(\lambda)$ after time
$\gamma_{i}$. Using the well-known memoryless property of the PPP, we see that
this distribution is the distribution of $\gamma_{i}+X$, where $X$ is an
independent Exp$(\lambda)$-distributed random variable. This distribution has
the density
$s\mapsto\lambda{\operatorname{e}}^{-(s-\gamma_{i})\lambda}{\mathchoice{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.5mu\mathrm{l}}{1\mskip-5.0mu\mathrm{l}}}_{[\gamma_{i},\infty)}(s)$.

We also see that $A_{i+1}-1$, the number of unsuccessful sending attempts in
the time interval $(\widetilde{T}_{i},\widetilde{T}_{i+1}]$, has the
conditional distribution equal to the one of ${\mathcal{N}}((0,\gamma_{i}])$,
the Poisson distribution with parameter $\lambda\gamma_{i}$. Hence, the
conditional probability that $A_{i+1}=k$ is equal to
${\operatorname{Poi}}_{\lambda\gamma_{i}}(k-1)={\operatorname{e}}^{-\lambda\gamma_{i}}\frac{(\lambda\gamma_{i})^{k-1}}{(k-1)!}$.

Summarizing, we see that $(A_{i+1},\sigma_{i+1})$ given
$(A_{j},\sigma_{j})_{j\leq i}$ depends only on the $(\kappa-1)$-past, i.e., on
$(A_{j},\sigma_{j})_{j\in\\{i-\kappa+2,\dots,i\\}}$ and that

$\displaystyle\mathbb{P}$ $\displaystyle\big{(}(A_{i+1},\sigma_{i+1})\in{\rm
d}(k,s)\mid(A_{i},\sigma_{i})=(a_{1},t_{1}),\cdots,(A_{i-\kappa+2},\sigma_{i-\kappa+2})=(a_{\kappa-1},t_{\kappa-1})\big{)}$
(3.2)
$\displaystyle=\frac{(\lambda\gamma)^{k-1}}{(k-1)!}\lambda{\operatorname{e}}^{-\lambda
s}{\mathchoice{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.5mu\mathrm{l}}{1\mskip-5.0mu\mathrm{l}}}_{[\gamma,\infty)}(s)\,{\rm
d}s,$

where $\gamma=[1-\sum_{k=1}^{\kappa-1}t_{k}]_{+}$. Hence,
$(A_{i},\sigma_{i})_{i\in\mathbb{N}}$ is a $(\kappa-1)$-Markov chain with the
kernel given in (1.5). $\square$

The fact that $(A_{i},\sigma_{i})_{i\in\mathbb{N}}$ is a $(\kappa-1)$-Markov
chain can obviously also be rephrased in terms of the sequence of subsequent
$(\kappa-1)$-vectors:

######  Corollary 3.2.

Equivalently, one can formulate Lemma 3.1 by saying that the vectors

$R_{i}^{{\scriptscriptstyle{({\rm
CSMA})}}}:=\big{(}(A_{i},\sigma_{i}),\cdots,(A_{i+\kappa-2},\sigma_{i+\kappa-2})\big{)}\in\Sigma^{\kappa-1}$
(3.3)

form a time-homogeneous Markov chain $(R_{i}^{{\scriptscriptstyle{({\rm
CSMA})}}})_{i\in\mathbb{N}}$ on the state space $\Sigma^{\kappa-1}$ with the
transition kernel $P_{\rm CSMA}$ defined by

$\displaystyle P_{\rm CSMA}\big{(}\big{(}($ $\displaystyle
a_{1},t_{1}),\cdots,(a_{\kappa-1},t_{\kappa-1})\big{)},{\rm
d}\big{(}(b_{1},s_{1}),\cdots,(b_{\kappa-1},s_{\kappa-1})\big{)}\big{)}$ (3.4)
$\displaystyle=\bigotimes_{i=1}^{\kappa-2}\delta_{(a_{i+1},t_{i+1})}({\rm
d}(b_{i},s_{i}))\,\otimes W_{\rm
CSMA}\big{(}\big{(}(a_{1},t_{1}),\cdots,(a_{\kappa-1},t_{\kappa-1})\big{)},{\rm
d}(b_{\kappa-1},s_{\kappa-1})\big{)}.$

In Section 4 we will need the following strong ergodicity property of the
Markov chain $(R_{i}^{{\scriptscriptstyle{({\rm CSMA})}}})_{i\in\mathbb{N}}$.
By $P^{i}$ we denote the $i$-th power of $P$ (in the sense of ‘matrix’
multiplication), i.e., the $i$-step transition kernel, for $i\in\mathbb{N}$.

Condition (U).We say, a Markov chain in a Polish space $\Sigma$ with
transition kernel $P$ satisfies (U) if there exist $\ell,N\in\mathbb{N}$
satisfying $\ell\leq N$ and a constant $M\in[1,\infty)$ such that

$P^{\ell}(\sigma,\cdot)\leq\frac{M}{N}\sum_{i=1}^{N}P^{i}(\tau,\cdot),\qquad\sigma,\tau\in\Sigma.$
(3.5)

Condition (U) is a kind of uniform ergodicity property. It implies that the
Markov chain has a unique invariant measure [DZ10, Ex. 6.5.8].

######  Lemma 3.3 (Uniform ergodicity of $(R_{i}^{{\scriptscriptstyle{({\rm
CSMA})}}})_{i\in\mathbb{N}}$).

For any $\lambda\in(0,\infty)$ and $\kappa\in\mathbb{N}$, the Markov chain
$(R_{i}^{{\scriptscriptstyle{({\rm CSMA})}}})_{i\in\mathbb{N}}$ introduced in
Corollary 3.2 satisfies (U).

###### Proof.

Instead of the transition kernel $P_{\rm CSMA}$, it will be sufficient to work
with the kernel $W_{\rm CSMA}$. We write $W_{\rm
CSMA}^{{\scriptscriptstyle{({i})}}}$ for the $i$-th power of the kernel
$W_{\rm CSMA}$. We will show the existence of a constant $\widetilde{M}$ such
that

$\displaystyle W_{\rm
CSMA}^{{\scriptscriptstyle{({\kappa+1})}}}\big{(}(a,t),(k,{\rm
d}s)\big{)}/{\rm d}s\leq\widetilde{M}\,W_{\rm
CSMA}^{{\scriptscriptstyle{({\kappa+1})}}}\big{(}(\widetilde{a},\widetilde{t}),(k,{\rm
d}s)\big{)}/{\rm d}s$ (3.6)

for
$a,\widetilde{a}\in\mathbb{N}^{\kappa-1},t,\widetilde{t}\in(0,\infty)^{\kappa-1},k\in\mathbb{N},s\in(0,\infty)$.
It is clear that (U) follows from that assertion with $\ell=N=\kappa+1$ and
$M=\widetilde{M}(\kappa+1)$.

From (1.5) we see that actually both sides of (3.6) do not depend on $a$ nor
on $\widetilde{a}$. We write both sides of (3.6) in terms of random variables,
more precisely in terms of a $(\kappa-1)$-Markov chain
$(\sigma_{i})_{i\in\\{-\kappa+2,-\kappa+3,\dots\\}}$ using the notation
$\mathbb{E}_{t}(\cdot)=\mathbb{E}(\cdot|\sigma_{-\kappa+i+1}=t_{i}\forall
i\in[\kappa-1])$, and then we have

$W_{\rm CSMA}^{{\scriptscriptstyle{({\kappa+1})}}}\big{(}(a,t),(k,{\rm
d}s)\big{)}/{\rm d}s=\frac{\lambda^{k}}{(k-1)!}{\operatorname{e}}^{-\lambda
s}\mathbb{E}_{t}\big{[}\gamma^{k-1}{\mathchoice{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.5mu\mathrm{l}}{1\mskip-5.0mu\mathrm{l}}}_{[0,s]}(\gamma)\big{]},\qquad\mbox{where
}\gamma=\Big{(}1-\sum_{i=2}^{\kappa}\sigma_{i}\Big{)}_{+}.$

Hence, (3.6) is equivalent to

$\mathbb{E}_{t}\big{[}\gamma^{k-1}{\mathchoice{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.5mu\mathrm{l}}{1\mskip-5.0mu\mathrm{l}}}_{[0,s]}(\gamma)\big{]}\leq
M\mathbb{E}_{\widetilde{t}}\big{[}\gamma^{k-1}{\mathchoice{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.5mu\mathrm{l}}{1\mskip-5.0mu\mathrm{l}}}_{[0,s]}(\gamma)\big{]},\qquad
t,\widetilde{t}\in(0,\infty)^{\kappa-1},k\in\mathbb{N},s\in(0,\infty).$ (3.7)

We are going to find a lower bound for the expectation on the right by
restricting to the event $\\{\sigma_{1}>1\\}$, on which
$\sigma_{2},\dots,\sigma_{\kappa}$ are independent ${\rm
Exp}_{\lambda}$-distributed variables (this reflects the fact that, if for
more than one time unit no new message arrives, then all channels are empty
and the next $\kappa$ incoming messages will find a free channel).
Furthermore, we will derive an upper bound for the left-hand side in terms of
a multiple integral involving such random variables.

Note that

$\mathbb{E}_{t}\big{[}\gamma^{k-1}{\mathchoice{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.5mu\mathrm{l}}{1\mskip-5.0mu\mathrm{l}}}_{[0,s]}(\gamma)\big{]}=\int_{(1-s)_{+}}^{1}{\rm
d}x\,(1-x)^{k-1}\mathbb{P}_{t}\Big{(}\sum_{i=2}^{\kappa}\sigma_{i}\in{\rm
d}x\Big{)}\big{/}{\rm d}x.$

Introduce the probability density
$f_{\gamma}(s)=\lambda{\operatorname{e}}^{-\lambda(s-\gamma)}{\mathchoice{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.5mu\mathrm{l}}{1\mskip-5.0mu\mathrm{l}}}_{[\gamma,\infty)}(s)$
on $[0,\infty)$. Then a density of $\sum_{i=2}^{\kappa}\sigma_{i}$ under
$\mathbb{E}_{(t_{2},t_{3},\dots,t_{\kappa-1},s_{1})}$ is the map

$(0,\infty)\ni x\mapsto\int_{(0,\infty)^{\kappa-1}}{\rm d}s_{2}\dots\rm
ds_{\kappa}\,{\mathchoice{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.5mu\mathrm{l}}{1\mskip-5.0mu\mathrm{l}}}\Big{\\{}\sum_{i=2}^{\kappa}s_{i}=x\Big{\\}}\prod_{i=1}^{\kappa-1}f_{\gamma_{i}}(s_{i}),\qquad\mbox{with
}\gamma_{i}=\Big{(}1-\sum_{j=-\kappa+2+i}^{i-1}s_{j}\Big{)}_{+},$

where we put $s_{-\kappa+j}=t_{j}$. Now we estimate
$f_{\gamma}(s)\leq{\operatorname{e}}^{\lambda}f_{0}(s)$, then the above
density is upper-bounded by
${\operatorname{e}}^{\lambda(\kappa-1)}f_{0}^{\star(\kappa-1)}(x)$, where
$f_{0}^{\star(\kappa-1)}$ is the $(\kappa-1)$-fold convolution of $f_{0}$.
This implies that

$\mathbb{E}_{t}\big{[}\gamma^{k-1}{\mathchoice{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.5mu\mathrm{l}}{1\mskip-5.0mu\mathrm{l}}}_{[0,s]}(\gamma)\big{]}\leq{\operatorname{e}}^{\lambda(\kappa-1)}\int_{(1-s)_{+}}^{1}{\rm
d}x\,(1-x)^{k-1}f_{0}^{\star(\kappa-1)}(x).$

On the other hand, we may estimate

$\displaystyle\mathbb{E}_{\widetilde{t}}\big{[}\gamma^{k-1}{\mathchoice{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.5mu\mathrm{l}}{1\mskip-5.0mu\mathrm{l}}}_{[0,s]}(\gamma)\big{]}$
$\displaystyle\geq\mathbb{E}_{\widetilde{t}}\big{[}{\mathchoice{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.5mu\mathrm{l}}{1\mskip-5.0mu\mathrm{l}}}\\{\sigma_{1}>1\\}\gamma^{k-1}{\mathchoice{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.5mu\mathrm{l}}{1\mskip-5.0mu\mathrm{l}}}_{[0,s]}(\gamma)\big{]}$
$\displaystyle=\mathbb{P}_{\widetilde{t}}(\sigma_{1}>1)\int_{(1-s)_{+}}^{1}{\rm
d}x\,(1-x)^{k-1}\mathbb{P}_{t}\Big{(}\sum_{i=2}^{\kappa}\sigma_{i}\in{\rm
d}x\Big{)}\big{/}{\rm d}x$
$\displaystyle\geq{\operatorname{e}}^{-\lambda}\int_{(1-s)_{+}}^{1}{\rm
d}x\,(1-x)^{k-1}f_{0}^{\star(\kappa-1)}(x).$

The last two displays together imply our goal, (3.7), and hence (3.6).
$\square$

###  3.2. Markov approach for the ALOHA protocol

Now we turn to a similar treatment of the ALOHA protocol. We adopt all the
notation from Section 3.1; that is, we fix $\lambda\in(0,\infty)$ and
$\kappa\in\mathbb{N}$ and assume that $(T_{i})_{i\in\mathbb{N}}$ is a standard
PPP($\lambda$) (the sequence of times at which a message comes in and requires
a channel for being transmitted) and ${\mathcal{N}}((a,b])$ is the number of
Poisson points in the time interval $(a,b]$ for any $a<b$.

Recall that, in the ALOHA protocol, each incoming message jumps into a
randomly picked one of the $\kappa$ channels, regardless whether it is idle or
busy. If it is busy, then it destroys the message that is currently in the
channel and itself as well. As a consequence, the new message is rejected
immediately, i.e., it does not get access to the system, while the old one
first remains in the channel until its service time is over and leaves after
one time unit without having been successfully delivered. However, if the
channel is idle, then the new message is only _potentially_ successful, since
it can still be destroyed during the service time by a new arriving one that
picks this channel. This uncertain situation remains until one time unit after
the entry into the channel; then the message is successfully delivered if it
has not been cancelled by then.

We consider the sequence $(\widetilde{T}_{i})_{i\in\mathbb{N}}$ of all the
times at which an incoming message picks an idle channel, a subsequence of
$(T_{i})_{i\in\mathbb{N}}$. We again put
$\sigma_{i}=\widetilde{T}_{i}-\widetilde{T}_{i-1}$ and
$A_{i}=A((\widetilde{T}_{i-1},\widetilde{T}_{i}])$, which is $1+$ the number
of incoming messages that jump into some busy channel and therefore destroy
the message therein. Recall that $\Sigma=\mathbb{N}\times(0,\infty)$.

######  Lemma 3.4 (Markovian structure of
$(A_{i},\sigma_{i})_{i\in\mathbb{N}}$ in ALOHA case).

The sequence $(A_{i},\sigma_{i})_{i\in\mathbb{N}}$ is a $(\kappa-1)$-Markov
chain with kernel $W_{\rm ALOHA}$ from $\Sigma^{\kappa-1}$ to $\Sigma$ defined
by

$W_{\rm
ALOHA}\big{(}\big{(}(a_{1},t_{1}),\cdots,(a_{\kappa-1},t_{\kappa-1})\big{)},(k,{\rm
d}s)\big{)}=\frac{\big{(}\gamma+\frac{B(s)}{\kappa}\big{)}^{k-1}}{(k-1)!}\left(1-\frac{\beta(s)}{\kappa}\right)\lambda^{k}{\operatorname{e}}^{-\lambda
s}{\mathchoice{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.5mu\mathrm{l}}{1\mskip-5.0mu\mathrm{l}}}_{[\gamma_{i},\infty)}(s)\,{\rm
d}s,$

where we wrote $\gamma:=[1-\sum_{k=1}^{\kappa-1}t_{k}]_{+}$ and

$\displaystyle\beta(s):=\max\Big{\\{}m\in\mathbb{N}\colon
s+\sum_{j=0}^{m-2}t_{\kappa-1-j}\leq
1\Big{\\}}\wedge\kappa\in\\{0,1,\dots,\kappa\\}\qquad\mbox{and}\qquad
B(s)=\int_{0}^{s}\beta(r)\,{\rm d}r$ (3.8)

for the number of busy channels $s$ time unit after the last successful
arrival and its primitive.

###### Proof.

We keep $i\in\mathbb{N}$ fixed, condition on $(A_{j},\sigma_{j})_{j\leq i}$
and examine the distribution of $(A_{i+1},\sigma_{i+1})$. Let us first examine
the density of the probability of the event $\\{\sigma_{i+1}=s\\}$. At time
$\widetilde{T}_{i+1}$ there is at least one free channel in order for the
arriving message to access the system. Hence, $\widetilde{T}_{i+1}$ must be
after time $\widetilde{T}_{i}+\gamma_{i}$ , where
$\gamma_{i}:=[1-\sum_{n=i-\kappa+2}^{i}\sigma_{n}]_{+}$, like in the CSMA
model, that is, $\sigma_{i+1}>\gamma_{i}$. However, this time
$\widetilde{T}_{i+1}$ is not necessarily the first point of the PPP after
$\widetilde{T}_{i}+\gamma_{i}$, but the first Poisson point after
$\widetilde{T}_{i}+\gamma_{i}$ at which an idle channel is picked. Hence, we
have to calculate the probability of picking a free channel at an Poisson time
point. For this, we need to know the number of free channels at any arbitrary
time after $\widetilde{T}_{i}+\gamma_{i}$.

So let $\widetilde{T}_{i}+s$, $s>\gamma_{i}$, be this arbitrary time. If
$s>1$, at least one time unit has passed without new incoming messages after
$\widetilde{T}_{i}$, which means that all channels are idle again at
$\widetilde{T}_{i}+s$. If $s\leq 1$, at least one channel is busy at time
$\widetilde{T}_{i}+s$, as there is at least one message, namely the one
arrived at $\widetilde{T}_{i}$, whose service time is not over yet. Of course,
there could be more messages still remaining in the system, depending on $s$,
and we have to determine this relation. It is clear, that if additionally
$s+\sigma_{i}\leq 1$, then the messages arrived at $\widetilde{T}_{i-1}$ is
also still in the system, so there are at least two busy channels at time
$\widetilde{T}_{i}+s$. Analogously, there must be at least 3 occupied
channels, if $s+\sigma_{i}+\sigma_{i-1}\leq 1$ additionally, as the service
time of the message arrived at $\widetilde{T}_{i-2}$ is also not over yet. We
see step by step, that if $s+\sum_{k=0}^{\kappa-3}\sigma_{i-k}\leq 1$, we have
at least $\kappa-1$ busy channels and if
$s+\sum_{k=0}^{\kappa-2}\sigma_{i-k}\leq 1$, all $k$ channels must be busy, as
the delivery of all the last $k$ messages is still remaining. Hence, the
number of busy channels at time $\widetilde{T}_{i}+s$ is given, for
$s>\gamma_{i}$, by

$\beta(s):={\mathchoice{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.5mu\mathrm{l}}{1\mskip-5.0mu\mathrm{l}}}_{\\{s\leq
1\\}}+{\mathchoice{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.5mu\mathrm{l}}{1\mskip-5.0mu\mathrm{l}}}_{\\{s+\sigma_{i}\leq
1\\}}+\cdots+{\mathchoice{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.5mu\mathrm{l}}{1\mskip-5.0mu\mathrm{l}}}_{\\{s+\sum_{k=0}^{\kappa-2}\sigma_{i-k}\leq
1\\}}=\max\Big{\\{}m\in\mathbb{N}\colon s+\sum_{k=0}^{m-2}\sigma_{i-k}\leq
1\Big{\\}}\wedge\kappa.$ (3.9)

Then it is clear that the probability of picking randomly a busy respectively
free channel at time $\widetilde{T}_{i}+s$ is equal to
$\frac{\beta(s)}{\kappa}$ respectively $1-\frac{\beta(s)}{\kappa}$. So the
first point of the PPP after $\widetilde{T}_{i}+\gamma_{i}$ coincides only
with probability $1-\frac{\beta(s)}{\kappa}$ with $\widetilde{T}_{i+1}$ (on
the event $\\{\sigma_{i+1}=s\\}$). This yields the density

$\displaystyle
s\mapsto\Big{(}1-\frac{\beta(s)}{\kappa}\Big{)}\lambda{\operatorname{e}}^{-\lambda(s-\gamma_{i})}{\mathchoice{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.5mu\mathrm{l}}{1\mskip-5.0mu\mathrm{l}}}_{[\gamma_{i},\infty)}(s)$

for the probability that the first message after time
$\widetilde{T}_{i}+\gamma_{i}$ picks a free channel.

Now we consider, for any $n\in\mathbb{N}$, the event that
$\widetilde{T}_{i+1}=\widetilde{T}_{i}+s$ is the $n$-th point of the PPP after
$\widetilde{T}_{i}+\gamma_{i}$ at which for the first time an idle channel is
picked. On the event that there are precisely $n-1$ Poisson points in the
interval $(\widetilde{T}_{i}+\gamma_{i},\widetilde{T}_{i+1})$ and another one
at $\widetilde{T}_{i+1}=\widetilde{T}_{i}+s$, the density of these $n$ Poisson
points is equal to

$(s_{1},\dots,s_{n-1},s)\mapsto{\mathchoice{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.5mu\mathrm{l}}{1\mskip-5.0mu\mathrm{l}}}_{\\{\gamma_{i}<s_{1}<s_{2}<\dots<s_{n-1}<s\\}}\lambda^{n}{\operatorname{e}}^{-\lambda(s-\gamma_{i})}\,{\rm
d}s_{1}\cdots{\rm d}s_{n-1}{\rm d}s.$

On this event, the probability that the first $n-1$ of them pick a busy
channel and the last one an idle one is equal to

$\displaystyle\Big{(}1-\frac{\beta(s)}{\kappa}\Big{)}\prod_{k=1}^{n-1}\frac{\beta(s_{k})}{\kappa}.$

In order to obtain the density of $\sigma_{i+1}$, we need to integrate over
all these $s_{1},\dots,s_{n-1}$ and have to sum on $n\in\mathbb{N}$. Hence,
the conditional distribution of $\sigma_{i+1}$ is given as

$\displaystyle\mathbb{P}$ $\displaystyle(\sigma_{i+1}\in{\rm
d}s\mid(A_{j},\sigma_{j})_{j\leq i})$
$\displaystyle=\sum_{n=1}^{\infty}\Big{[}\int_{\gamma_{i}<s_{1}<s_{2}<\dots<s_{n-1}<s}\Big{(}\prod_{k=1}^{n-1}\frac{\beta(s_{k})}{\kappa}\Big{)}\,{\rm
d}s_{1}{\rm d}s_{2}\dots,{\rm
d}s_{n-1}\Big{]}\,\Big{(}1-\frac{\beta(s)}{\kappa}\Big{)}\lambda^{n}{\operatorname{e}}^{-\lambda(s-\gamma_{i})}\,{\rm
d}s$
$\displaystyle=\sum_{n=1}^{\infty}\frac{1}{(n-1)!}\Big{[}\int_{0}^{s}\frac{\beta(r)}{\kappa}\,{\rm
d}r\Big{]}^{n-1}\left(1-\frac{\beta(s)}{\kappa}\right)\lambda^{n}{\operatorname{e}}^{-\lambda(s-\gamma_{i})}{\mathchoice{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.5mu\mathrm{l}}{1\mskip-5.0mu\mathrm{l}}}_{[\gamma_{i},\infty)}(s)\,{\rm
d}s$ $\displaystyle={\operatorname{e}}^{\lambda
B(s)/\kappa}\left(1-\frac{\beta(s)}{\kappa}\right)\lambda{\operatorname{e}}^{-\lambda(s-\gamma_{i})}{\mathchoice{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.5mu\mathrm{l}}{1\mskip-5.0mu\mathrm{l}}}_{[\gamma_{i},\infty)}(s)\,{\rm
d}s,$

where we used the exponential series and remind on (3.8), now with
$\gamma_{i}$ instead of $\gamma$ (observe that $\beta(s)=0$ on
$[0,\gamma_{i}]$).

Now, we look at the intersection of $\\{\sigma_{i+1}=s\\}$ with the event
$\left\\{A_{i+1}=k\right\\}$ for $k\in\mathbb{N}$. Here we have $k-1$
unsuccessful attempts during $(\widetilde{T}_{i},\widetilde{T}_{i+1}]$; indeed
these are all the Poisson points in the interval
$(\widetilde{T}_{i},\widetilde{T}_{i}+\gamma_{i}]$ plus the ones in the
interval $(\widetilde{T}_{i}+\gamma_{i},\widetilde{T}_{i+1})$ that failed to
pick an idle channel, and these two numbers are independent by the properties
of the PPP. The number of the first ones have a Poisson distribution with
parameter $\lambda\gamma_{i}$, and the one of the latter ones has been
examined above. Hence, the conditional distribution of $A_{i+1}$ is the
convolution of these two:

$\displaystyle\mathbb{P}$ $\displaystyle\big{(}A_{i+1}=k,\sigma_{i+1}\in{\rm
d}s\mid(A_{j},\sigma_{j})_{j\leq i}\big{)}$
$\displaystyle=\sum_{n=1}^{k}\frac{(\lambda\gamma_{i})^{k-n}}{(k-n)!}{\operatorname{e}}^{-\lambda\gamma_{i}}\left(1-\frac{\beta(s)}{\kappa}\right)\frac{B(s)^{n-1}/(n-1)!}{\kappa^{n-1}}\lambda^{n}{\operatorname{e}}^{-\lambda(s-\gamma_{i})}{\mathchoice{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.5mu\mathrm{l}}{1\mskip-5.0mu\mathrm{l}}}_{[\gamma_{i},\infty)}(s)\,{\rm
d}s$
$\displaystyle=\gamma_{i}^{k-1}\sum_{n=1}^{k}\frac{(B(s)/\gamma_{i}\kappa)^{n-1}}{(k-n)!(n-1)!}\left(1-\frac{\beta(s)}{\kappa}\right)\lambda^{k}{\operatorname{e}}^{-\lambda
s}{\mathchoice{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.5mu\mathrm{l}}{1\mskip-5.0mu\mathrm{l}}}_{[\gamma_{i},\infty)}(s)\,{\rm
d}s$
$\displaystyle=\frac{\gamma_{i}^{k-1}}{(k-1)!}\Big{(}1+\frac{B(s)}{\gamma_{i}\kappa}\Big{)}^{k-1}\left(1-\frac{\beta(s)}{\kappa}\right)\lambda^{k}{\operatorname{e}}^{-\lambda
s}{\mathchoice{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.5mu\mathrm{l}}{1\mskip-5.0mu\mathrm{l}}}_{[\gamma_{i},\infty)}(s)\,{\rm
d}s$ $\displaystyle=W_{\rm
ALOHA}\big{(}\big{(}(a_{1},t_{1}),\cdots,(a_{\kappa-1},t_{\kappa-1})\big{)},(k,{\rm
d}s)\big{)}\big{)},$

where we used the binomial theorem. In particular, we see that we have again a
$(\kappa-1)$-Markov chain, as the transition probaility depends only on
$\sigma_{i},\dots,\sigma_{i-\kappa+2}$ (and by the way, not at all on the
$A_{j}$’s). $\square$

Analogously to the CSMA case in Section 3.1, the sequence of
$(\kappa-1)$-vectors $R_{i}^{{\scriptscriptstyle{({\rm ALOHA})}}}$ of
$(A_{i},\sigma_{i})_{i\in\mathbb{N}}$ defined as in (3.3) form a Markov chain
on the state space $\Sigma^{\kappa-1}$ with a transition kernel $P_{\rm
ALOHA}$ that is defined analogously to (3.4). Also the analogue to Lemma 3.3
holds:

######  Lemma 3.5 (Uniform ergodicity of $(R_{i}^{{\scriptscriptstyle{({\rm
ALOHA})}}})_{i\in\mathbb{N}}$).

For the ALOHA protocol, for any $\lambda\in(0,\infty)$ and
$\kappa\in\mathbb{N}$, the Markov chain $(R_{i}^{{\scriptscriptstyle{({\rm
ALOHA})}}})_{i\in\mathbb{N}}$ satisfies (U).

###### Proof.

We use the same strategy as in the proof of Lemma 3.3 and will prove that
(3.6) holds for some $\widetilde{M}$. Again abbreviate
$\mathbb{E}_{t}(\cdot)=\mathbb{E}(\cdot|\sigma_{-\kappa+i+1}=t_{i}\forall
i\in[\kappa-1])$ for $t=(t_{1},\cdots,t_{\kappa-1})\in(0,\infty)^{\kappa-1}$.
Then, using the notation
$\gamma=\left[1-\sum_{i=2}^{\kappa}\sigma_{i}\right]_{+}$ and

$\displaystyle\beta^{{\scriptscriptstyle{({\sigma})}}}(s):={\mathchoice{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.5mu\mathrm{l}}{1\mskip-5.0mu\mathrm{l}}}_{[\gamma,\infty)}(s)\,\max\Big{\\{}m\colon
s+\sum_{i=0}^{m-2}\sigma_{\kappa-i}\leq 1\Big{\\}}\wedge\kappa$

we can write

$\displaystyle W_{\rm
ALOHA}^{{\scriptscriptstyle{({\kappa+1})}}}\big{(}(a,t),(k,{\rm
d}s)\big{)}/{\rm
d}s=\frac{\lambda^{k}}{(k-1)!}\left(1-\frac{\beta(s)}{k}\right)e^{-\lambda
s}\mathbb{E}_{t}\left[\left(\gamma+\frac{\beta^{{\scriptscriptstyle{({\sigma})}}}(s)}{\kappa}\right)^{k-1}{\mathchoice{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.5mu\mathrm{l}}{1\mskip-5.0mu\mathrm{l}}}_{[0,s]}(\gamma)\right];$

observe that $\beta^{{\scriptscriptstyle{({\sigma})}}}(s)$ and $\gamma$ are
also functions of the random variables $\sigma_{2},\cdots,\sigma_{\kappa}$.

For our goal it is sufficient to show the existence of some $\widetilde{M}>0$
such that, for each $t,\tilde{t}\in(0,\infty)^{\kappa-1}$, $s>0$,
$k\in\mathbb{N}$ and $n\leq k$

$\displaystyle\mathbb{E}_{t}\big{[}G(\sigma_{2},\dots,\sigma_{\kappa})\big{]}\leq\widetilde{M}\mathbb{E}_{\tilde{t}}\big{[}G(\sigma_{2},\dots,\sigma_{\kappa})\big{]},\qquad\mbox{for
}G(\sigma_{2},\dots,\sigma_{\kappa})=\left(\gamma+\frac{\beta^{{\scriptscriptstyle{({\sigma})}}}(s)}{\kappa}\right)^{k-1}{\mathchoice{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.5mu\mathrm{l}}{1\mskip-5.0mu\mathrm{l}}}_{[0,s]}(\gamma).$

We will show this even for any non-negative measurable function $G$ (with the
same constant $\widetilde{M}$) by showing the corresponding inequality for the
respective densities of $(\sigma_{2},\dots,\sigma_{\kappa})$ under
$\mathbb{P}_{t}$ and $\mathbb{P}_{\widetilde{t}}$.

Recall the probability density
$f_{g}(s)=\lambda{\operatorname{e}}^{-\lambda(s-g)}{\mathchoice{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.5mu\mathrm{l}}{1\mskip-5.0mu\mathrm{l}}}_{[g,\infty)}(s)$
on $s\in[0,\infty)$ for any $g\in[0,\infty)$. Now, a density of
$(\sigma_{2},\dots,\sigma_{\kappa})$ under
$\mathbb{E}_{(t_{2},t_{3},\cdots,t_{\kappa-1},s_{1})}$ is the map

$(s_{2},\dots,s_{\kappa})\mapsto\prod_{i=1}^{\kappa-1}f_{\gamma_{i}}(s_{i}),$
(3.10)

where we wrote $s_{-\kappa+j}=t_{j}$ and
$\gamma_{i}:=[1-\sum_{j=-\kappa+2+i}^{i-1}s_{j}]_{+}$. Since
$f_{g}(s)\leq{\operatorname{e}}^{\lambda}f_{0}(s)$ for any $g,s\in[0,\infty)$,
this density is upper bounded by
${\operatorname{e}}^{\lambda(\kappa-1)}f_{0}^{\otimes(\kappa-1)}(s_{2},\dots,s_{\kappa})$,
where $f_{0}^{\otimes(\kappa-1)}$ is the $(\kappa-1)$-fold tensor product of
$f_{0}$. Then we can upper bound the left-hand side as follows (the
expectation after the first equality is on $\sigma_{1}$):

$\displaystyle\mathbb{E}_{t}\big{[}G(\sigma_{2},\dots,\sigma_{\kappa})\big{]}$
$\displaystyle=\mathbb{E}_{t}\Big{[}\int_{[0,\infty)^{\kappa-1}}G(s_{2},\dots,s_{\kappa})\,\prod_{i=1}^{\kappa-1}f_{\gamma_{i}}(s_{i})\Big{]}$
$\displaystyle\leq{\operatorname{e}}^{\lambda(\kappa-1)}\mathbb{E}_{t}\Big{[}\int_{[0,\infty)^{\kappa-1}}G(s_{2},\dots,s_{\kappa})\,f_{0}^{\otimes(\kappa-1)}(s_{2},\dots,s_{\kappa})\Big{]}$
$\displaystyle={\operatorname{e}}^{\lambda(\kappa-1)}\int_{[0,\infty)^{\kappa-1}}G(s_{2},\dots,s_{\kappa})\,f_{0}^{\otimes(\kappa-1)}(s_{2},\dots,s_{\kappa}).$

On the other hand, if we restrict to the event $\\{\sigma_{1}>1\\}$, then
$\sigma_{2},\dots,\sigma_{\kappa}$ are again independent exponentially
distributed variables and independent of $\sigma_{1}$, and we can estimate

$\displaystyle\mathbb{E}_{\widetilde{t}}\big{[}G(\sigma_{2},\dots,\sigma_{\kappa})\big{]}$
$\displaystyle\geq\mathbb{E}_{\widetilde{t}}\big{[}{\mathchoice{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.5mu\mathrm{l}}{1\mskip-5.0mu\mathrm{l}}}_{\\{\sigma_{1}>1\\}}G(\sigma_{2},\dots,\sigma_{\kappa})\big{]}$
$\displaystyle=\mathbb{P}_{\widetilde{t}}(\sigma_{1}>1)\int_{[0,\infty)^{\kappa-1}}G(s_{2},\dots,s_{\kappa})\,f_{0}^{\otimes(\kappa-1)}(s_{2},\dots,s_{\kappa})\,{\rm
d}s_{2},\dots,{\rm d}s_{\kappa}.$

Since
$\mathbb{P}_{\widetilde{t}}(\sigma_{1}>1)\geq{\operatorname{e}}^{-\lambda}$,
this implies the assertion with
$\widetilde{M}={\operatorname{e}}^{\lambda\kappa}$. $\square$

##  4\. Large deviations

In this section, we prove a large deviation upper bound for the pair
$\frac{1}{t}(S(t),A(t))$ for both protocols. We can make most of the steps
jointly for both protocols. The basis of our large-deviation analysis is the
empirical pair measures and the empirical $\kappa$-string measures
$L_{n}^{\kappa}$ of the Markov chain that we introduced in Section 1.3.2. The
two LDPs for $(L_{n}^{\kappa})_{n\in\mathbb{N}}$ as $n\to\infty$ are easily
derived from general theory, and the main object, $(A(t),S(t))$ is a kind of
time-inverse of
$n\mapsto(\langle\pi_{1},L_{n}^{\kappa}\rangle,\langle\pi_{1},L_{n}^{\kappa}\rangle)$.
However, there are two problems left: The latter is a priori not a continuous
functional of $L_{n}^{\kappa}$, and we need to make the step from an LDP for
this pair to the pair $(A(t),S(t))$. These two major steps will be done in
Lemmas 4.3 and 4.4. However, we were not able to overcome the lack of
continuity of $\mu\mapsto\langle\pi_{2},\mu\rangle$ and cannot derive a full
LDP for $(A(t),S(t))$.

Let us abbreviate $\Sigma=\mathbb{N}\times(0,\infty)$ and let $*\in\\{\rm
CSMA,\rm ALOHA\\}$. We introduce the empirical pair measure of the Markov
chain $(R^{*}_{i})_{i\in\mathbb{N}_{0}}$ defined in (3.3),

$L_{n}^{{\scriptscriptstyle{({2})}}}=\frac{1}{n}\sum_{i=1}^{n}\delta_{(R^{*}_{i-1},R^{*}_{i})}\in{\mathcal{M}}_{1}(\Sigma^{\kappa-1}\times\Sigma^{\kappa-1}).$

In this expression, we assume periodic boundary conditions, i.e.,
$R^{*}_{0}=R^{*}_{n}$. Then $L_{n}^{{\scriptscriptstyle{({2})}}}$ satisfies
the marginal property: its two marginal measures are equal to each other. We
denote by ${\mathcal{M}}_{1}^{{\scriptscriptstyle{({\rm
s})}}}(\Sigma^{\kappa-1}\times\Sigma^{\kappa-1})$ the set of probability
measures $\nu$ on $\Sigma^{\kappa-1}\times\Sigma^{\kappa-1}$ that satisfy this
marginal property and write $\overline{\nu}$ for any of the two marginal
measures of $\nu$. (The assumption $R^{*}_{0}=R^{*}_{n}$ is only of technical
nature and can also be dropped without any problem, but we will not elaborate
on that minor point.)

Since $(R^{*}_{i})_{i\in\mathbb{N}_{0}}$ satisfies the condition (U) by Lemmas
3.3 and 3.5, respectively, [DS89, Exercise 4.1.48] says that there is an
invariant distribution $\nu_{*}$ of $(R^{*}_{i})_{i\in\mathbb{N}_{0}}$. Then,
by [DS89, Lemma 4.1.45] the empirical pair measures
$(L_{n}^{{\scriptscriptstyle{({2})}}})_{n\in\mathbb{N}}$ converges almost
surely towards $\bar{\nu}_{*}\otimes P_{*}$. Furthermore, we even get a good
control on the rate of this convergence: By [DZ10, Cor. 6.5.10 and Th. 6.5.12]
the empirical pair measures
$(L_{n}^{{\scriptscriptstyle{({2})}}})_{n\in\mathbb{N}}$ satisfies an LDP on
${\mathcal{M}}_{1}(\Sigma^{\kappa-1}\times\Sigma^{\kappa-1})$ with rate
function

$\nu\mapsto H(\nu\mid\overline{\nu}\otimes
P_{*})=\int_{\Sigma\times\Sigma}\nu({\rm d}R,{\rm
d}R^{\prime})\log\frac{\nu({\rm d}R,{\rm d}R^{\prime})}{\overline{\nu}({\rm
d}R)P_{*}(R,{\rm d}R^{\prime})},$ (4.1)

if $\nu\in{\mathcal{M}}_{1}^{{\scriptscriptstyle{({\rm
s})}}}(\Sigma^{\kappa-1}\times\Sigma^{\kappa-1})$ is absolutely continuous
with respect to $\overline{\nu}\otimes P_{*}$, and $\infty$ otherwise. The
term in (4.1) is called the relative entropy of $\nu$ with respect to
$\overline{\nu}\otimes P_{*}$.

The empirical pair measures $L_{n}^{{\scriptscriptstyle{({2})}}}$ stand in a
simple one-to-one correspondence with the empirical $\kappa$-string measures
that we are going to introduce now; we would like to formulate our LDP in
terms of these measures instead. Consider the set
${\mathcal{M}}_{1}^{{\scriptscriptstyle{({\rm s})}}}(\Sigma^{\kappa})$ of
probability measures $\mu$ on $\Sigma^{\kappa}$ whose first marginal measure
$\mu^{{\scriptscriptstyle{({\kappa-1})}}}$ on $\Sigma^{\kappa-1}$ (i.e., when
projected on the first $\kappa-1$ components) is equal to its second marginal
measure (i.e., when projected on the last $\kappa-1$ components). Then the
above LDP for $(L_{n}^{{\scriptscriptstyle{({2})}}})_{n\in\mathbb{N}}$ is
equivalent to saying that the empirical $\kappa$-string measure

$L_{n}^{\kappa}=\frac{1}{n}\sum_{i=0}^{n-1}\delta_{((A_{i+1},\sigma_{i+1}),\dots,(A_{i+\kappa},\sigma_{i+\kappa}))}$

satisfies an LDP on ${\mathcal{M}}_{1}(\Sigma^{\kappa})$ with rate function

$\mu\mapsto H(\mu\mid\mu^{{\scriptscriptstyle{({\kappa-1})}}}\otimes
W_{*})=\int_{\Sigma^{\kappa}}{\rm d}\mu\,\log\frac{{\rm d}\mu}{{\rm
d}(\mu^{{\scriptscriptstyle{({\kappa-1})}}}\otimes W_{*})},$ (4.2)

if $\mu\in{\mathcal{M}}_{1}^{{\scriptscriptstyle{({\rm
s})}}}(\Sigma^{\kappa})$, and $=\infty$ otherwise.

Let us first analyse the rate function. Recall the projections
$\pi_{1}\colon\Sigma^{\kappa}\to\mathbb{N}$ and
$\pi_{2}\colon\Sigma^{\kappa}\to(0,\infty)$ defined by
$\pi_{1}((a_{1},r_{1}),\dots,(a_{\kappa},r_{\kappa}))=a_{\kappa}$ and
$\pi_{2}((a_{1},r_{1}),\dots,(a_{\kappa},r_{\kappa}))=r_{\kappa}$. As a
prestep, we analyse a candidate for the rate function in an LDP for the pair
$(\langle\pi_{1},L_{n}^{\kappa}\rangle,\langle\pi_{1},L_{n}^{\kappa}\rangle)$.

######  Lemma 4.1 (An auxiliary rate function).

For $*\in\\{{\rm CSMA},{\rm ALOHA}\\}$, introduce
$J_{*}\colon[0,\infty)^{2}\to[0,\infty)$ as

$J_{*}(x,y)=\sup_{A\in\mathbb{R},B\in(-\infty,\lambda)}\inf_{\mu\in\mathcal{M}_{1}^{{\scriptscriptstyle{({s})}}}(\Sigma^{\kappa})}\big{[}A(x-\left<\pi_{1},\mu\right>)+B(y-\left<\pi_{2},\mu\right>)+H(\mu\mid\mu^{{\scriptscriptstyle{({\kappa-1})}}}\otimes
W_{*})\big{]}.$ (4.3)

Then $J_{*}$ is convex and hence continuous and possesses precisely one
minimizer $(x_{\rm min},y_{\rm min})\in(0,\infty)^{2}$.

###### Proof.

By [DS89, Theorems 4.1.43 and Lemma 4.1.45], the map $\nu\mapsto
H(\nu\mid\overline{\nu}\otimes P_{*})$ is convex and possesses the unique
minimizer $\overline{\nu}_{*}\otimes P_{*}$, where $\nu_{*}$ is the invariant
distribution of $(R^{*}_{i})_{i\in\mathbb{N}_{0}}$, whose existence is implied
by Condition (U). Hence, the map $\mu\mapsto
H(\mu\mid\mu^{{\scriptscriptstyle{({\kappa-1})}}}\otimes W_{*})$ is also
convex with the only minimizer
$\widetilde{\mu}_{*}:=\nu^{{\scriptscriptstyle{({\kappa-1})}}}_{*}\otimes
W_{*}\in{\mathcal{M}}_{1}^{{\scriptscriptstyle{({\rm s})}}}(\Sigma^{\kappa})$.
Hence, $J_{*}$ has a unique minimizer, which is equal to $(x_{\rm min},y_{\rm
min})=(\langle\pi_{1},\widetilde{\mu}_{*}\rangle,\langle\pi_{2},\widetilde{\mu}_{*}\rangle)$.
It is an easy exercise to prove the convexity of $J_{*}$, using (4.3) (observe
that it is the Legendre transform of a function that is an supremum of linear
functions). In particular, it is continuous in $(0,\infty)^{2}$, and all the
right- and the left partial derivatives exist in $(0,\infty)^{2}$. $\square$

Recall from Theorem 1.6 the rate functions

$I_{\rm
CSMA}(a,s)=\sup_{A\in\mathbb{R},B\in(-\infty,\lambda)}\inf_{\mu\in{\mathcal{M}}_{1}^{{\scriptscriptstyle{({\rm
s})}}}(\Sigma^{\kappa})}\big{[}A\left(a-s\left<\pi_{1},\mu\right>\right)+B\left(1-s\left<\pi_{2},\mu\right>\right)+H(\mu\mid\mu^{{\scriptscriptstyle{({\kappa-1})}}}\otimes
W_{\rm CSMA})\big{]}$

for the CSMA protocol and

$\displaystyle I_{\rm
ALOHA}(a,s)=\sup_{A\in\mathbb{R},B\in(-\infty,\lambda)}\inf_{\mu\in{\mathcal{M}}_{1}^{{\scriptscriptstyle{({\rm
s})}}}(\Sigma^{\kappa})}\Big{[}A\big{(}a-\textstyle{\frac{a+s}{2}}\left<\pi_{1},\mu\right>\big{)}$
$\displaystyle+B\big{(}1-\textstyle{\frac{a+s}{2}}\left<\pi_{2},\mu\right>\big{)}$
$\displaystyle+H(\mu\mid\mu^{{\scriptscriptstyle{({\kappa-1})}}}\otimes W_{\rm
ALOHA})\Big{]}$

in the case of ALOHA protocol, where $a,s\in[0,\infty)$.

######  Corollary 4.2 (Properties of $I_{\rm CSMA}$ and $I_{\rm ALOHA}$).

For both $*\in\\{{\rm CSMA},{\rm ALOHA}\\}$, $I_{*}$ is convex and hence
continuous in $(0,\infty)^{2}$ and has precisely one minimizer $(a_{\rm
min},s_{\rm min})\in(0,\infty)^{2}$ (given in (4.4) and (4.5), respectively).

###### Proof.

Observe that, for any $a,s\in[0,\infty)$,

$I_{\rm CSMA}(a,s)=sJ_{\rm
CSMA}(\textstyle{\frac{a}{s}},\textstyle{\frac{1}{s}})\qquad\mbox{and}\qquad
I_{\rm ALOHA}(a,s)=\frac{a+s}{2}J_{\rm
ALOHA}(\textstyle{\frac{2a}{a+s}},\textstyle{\frac{2}{a+s}}).$

Using this, one easily sees that $I_{*}$ is uniquely minimized in the points

$\displaystyle(a_{\rm min},s_{\rm min})=\left(\frac{x_{\rm min}}{y_{\rm
min}},\frac{1}{y_{\rm
min}}\right)=\left(\frac{\left<\pi_{1},\tilde{\nu}\right>}{\left<\pi_{2},\tilde{\nu}\right>},\frac{1}{\left<\pi_{2},\tilde{\nu}\right>}\right)$
(4.4)

in the CSMA case and

$\displaystyle(a_{\rm min},s_{\rm min})=\left(\frac{x_{\rm min}}{y_{\rm
min}},\frac{2-x_{\rm min}}{y_{\rm
min}}\right)=\left(\frac{\left<\pi_{1},\tilde{\nu}\right>}{\left<\pi_{2},\tilde{\nu}\right>},\frac{2-\left<\pi_{1},\tilde{\nu}\right>}{\left<\pi_{2},\tilde{\nu}\right>}\right)$
(4.5)

in the ALOHA case.

For showing the convexity of $I_{\rm CSMA}$ we need to show that $(a,s)\mapsto
sf(\frac{a}{s},\frac{1}{s})$ is convex if $f$ is convex. Fix
$(a_{1},s_{1}),(a_{2},s_{2})\in[0,\infty)^{2}$, then we see that

$f\big{(}\textstyle{\frac{a_{1}+a_{2}}{s_{1}+s_{2}}},\textstyle{\frac{1}{s_{1}+s_{2}}}\big{)}=f\Big{(}\textstyle{\frac{s_{1}}{s_{1}+s_{2}}}\big{(}\textstyle{\frac{a_{1}}{s_{1}}},\textstyle{\frac{1}{s_{1}}}\big{)}+\textstyle{\frac{s_{2}}{s_{1}+s_{2}}}\big{(}\textstyle{\frac{a_{2}}{s_{2}}},\textstyle{\frac{1}{s_{2}}}\big{)}\Big{)}\leq\textstyle{\frac{s_{1}}{s_{1}+s_{2}}}f\big{(}\textstyle{\frac{a_{1}}{s_{1}}},\textstyle{\frac{1}{s_{1}}}\big{)}+\textstyle{\frac{s_{2}}{s_{1}+s_{2}}}f\big{(}\textstyle{\frac{a_{2}}{s_{2}}},\textstyle{\frac{1}{s_{2}}}\big{)}.$

Multiplying with $\frac{1}{2}(s_{1}+s_{2})$ implies the convexity of
$(a,s)\mapsto sf(\frac{a}{s},\frac{1}{s})$. A similar proof shows the
convexity of $I_{\rm ALOHA}$. Indeed, again assume that $f$ is convex and pick
$(a_{1},s_{1}),(a_{2},s_{2})\in[0,\infty)^{2}$, then we see that

$\displaystyle
f\Big{(}\textstyle{\frac{a_{1}+a_{2}}{\frac{1}{2}(a_{1}+a_{2}+s_{1}+s_{2})}},\textstyle{\frac{2}{\frac{1}{2}(a_{1}+a_{2}+s_{1}+s_{2})}}\Big{)}$
$\displaystyle\leq\frac{a_{1}+s_{1}}{a_{1}+a_{2}+s_{1}+s_{2}}f\Big{(}\textstyle{\frac{a_{1}}{\frac{1}{2}(a_{1}+s_{1})}},\frac{2}{\frac{1}{2}(a_{1}+s_{1})}\Big{)}$
$\displaystyle\quad+\frac{a_{2}+s_{2}}{a_{1}+a_{2}+s_{1}+s_{2}}f\Big{(}\textstyle{\frac{a_{2}}{\frac{1}{2}(a_{2}+s_{2})}},\frac{2}{\frac{1}{2}(a_{2}+s_{2})}\Big{)}.$

Multyplying with $\frac{1}{2}(a_{1}+a_{2}+s_{1}+s_{2})$ implies the convexity
of $(a,s)\mapsto\frac{a+s}{2}f(\frac{2a}{a+s},\frac{2}{a+s})$ and hence the
one of $I_{\rm ALOHA}$. $\square$

Now we prove the large-deviation upper bound for
$(\langle\pi_{1},L_{n}^{\kappa}\rangle,\langle\pi_{2},L_{n}^{\kappa}\rangle)$.

######  Lemma 4.3 (LDP upper bound for
$(\langle\pi_{1},L_{n}^{\kappa}\rangle,\langle\pi_{2},L_{n}^{\kappa}\rangle)$).

For both $*\in\\{{\rm CSMA},{\rm ALOHA}\\}$, for any closed set
$F\subset(0,\infty)^{2}$,

$\displaystyle\limsup_{n\to\infty}\frac{1}{n}\log\mathbb{P}\big{(}(\langle\pi_{1},L_{n}^{\kappa}\rangle,\langle\pi_{2},L_{n}^{\kappa}\rangle)\in
F\big{)}\leq-\inf_{F}J_{*}.$

###### Proof.

We are going to apply the Gärtner–Ellis theorem, which implies our assertion
if the function $\Lambda$, defined by

$\Lambda(A,B)=\lim_{n\to\infty}\frac{1}{n}\log\mathbb{E}\left[{\operatorname{e}}^{n(A\left<\pi_{1},L_{n}^{\kappa}\right>+B\left<\pi_{2},L_{n}^{\kappa}\right>)}\right],\qquad
A\in\mathbb{R},B\in(-\infty,\lambda),$ (4.6)

exists and is lower semi-continuous. In this case, the rate function (which is
convex and lower semi-continuous) is given by the Legendre transform of
$\Lambda$, which we will identify as the function $J_{*}$ defined in (4.3).

If $\Lambda$ would be differentiable, then the Gärtner–Ellis theorem would
provide also the corresponding lower bound and hence a full LDP. However, in
our case we do not know if this is true, due to the discontinuity of the
mappings $\mu\mapsto\langle\pi_{i},\mu\rangle$ for $i\in\\{1,2\\}$ in the weak
topology of probability measures, since $\pi_{i}$ is not bounded.

So let us identify the limit in (4.6), which will be done with the help of the
LDP for $(L_{n}^{\kappa})_{n\in\mathbb{N}}$. Also here, we are facing the
serious problem of missing unboundedness of $\pi_{1}$ and $\pi_{2}$; but we
found a way around this. Indeed, we absorb the $\pi_{2}$-part in the
transition kernel and employ a cutting argument for the $\pi_{1}$-part. We
write now $\mathbb{E}_{*}=\mathbb{E}_{*}^{{\scriptscriptstyle{({\lambda})}}}$
for the expectation with respect to our Markov chain (stressing the arrival
parameter $\lambda$ of the underlying PPP). The following trick absorbs the
$\pi_{2}$-integral into the transition kernel. For this, we write
$W_{*}^{{\scriptscriptstyle{({\lambda})}}}=W_{*}$ to stress the parameter
$\lambda$ in the transition kernel of our Markov kernel, and we introduce the
transformed kernels

$W_{*}^{{\scriptscriptstyle{({A,B,\lambda})}}}((a,t),(k,{\rm
d}s))={\operatorname{e}}^{Ak+Bs}W_{*}((a,t),(k,{\rm d}s)),\qquad
A\in\mathbb{R},B\in(-\infty,\lambda),s\in(0,\infty),k\in\mathbb{N}.$ (4.7)

Then we observe that

$W_{*}^{{\scriptscriptstyle{({A,B,\lambda})}}}=W_{*}^{{\scriptscriptstyle{({D,0,\lambda-B})}}},\qquad\mbox{where
}D:=A+\log\frac{\lambda}{\lambda-B}.$ (4.8)

As a consequence,

$H(\mu\mid\mu^{(\kappa-1)}\otimes
W_{*}^{{\scriptscriptstyle{({\lambda-B})}}})=\log\frac{\lambda}{\lambda-B}\left<\pi_{1},\mu\right>-B\left<\pi_{2},\mu\right>+H(\mu\mid\mu^{{\scriptscriptstyle{({\kappa-1})}}}\otimes
W_{*}).$ (4.9)

We have from (4.8) that

$\mathbb{E}_{*}^{\lambda}\left[{\operatorname{e}}^{n(A\left<\pi_{1},L_{n}^{\kappa}\right>+B\left<\pi_{2},L_{n}^{\kappa}\right>)}\right]=\mathbb{E}_{*}^{{\scriptscriptstyle{({\lambda-B})}}}\left[{\operatorname{e}}^{nD\left<\pi_{1},L_{n}^{\kappa}\right>}\right],\qquad
n\in\mathbb{N}.$

For definiteness, assume that $D>0$; the opposite case is almost the same.
Since we can lower bound $\pi\geq\pi\wedge m$ and since
$\mu\mapsto\left<\pi_{1}\wedge m,\mu\right>$ is continuous and since
$(L_{n}^{\kappa})_{n\in\mathbb{N}}$ satisfies an LDP with rate function
$\mu\mapsto H(\mu\mid\mu^{{\scriptscriptstyle{({\kappa-1})}}}\otimes W_{*})$,
Varadhan’s lemma tells us that

$\liminf_{n\to\infty}\frac{1}{n}\log\mathbb{E}_{*}^{{\scriptscriptstyle{({\lambda-B})}}}\left[{\operatorname{e}}^{nD\left<\pi_{1},L_{n}^{\kappa}\right>}\right]\geq\lim_{m\to\infty}\sup_{\mu}\left[D\left<\pi_{1}\wedge
m,\mu\right>-H(\mu\mid\mu^{{\scriptscriptstyle{({\kappa-1})}}}\otimes
W_{*}^{{\scriptscriptstyle{({\lambda-B})}}})\right]=M(A,B),$ (4.10)

where

$M(A,B)=\sup_{\mu}\left[A\left<\pi_{1},\mu\right>+B\left<\pi_{2},\mu\right>-H(\mu\mid\mu^{(\kappa-1)}\otimes
W_{*})\right],$ (4.11)

where we used (4.9). We will show in the following that also the complementary
inequality to (4.10) holds, which shows that (4.6) holds with $\Lambda=M$.
This finishes the proof of the lemma, since it easily follows from (4.11) that
$J_{*}$ defined in (4.3) is the Legendre transform of $M=\Lambda$.

For estimating in the opposite direction, we need to employ a cutting argument
as follows. For any $m\in\mathbb{N}$ and $\delta>0$,

$\displaystyle\mathbb{E}_{*}^{{\scriptscriptstyle{({\lambda-B})}}}\left[{\operatorname{e}}^{nD\left<\pi_{1},L_{n}^{\kappa}\right>}\right]$
$\displaystyle=\mathbb{E}_{*}^{{\scriptscriptstyle{({\lambda-B})}}}\left[{\operatorname{e}}^{nD\left<\pi_{1},L_{n}^{\kappa}\right>}{\mathchoice{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.5mu\mathrm{l}}{1\mskip-5.0mu\mathrm{l}}}_{\left\\{D|\left<\pi_{1}-\pi_{1}\wedge
m,L_{n}^{\kappa}\right>|\leq\delta\right\\}}+{\operatorname{e}}^{nD\left<\pi_{1},L_{n}^{\kappa}\right>}{\mathchoice{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.5mu\mathrm{l}}{1\mskip-5.0mu\mathrm{l}}}_{\left\\{D|\left<\pi_{1}-\pi_{1}\wedge
m,L_{n}^{\kappa}\right>|>\delta\right\\}}\right]$
$\displaystyle\leq{\operatorname{e}}^{\delta
n}\mathbb{E}_{*}^{{\scriptscriptstyle{({\lambda-B})}}}\left[{\operatorname{e}}^{nD\left<\pi_{1}\wedge
m,L_{n}^{\kappa}\right>}\right]+\mathbb{E}_{*}^{{\scriptscriptstyle{({\lambda-B})}}}\left[{\operatorname{e}}^{nD\left<\pi_{1},L_{n}^{\kappa}\right>}{\mathchoice{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.5mu\mathrm{l}}{1\mskip-5.0mu\mathrm{l}}}_{\left\\{D\sum_{i=1}^{n}(A_{i}-m)_{+}>\delta
n\right\\}}\right].$

We need to show that the exponential large-$n$ rate of the last term is
arbitrarily small if $m$ is picked large, then the complementary inequality to
(4.10) follows. From Lemmas 3.1 and 3.4, respectively, we know that, given
$(\sigma_{i})_{i\in\mathbb{N}}$, under
$\mathbb{E}^{{\scriptscriptstyle{({\lambda-B})}}}$, the random variables
$A_{1},\dots,A_{n}$ are independent and have the distribution of $1+$ a
${\operatorname{Poi}}_{\lambda_{i}}$-distributed random variable, where
$\lambda_{i}=(\lambda-B)\gamma_{i}$ in the CSMA-case and
$\lambda_{i}=(\lambda-B)(\gamma_{i}+B(s)/\kappa)$ in the ALOHA-case, where
$\gamma_{i}=(1-\sum_{j=1}^{\kappa-1}\sigma_{i-j})_{+}$. In any case, we have
$\lambda_{i}\leq 2\lambda$ for any $i$ and can therefore estimate

$\mathbb{P}_{*}^{{\scriptscriptstyle{({\lambda-B})}}}\big{(}A_{i}=k\,\big{|}\,(\sigma_{j})_{j\in\mathbb{N}}\big{)}\leq{\operatorname{e}}^{2\lambda}{\operatorname{Poi}}_{2\lambda}(k-1),\qquad
k\in\mathbb{N}.$

Hence, we can estimate, writing $\mathbb{E}$ for expectation with respect to
${\operatorname{Poi}}_{2\lambda}$, using the exponential Chebyshev inequality
with some $K>0$,

$\displaystyle\mathbb{E}_{*}^{{\scriptscriptstyle{({\lambda-B})}}}\left[{\operatorname{e}}^{nD\left<\pi_{1},L_{n}^{\kappa}\right>}{\mathchoice{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.5mu\mathrm{l}}{1\mskip-5.0mu\mathrm{l}}}_{\left\\{D\sum_{i=1}^{n}(A_{i}-m)_{+}>\delta
n\right\\}}\right]$ $\displaystyle\leq{\operatorname{e}}^{2\lambda
n}\mathbb{E}\left[{\operatorname{e}}^{nD\left<\pi_{1},L_{n}^{\kappa}\right>}{\mathchoice{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.0mu\mathrm{l}}{1\mskip-4.5mu\mathrm{l}}{1\mskip-5.0mu\mathrm{l}}}_{\left\\{D\sum_{i=1}^{n}(A_{i}-m)_{+}>\delta
n\right\\}}\right]$ (4.12) $\displaystyle\leq{\operatorname{e}}^{2\lambda
n}{\operatorname{e}}^{-\frac{K\delta
n}{D}}\mathbb{E}\left[{\operatorname{e}}^{D\sum_{i=1}^{n}A_{i}}\,{\operatorname{e}}^{K\sum_{i=1}^{n}(A_{i}-m)_{+}}\right]$
$\displaystyle=\exp\Big{\\{}-n\Big{[}-\log(2\lambda)+K\frac{\delta}{D}-\log\mathbb{E}\big{[}{\operatorname{e}}^{DA_{1}+K(A_{1}-m)_{+}}\big{]}\Big{]}\Big{\\}}.$

We need to show that the last term in the brackets can be made arbitrarily
large as $m\to\infty$ with an appropriate choice of $K=K(m)$. We estimate the
last term as follows:

$\displaystyle\mathbb{E}\big{[}{\operatorname{e}}^{DA_{1}+K(A_{1}-m)_{+}}\big{]}$
$\displaystyle=\sum_{k=0}^{m}{\operatorname{e}}^{-2\lambda}\frac{(2\lambda)^{k}}{k!}{\operatorname{e}}^{Dk}+\sum_{k>m}{\operatorname{e}}^{-2\lambda}\frac{(2\lambda)^{k}}{k!}{\operatorname{e}}^{Dk}{\operatorname{e}}^{K(k-m)}$
$\displaystyle\leq{\operatorname{e}}^{2\lambda({\operatorname{e}}^{D}-1)}+\frac{(2\lambda{\operatorname{e}}^{D})^{m}}{m!}{\operatorname{e}}^{2\lambda({\operatorname{e}}^{D+K}-1)},$

where we used an index shift and estimated
$\frac{1}{(k+m)!}\leq\frac{1}{k!}\,\frac{1}{m!}$. Now it is easy to see that
one can pick $K=K(m)\to\infty$ in such a way that the term in the brackets on
the right of (4.12) diverges to $\infty$ (take $K$ of order $\log m$).

This finishes the proof of the complementary inequality to (4.10) and
therefore finishes the proof of the lemma.

$\square$

Now we can prove the main result of this section, the LDP upper bounds for
$\frac{1}{t}(A(t),S(t))$. This finishes the proof of Theorem 1.6.

######  Lemma 4.4.

For $*\in\\{{\rm ALOHA,CSMA}\\}$, as $t\to\infty$, the pair
$\frac{1}{t}(A(t),S(t))$ satisfies the LDP upper bound on $(0,\infty)^{2}$
with rate function $I_{*}$, i.e., for any closed set $F\subset(0,\infty)^{2}$
we have

$\displaystyle\limsup_{t\to\infty}\frac{1}{t}\log\mathbb{P}\Big{(}\frac{1}{t}\big{(}S(t),A(t)\big{)}\in
F\Big{)}\leq-\inf_{F}I_{*}$

where $I_{*}$ is given before Lemma 4.2. Furthermore, in both cases
$(\frac{1}{t}(A(t),S(t)))_{t>0}$ is exponentially tight, i.e., for any $M>0$
there is an $K>0$ such that
$\mathbb{P}(\frac{1}{t}(A(t),S(t))\in([0,K]^{2})^{\rm
c})\leq{\operatorname{e}}^{-Mt}$ for any large $t$.

###### Proof.

Let us explain our proof strategy. As we already mentioned above, the sequence
$(L_{n}^{{\scriptscriptstyle{({2})}}})_{n\in\mathbb{N}}$ of empirical pair
measures of the Markov chain $(R_{i}^{*})_{i\in\mathbb{N}_{0}}$ satisfies an
LDP with rate function given in (4.1). Then it is clear that the sequence
$(L_{n}^{\kappa})_{n\in\mathbb{N}}$ of empirical $\kappa$-string measures
satisfies an LDP with rate function given in (4.2). It will turn out that
$(A(t),S(t))$ can be expressed in terms of the partial sums

$\sum_{i=1}^{n}A_{i}=n\langle\pi_{1},L_{n}^{\kappa}\rangle\qquad\mbox{and}\qquad\sum_{i=1}^{n}\sigma_{i}=n\langle\pi_{2},L_{n}^{\kappa}\rangle.$
(4.13)

We will derive the upper bound of the LDP for $\frac{1}{t}(A(t),S(t))$ from
this, in combination with the upper bound of Lemma 4.3 for the pair
$(\langle\pi_{1},L_{n}^{\kappa}\rangle,\langle\pi_{2},L_{n}^{\kappa}\rangle)$.
This derivation will be heuristically done in Step 1 of the proof. Since
$(A(t),S(t))$ is basically a pair of time-inverses, probabilities of events of
one-sided inequalities like $\\{A(t)<a,S(t)>s\\}$ for $a,s\in(0,\infty)$ are
relatively easy to handle, and this we will do in Step 2. The LDP upper bound
for $\frac{1}{t}(A(t),S(t))$ will be proved in Step 3, while the proof of the
exponential tightness is contained in Step 2.

Step 1: Heuristics. We assume that
$(\langle\pi_{1},L_{n}^{\kappa}\rangle,\langle\pi_{2},L_{n}^{\kappa}\rangle)$
satisfies the LDP with rate function $J_{*}$ given in (4.3) and derive
heuristically the LDP for $\frac{1}{t}(A(t),S(t))$ from that. Let us first
treat the CSMA protocol. Fix $a,s>0$. Using (4.13), we see (ignoring that $at$
and $st$ may be not integers) that, as $t\to\infty$,

$\displaystyle\mathbb{P}\left(S(t)\approx st,A(t)\approx at\right)$
$\displaystyle=\mathbb{P}\Big{(}\sum_{i=1}^{st}\sigma_{i}\approx
t,\sum_{i=1}^{st}A_{i}\approx
at\Big{)}=\mathbb{P}\Big{(}\langle\pi_{2},L_{st}^{\kappa}\rangle\approx\frac{1}{s},\langle\pi_{1},L_{st}^{\kappa}\rangle\approx\frac{a}{s}\Big{)}$
(4.14) $\displaystyle\approx\exp\big{(}-stJ_{\rm
CSMA}(a/s,1/s)\big{)}=\exp\big{(}-tI_{\rm CSMA}(a,s)\big{)}.$

This finishes the heuristics for the CSMA case.

In the ALOHA case, let $\widetilde{S}(t)$ be number of potentially successful
messages that arrive by time $t$, i.e., those that pick a free channel at
arrival. Since every time that a new arriving message picks a busy channel,
the old one that is already in this channel also gets lost, the number of
successfully delivered messages by time $t$ is obtained by subtracting the
number of new arriving messages taking a busy channel, from the number of
potentially successful messages. The former is equal to $A_{i}-1$ in each
interval $(\widetilde{T}_{i},\widetilde{T}_{i+1}]$. Considering
$\widetilde{S}(t)$ potentially successful messages and therefore
$\widetilde{S}(t)$ intervals, it means that we have

$S(t)=\widetilde{S}(t)-\sum_{i=1}^{\widetilde{S}(t)}(A_{i}-1)=\widetilde{S}(t)-\Big{(}-\widetilde{S}(t)+\sum_{i=1}^{\widetilde{S}(t)}A_{i}\Big{)}=2\widetilde{S}(t)-\sum_{i=1}^{\widetilde{S}(t)}A_{i}\approx
2\widetilde{S}(t)-A(t).$ (4.15)

Furthermore, $\sum_{i=1}^{\widetilde{S}(t)}\sigma_{i}\approx t$, as we have
already seen in the case of CSMA. Now, let $s,a>0$, the we have, as
$t\to\infty$,

$\displaystyle\mathbb{P}(S(t)=st,A(t)=at)$
$\displaystyle\approx\mathbb{P}\big{(}\widetilde{S}(t)\approx\textstyle{\frac{1}{2}}(a+s)t,A(t)=at\big{)}$
$\displaystyle=\mathbb{P}\Big{(}\sum_{i=1}^{\frac{1}{2}(s+a)t}\sigma_{i}\approx
t,\sum_{i=1}^{\frac{1}{2}(s+a)t}A_{i}\approx at\Big{)}$
$\displaystyle\approx\mathbb{P}\Big{(}\big{\langle}\pi_{2},L^{\kappa}_{\frac{1}{2}(s+a)t}\big{\rangle}=\frac{2}{s+a},\big{\langle}\pi_{1},L^{\kappa}_{\frac{1}{2}(s+a)t}\big{\rangle}=\frac{2a}{s+a}\Big{)}$
$\displaystyle\approx\exp\Big{(}-t\frac{a+s}{2}J_{\rm
ALOHA}(\textstyle{\frac{2a}{a+s}},\textstyle{\frac{2}{a+s}})\Big{)}=\exp\big{(}-tI_{\rm
ALOHA}(a,s)\big{)},$

which finishes the heuristics.

Step 2: Exponential rates for quadrants. As we mentioned, one-sided
inequalities for $S(t)$ and $A(t)$ are relatively easily to handle. We
demonstrate this by showing, as a first step, the exponential tightness of
$(\frac{1}{t}(A(t),S(t)))_{t>0}$. Indeed, for any $K>0$,

$\mathbb{P}\big{(}{\textstyle{\frac{1}{t}}}(A(t),S(t))\in\big{(}[0,K]^{2}\big{)}^{\rm
c}\big{)}\leq\mathbb{P}(A(t)>tK)+\mathbb{P}(S(t)>tK).$

It is easy to see that
$\lim_{K\to\infty}\limsup_{t\to\infty}\frac{1}{t}\log\mathbb{P}(A(t)>tK)=-\infty$,
observing that $A(t)$ is ${\operatorname{Poi}}_{\lambda t}$-distributed. Now,
using the LDP for $(L_{n}^{\kappa})_{n\in\mathbb{N}}$ and again using the
Gärtner–Ellis theorem we can derive an LDP upper bound for
$(\left<\pi_{2},L_{n}^{\kappa}\right>)$ as in Lemma 4.3 with rate function

$\displaystyle\tilde{J}(y)=\sup_{B\in(-\infty,\lambda)}\inf_{\mu\in\mathcal{M}_{1}^{{\scriptscriptstyle{({s})}}}(\Sigma^{\kappa-1})}\left[B(y-\left<\pi_{2},\mu\right>)+H(\mu\mid\mu^{{\scriptscriptstyle{({\kappa})}}-1}\otimes
W_{*})\right].$

Then, using also (4.13), we estimate

$\mathbb{P}(S(t)>tK)=\mathbb{P}\Big{(}\sum_{i=1}^{tK}\sigma_{i}<t\Big{)}\leq\mathbb{P}\big{(}\langle\pi_{2},L_{tK}^{\kappa}\rangle\leq\textstyle{\frac{1}{K}}\big{)}\leq{\operatorname{e}}^{-tK\inf_{(0,1/K]}\tilde{J}}{\operatorname{e}}^{o(t)},$

. Then, it is easy to see that $K\inf_{(0,1/K]}\tilde{J}\to\infty$ as
$K\to\infty$, hence exponential tightness follows.

We further use the simple relation between the partial sum of the
$\sigma_{i}$’s and $(A(t),S(t))$ for proving that, for any
$(a,s)\in(0,\infty)^{2}$,

$\partial_{a}I(a,s)>0,\partial_{s}I(a,s)>0\qquad\Longrightarrow\qquad\limsup_{t\to\infty}\frac{1}{t}\log\mathbb{P}\big{(}\textstyle{\frac{1}{t}}(A(t),S(t)\big{)}\in[a,\infty)\times[s,\infty)\big{)}\leq-
I_{*}(a,s).$ (4.16)

Analogous statements for all the other sign combinations of the partial
derivatives with the respective quadrants are also true and are proved in the
same manner; we omit these proofs. Since $I_{*}$ is continuous, we can freely
replace the closed set $[a,\infty)\times[s,\infty)$ by
$(a,\infty)\times(s,\infty)$.

We prove now (4.16) for the CSMA case; the other one is similar and will be
omitted. Fix $(a,s)$ such that $\partial_{a}I(a,s)$ and $\partial_{s}I(a,s)$
are both positive. For showing (4.16), we see that (again using (4.13))

$\displaystyle\mathbb{P}\big{(}\textstyle{\frac{1}{t}}(A(t),S(t))\in[a,\infty)\times[s,\infty)\big{)}$
$\displaystyle=\mathbb{P}\big{(}S(t)\geq st,A(t)\geq at\big{)}$
$\displaystyle=\mathbb{P}\Big{(}\langle\pi_{2},L_{ts}^{\kappa}\rangle\leq\frac{1}{s},\langle\pi_{1},L_{ts}^{\kappa}\rangle\geq\frac{a}{s}\Big{)}$
$\displaystyle\leq\exp\Big{(}-ts\inf_{[\textstyle{\frac{a}{s}},\infty)\times(-\infty,\frac{1}{s}]}J_{{\rm
CSMA}}\Big{)}{\operatorname{e}}^{o(t)}$
$\displaystyle=\exp\Big{(}-t\inf_{[a,\infty)\times[s,\infty)}I_{\rm
CSMA}\Big{)}\,{\operatorname{e}}^{o(t)}=\exp\big{(}-tI_{\rm
CSMA}(a,s)\big{)}\,{\operatorname{e}}^{o(t)},$

where in the estimate we used the upper bound in the LDP for $L_{ts}^{\kappa}$
and afterwards that $I_{\rm CSMA}(a,s)=sJ_{\rm CSMA}(\frac{a}{s},\frac{1}{s})$
and then that it is continuous and assumes its infimum over
$[a,\infty)\times[s,\infty)$ in the corner of this quadrant. The latter comes
from the convexity of $I_{\rm CSMA}$ and the positivity of the two partial
derivatives.

For handling the case that one of the two partial derivatives is zero, we
claim that

$\partial_{a}I(a,s)=0,\partial_{s}I(a,s)>0\qquad\Longrightarrow\qquad\limsup_{t\to\infty}\frac{1}{t}\log\mathbb{P}\big{(}\textstyle{\frac{1}{t}}(A(t),S(t)\big{)}\in[a,\infty)\times[s,\infty)\big{)}\leq-
I_{*}(a,s).$ (4.17)

The proof of this is similar to the proof of (4.16), but estimates against the
half plane $[0,\infty)\times[s,\infty)$ and uses that the infimum of $I_{*}$
over $[0,\infty)\times[s,\infty)$ is attained at $(a,s)$ by convexity of
$\widetilde{a}\mapsto I_{*}(\widetilde{a},s)$ and because of
$\partial_{a}I(a,s)=0$. We omit the details.

Step 3: Proof of the upper bound. We use the fact that an exponentially tight
sequence $(X_{t})_{t>0}$ of random variables satisfies the LDP upper bound
with rate function $I$ on a Polish space $\mathcal{X}$ if

$\lim_{\varepsilon\downarrow
0}\lim_{t\to\infty}\frac{1}{t}\log\mathbb{P}(X_{t}\in
B_{\varepsilon}(x))\leq-I(x),\qquad x\in\mathcal{X}.$ (4.18)

The proof of this fact is an elementary exercise using standard compactness
arguments; we omit the proof.

We now check (4.18). Fix $x=(a,s)\in(0,\infty)^{2}$. Let us first consider the
case that $\partial_{a}I(a,s)$ and $\partial_{s}I(a,s)$ are both not equal to
zero. Let us assume, for definiteness, that $\partial_{a}I(a,s)>0$ and
$\partial_{s}I(a,s)>0$. Pick an $\varepsilon>0$ such that the two partial
derivatives are positive inside $B_{\varepsilon}(a)\times B_{\varepsilon}(s)$.
Then we can estimate from above, as $t\to\infty$, according to (4.16),

$\mathbb{P}\big{(}\textstyle{\frac{1}{t}}(A(t),S(t))\in
B_{\varepsilon}(a)\times
B_{\varepsilon}(s)\big{)}\leq\mathbb{P}\big{(}\textstyle{\frac{1}{t}}(A(t),S(t))\in[a-\varepsilon,\infty)\times[s-\varepsilon,\infty)\big{)}\leq{\operatorname{e}}^{-tI_{*}(a-\varepsilon,s-\varepsilon)}{\operatorname{e}}^{o(t)}.$

Since $I_{*}$ is continuous, we see that (4.18) is satisfied.

It remains to handle the case where one of the two partial derivatives is
equal to zero. If both are, then $(a,s)$ is the unique minimal point $(a_{\rm
min},s_{\rm min})$ of $I_{*}$, and the exponential rate is equal to zero,
which is equal to $I_{*}(a_{\rm min},s_{\rm min})$. The remaining case that
precisely one of the two partial derivatives vanishes, can be handled either
by an approximation argument (using the continuity of $I_{*}$) or by appealing
to (4.17); we omit the details. $\square$

## References

  * [A77] N. Abramson,  The ALOHA system: another alternative for computer communications,  Fall Joint Computer Conference 37 (Jan. 1977),  p. 281-285.
  * [B76] A.A. Borovkov,  Stochastic Processes in Queueing Theory,  Springer New York, NY  (1976).
  * [B48] E. Brockmeyer,  The life and works of A.K. Erlang,  Transactions of the Danish Academy of Technical Sciences,  no. 2. Kopenhagen: Akademiet for de Tekniske Videnskaber  (1948).
  * [C20a] Jinho Choi,  Multichannel ALOHA with exploration phase,  WCNC 2020: Proceedings of the 2020 IEEE Wireless Communications and Networking Conference, Seoul, South Korea, E1, Vol. 2020-May, pp. 1-6, (2020).
  * [C20b] Jinho Choi,  On Improving Throughput of Multichannel ALOHA using Preamble-based Exploration,  Journal of Communications and Networks 22:5 (October 2020).
  * [CL13] K. Cohen and A. Leshem,  Distributed Throughput Maximization for Multi-Channel ALOHA Networks,  5th IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP) (2013).
  * [CLBK04] M. Coupechoux, T. Lestable, C. Bonnet and V. Kumar.  Throughput of the multi-hop slotted aloha with multi-packet reception,  In IFIP Working Conference on Wireless On-Demand Network Systems.. 1–6  Berlin: Springer (2004).
  * [DS89] J.-D. Deuschel and D. W. Stroock,  Large Deviations, eng. 1. ed.,  Academic Press Inc. (1989).
  * [DZ10] A. Dembo and O. Zeitouni,  Large Deviations Techniques and Applications, eng. 2. ed., corr. printing of the 1998 ed.  Springer New York, NY (2010).
  * [GD11] Yayu Gao and and Lin Dai,  On the throughput of CSMA,  In: 45th Annual Conference on Information Sciences and Systems (March 2011).
  * [GOW04] A.J. Ganesh, N. O’Connell and D.J. Wischik, Big Queues, Springer, Berlin (2004).
  * [K53] David G. Kendall ,  Stochastic processes occurring in the theory of queues and their analysis by the method of the imbedded Markov chain,  Ann. Math. Statistics 24, 338-354 (1953).
  * [KK22] W. König and C. Kwofie,  Large deviations of the throughput in multi-channel medium-access protocols,  in preparation (2022).
  * [LST19] L. Lakatos, L. Szeidl and M. Telek,  Introduction to Queueing Systems with Telecommunication Applications,  2nd ed.,  Springer New York, NY (2019).
  * [MBMH] S. Morshed, M. Baratchi, P.K. Mandal, and G. Heijenk,  A multi-channel multiple access scheme using frequency offsets – modelling and analysis,  preprint.
  * [RS90] R. Rom and M. Sidi,  Multiple Access Protocols: Performance and Analysis,  Telecommunication networks and computer systems,  Springer New York, NY (1990).
  * [SBBB08] S. Salmi, M.L. Boucenna, M. Barkat and M. Benslama,  Throughput Evaluation in ALOHA Technique and its Derivatives Erasure Coding in Satellite Network Commmunications,  Jan. 2009.
  * [SL12] D. Shen and V. Li,  Stabilized multi-channel ALOHA for wireless OFDM networks,  In: IEEE (2012).
  * [SW95] A. Shwartz and A. Weiss,  Large Deviations for Performance Analysis: Queues, Communications, and Computing,  Stochastic modeling series,  London u.a.: Chapman und Hall (1995).
  * [WLZ10] Feng Wang, Dou Li und Yuping Zhao,  An enhanced collision-avoidance MAC protocol for IEEE 802.15.4,  In: IEEE Technology Conference Sep. 2010.