# On Discrete Age of Information of Infinite Size Status Updating System

Jixiang Zhang, Yinfei Xu  School of Information Science and Engineering,
Southeast University, NanJing, China.
Email: {230179077<EMAIL_ADDRESS>
###### Abstract

In this paper, for the discrete time status updating system with infinite
size, we derive the explicit expression of average age of information (AoI),
and the AoI’s stationary distribution. Based on the discussions of difference
between finite and infinite size status updating systems, we successfully
characterize the random dynamics of system’s AoI using a two-dimensional state
vector, which simultaneously tracks the real time AoI and the age of packet
currently under service. We constitute the two-dimensional age process and
completely solve all the stationary probabilities. Then, as one of the
marginal distributions, the stationary distribution of system’s AoI is
derived, and with which the mean of the AoI is also determined.

##  I Introduction

Age of information (AoI) of a status updating system was proposed in paper
[1], which was defined as the time elapsed since the generation time of the
last received packet in the destination. In recent years, it has been used
widely as the freshness metric to characterize the timeliness of various
communication systems. A detailed summary of main contributions of AoI was
given in paper [2]. So far, plenty of results have been obtained which
determine the mean of AoI for the system with different queue models, even in
some works, for example in work [3], the property of AoI’s stationary
distribution was considered. In papers [4, 5, 6], for simple queues including
$M/M/1$, $M/D/1$, and $D/M/1$, the expression of system’s average AoI was
obtained explicitly. Packet management strategies were discussed in paper [7],
and the benefit of introducing proper packet deadlines, both deterministic and
random to reduce the long term average AoI was proved in [8] and [9].
Recently, many papers have been launched considering the AoI of simple status
updating networks, such as the system with multiple sources [10] and the
system having multi-hop packet transmission [11, 12].

On the other hand, although there are not many, but still have some works
analyzing the AoI of discrete time systems. In paper [13], using the proof
techniques and tools developed for analyzing continuous AoI, the authors
obtained the average (peak) AoI of status updating system with $Ber/G/1$ and
$G/G/\infty$ queues. Later, in work [14] the expression of discrete AoI’s
distribution was obtained (in form of Laplace-Stieltjes Transform (LST)) for
basic system with different service disciplines. Discrete time system with
multiple sources was studied in paper [15], where the authors obtained the
exact per-source distribution of AoI and peak AoI in matrix-geometric form. In
our work [16], we obtain the explicit formula of average discrete AoI for
bufferless status updating system by defining a two-dimensional age process,
which characterizes the AoI and the age of packet in service as a whole.

In this paper, we consider the stationary AoI of an infinite size status
updating system which uses $Ber/Geo/1/\infty$ queue, and derive the explicit
expressions of AoI’s mean and its distribution. Based on the characteristic of
infinite size system, it shows that the random dynamics of system’s AoI can be
described using a two-dimensional stochastic process. We establish the
stationary equations of defined age process and obtain all the stationary
probabilities by solving the equations completely. Then, as one of the
marginal distributions, the stationary distribution of AoI can be determined
as well. Given AoI’s distribution, the mean of the AoI can be calculated
easily.

The rest of the paper are organized as follows. In Section II, we depict the
model of an infinite size status updating system and describe system’s age of
information. In Section III, the difference of finite and infinite size system
is discussed, based on which we successfully characterize the dynamics of AoI
using a two-dimensional age process. Then, explicit expressions of both AoI’s
mean and its stationary distribution are derived. Numerical simulations
including AoI’s distributions and the cumulative probabilities are plotted in
Section IV. In addition, we also compare the expressions of average discrete
AoI with that of corresponding continuous AoI, and propose a possible
relationship between average AoIs $\overline{\Delta}_{Ber/Geo/1/c}$ and
$\overline{\Delta}_{M/M/1/c}$ for general system size $c$. At last, the paper
is concluded in Section V.

##  II System Model and Problem Formulation

In Figure 1, we depict the model of an infinite size status updating system.
Packet arrivals to the transmitter is assumed to form a Bernoulli stochastic
process, and the packet service time follows the geometric distribution with
intensity $\gamma$. Updating packet generated at $s$ is transmitted to the
destination $d$ through the transmitter, in which a random period of time is
consumed. The service discipline of the system is First-Come First Served
(FCFS). The age of information (AoI) at the destination $d$ is defined as the
time elapsed since the generation time of the last received packet up to now.
During the time when no packet is obtained, the value of AoI increases 1 after
each time slot ends. Every time when a packet passes the transmitter and
arrives to $d$, the value of the AoI will be reduced to the _system time_ of
the received packet, which is actually equal to the instantaneous age of this
packet.

Let $a(k)$ be the value of AoI in $k$th time slot. Then, the AoI at next time
slot, $a(k+1)$ is determined by

$a(k+1)=\begin{cases}a(k)+1&\text{ if no packet is obtained at the
receiver,}\\\ a(k)+1-Y_{j}&\text{ if $j$th packet arrives to $d$.}\end{cases}$
(1)

where $Y_{j}$ is the interarrival time between $(j-1)$th and $j$th arriving
packet. Since the system considered here has infinite capacity, thus no packet
is missing and these $(j-1)$th and $j$th packets are truly generated
successively in the source node. However, when the size of system is finite,
no matter how small the probability is, some packets are deleted when they
arrive and find that the system is full.

The time average AoI is defined as follows, which converges to the mean of AoI
because it is assumed that the age process is ergodic. We use the notation
$\Delta_{inf}$ to represent the stationary AoI of the infinite size status
updating system. Then, we have

$\displaystyle\overline{\Delta}_{inf}$
$\displaystyle=\lim\nolimits_{T\to\infty}\frac{1}{T}\sum\nolimits_{k=1}^{T}a(k)$
$\displaystyle=\lim\nolimits_{T\to\infty}\frac{1}{T}\sum\nolimits_{i=1}^{M_{T}}i\cdot\left|\left\\{1\leq
k\leq T:a(k)=i\right\\}\right|$ (2)
$\displaystyle=\sum\nolimits_{i=1}^{\infty}i\cdot\pi_{i}$ (3)

in which $M_{T}=\max_{1\leq k\leq T}a(k)$, and for each $i\geq 1$,

$\pi_{i}=\lim\nolimits_{T\to\infty}\frac{\left|\left\\{1\leq k\leq
T:a(k)=i\right\\}\right|}{T}$ (4)

is the probability that stationary AoI takes value $i$. Notice that
probability distribution $\left\\{\pi_{i},i\geq 1\right\\}$ is the stationary
distribution of discrete AoI $\Delta_{inf}$, and from which AoI’s mean can be
calculated according to equation (3).

The randomness of both packet arrivals and the service time in server makes
the AoI at destination change randomly. After one time slot, the AoI may
increase by 1 if no packet is obtained, or drops to the instantaneous age of
the obtained packet if one such packet is successfully received. Although an
infinite number of packets can be contained in current system, in following
Section III we will prove that using a two-dimensional state vector, which
records the real time AoI and the age of packet in system’s server, is
sufficient to fully describe the random dynamics of system’s AoI. As long as
all the stationary probabilities of the two-dimensional age process are
obtained, the distribution of AoI is determined as one of two marginal
distributions. Given AoI’s distribution, then the average value of AoI can be
calculated.

Figure 1: The model of an infinite size discrete time status updating system.

##  III AoI of Infinite Size Status Updating System

In the following, we talk about the difference between the systems with finite
and infinite size. These discussions will give the method of characterizing
the AoI of an infinite size status updating system.

Observing that when the system has infinite capacity, all the packets from
source node can enter the system and be stored in buffer. For finite size
status updating systems, no matter how large the buffer is, it is still
possible that the coming packet is discarded since the buffer is already full.
In paper [3], the authors named the system without packet discarding as
_lossless system_ , while other systems are called _lossy systems_. Packet
discardings make the time interval between two consecutive packets received at
the destination undetermined, since some packets may been deleted when they
arrive to transmitter and find the buffer full. Therefore, in order to
describe the random changes of all the packet ages (including the value of
AoI) in a finite size system, we have to set an age-parameter $m_{i}$ for each
packet. However, if no packets are deleted at all times, the age difference
between two consecutive packets is exactly equal to the _interarrival time_ ,
whose probability distribution is determined by the packet arrival process.
For the Bernoulli arrivals with parameter $p$, suppose the age of current
packet is $m_{j}$, then we can determine that the next packet’s age $m_{j+1}$
is $m_{j}-IA$ with probability $(1-p)^{m_{j}-m_{j+1}-1}p$, where $IA$ is the
random interarrival time between two successive packets. Since the age of one
packet cannot be less than zero, when $IA\geq m_{j}$, we let $m_{j+1}=0$. For
these cases, the next packet is in fact not existent because it has not yet
arrived. This observation is sufficient for us to characterize all the random
dynamics of the age of information at the destination node.

Define the two-dimensional state vector $(n,m)$, $n>m\geq 0$ where $n$ denotes
system’s AoI and $m$ represents the age of packet in service. Constituting the
age process corresponding to infinite size system as

$AoI^{(\infty)}=\left\\{(n_{k},m_{k}):n_{k}>m_{k}\geq
0,k\in\mathbb{N}\right\\}$ (5)

When there is no packet in system, i.e., both the unbounded buffer and the
server are empty, the value of $m$ is set to 0.

We list all the random transfers of $(n,m)$ in Table I, where the considered
random variables that trigger the state vector transitions are the
interarrival time $IA$ and the service variable $B$, which represents whether
the packet service is completed in one time slot. Also define $\pi_{(n,m)}$ as
the stationary probability of state vector $(n,m)$ where $n>m\geq 0$. We
establish all the stationary equations of age process $AoI^{(\infty)}$ as
follows.

$\begin{cases}\pi_{(n,m)}=\pi_{(n-1,m-1)}(1-\gamma)+\sum\nolimits_{k=n}^{\infty}\pi_{(k,n-1)}p\gamma(1-p)^{n-m-1}&\quad(n>m\geq
2)\\\
\pi_{(n,1)}=\pi_{(n-1,0)}p(1-\gamma)+\sum\nolimits_{k=n}^{\infty}\pi_{(k,n-1)}p\gamma(1-p)^{n-2}&\quad(n\geq
2)\\\
\pi_{(n,0)}=\pi_{(n-1,0)}(1-p)+\sum\nolimits_{k=n}^{\infty}\pi_{(k,n-1)}\gamma(1-p)^{n-1}&\quad(n\geq
2)\\\ \pi_{(1,0)}=\sum\nolimits_{k=1}^{\infty}\pi_{(k,0)}p\gamma\end{cases}$
(6)

TABLE I: Descriptions of state vector transfers of age process $AoI^{(\infty)}$ Initial state | Considered r.v.s | Realizations of $IA$, $B$ and next state
---|---|---
$(n,m)$, $n>m\geq 1$ | $B=0$ | $(n+1,m+1)$
$(B=1,IA)$ | $(IA=1):(m+1,m)$
| $(IA=2):(m+1,m-1)$
| $\vdots$
|  | $(IA=m):(m+1,1)$
|  | $(IA\geq m+1):(m+1,0)$
$(n,0)$, $n\geq 1$ | $IA\geq 2$ | $(n+1,0)$
$(IA=1,B)$ | $(B=0):(n+1,1)$
| $(B=1):(1,0)$
|  |

Equations (6) are explained as follows. First of all, we consider how the
state vector $(n,m)$, $n>m\geq 2$ can be transferred to. From initial state
vector $(n-1,m-1)$, if the packet service does not finish in current time
slot, then apparently $(n,m)$ is obtained at next time slot. On the other
hand, beginning with an arbitrary state vector of form $(k,n-1)$, $k\geq n$,
as long as following two conditions are satisfied, that is, (i) the packet
service is completed; and (ii) the interarrival time $IA$ between current and
next packets is equal to $n-m$, then the state of age process $AoI^{(\infty)}$
will transfer to $(n,m)$ as well. Notice that when the value of AoI is reduced
to $n$, $IA=n-m$ implies that the age of packet which will be served next time
is equal to $m$. Combining these two cases, we obtain the first row of (6).

For the cases $n\geq 2$, next the stationary equations of $(n,1)$ are
discussed. Before one time slot, assuming the state vector is $(n-1,0)$, it is
observed that a packet arrives and stays in system after one time slot will
make the state vector change to $(n,1)$. In addition, from any state vector
$(k,n-1)$ where $k\geq n$, when the packet service ends after one time slot,
the packet of age $n$ is delivered to destination, which reduces the AoI to
$n$. Meanwhile, let the interarrival time $IA$ between current and next coming
packet equal $n-1$, then the age 1 packet at the head of queue will enter
system’s server. As a result, again we obtain the state vector $(n,1)$ at next
time slot. This explains the second row of equations (6).

The stationary equations for state vectors $(n,0)$, $n\geq 2$ are analyzed
according to similar discussions. In this situation, the system is empty and
the current value of AoI is $n$. The state vector $(n-1,0)$ jumps to $(n,0)$
as long as no packet arrives to the transmitter at the beginning of next time
slot. Apart from this, similarly, $(n,0)$ can also be obtained from the state
vectors having form $(k,n-1)$. Let the packet in server is the unique one in
system, when this packet completes the service and leaves, and no packet comes
at next time slot, the entire system is emptied. This requires the
interarrival time $IA$ is long enough, more specifically, $IA$ has to be
larger than $n$, the transition probability is equal to

$\gamma\sum\nolimits_{k=n}^{\infty}(1-p)^{k-1}p=\gamma(1-p)^{n-1}$

Thus, we see that the state vector $(k,n-1)$ transfers to $(n,0)$. Summarizing
all these possibilities, the third row of equations (6) are determined.

Finally, a packet enters an empty system and consumes only one time slot in
system’s server will offer the receiver one packet of age 1. Then, the AoI is
reset to 1 and notice that this is the only way the state vector $(1,0)$ can
be obtained.

In the following, we determine all the stationary probabilities $\pi_{(n,m)}$,
$n>m\geq 0$ by solving the system of equations (6) directly.

######  Theorem 1.

The stationary probabilities $\pi_{(n,m)}$, $n>m\geq 0$ of age process
$AoI^{(\infty)}$ are determined as

$\pi_{(n,0)}=\frac{p}{1-p}\Big{\\{}(1-p)^{n}-(1-\gamma)^{n}\Big{\\}}\qquad(n\geq
1)$ (7)

and for $n>m\geq 1$,

$\displaystyle\pi_{(n,m)}=\frac{p^{2}}{1-p}(1-p)^{n}\left(\frac{1-\gamma}{1-p}\right)^{m}-p\gamma(1-\gamma)^{n-1}+\frac{p(\gamma-p)}{(1-p)(1-\gamma)}\left(\frac{1-\gamma}{1-p}\right)^{m}(1-\gamma)^{n-m}$
(8)

###### Proof:

Now, we completely solve the system of equations (6) and derive all the
stationary probabilites $\pi_{(n,m)}$, $n>m\geq 0$. First of all, for $n>m\geq
2$, repeatedly using the first row of (6) gives

$\displaystyle\pi_{(n,m)}$
$\displaystyle=\pi_{(n-1,m-1)}(1-\gamma)+\sum\nolimits_{k=n}^{\infty}\pi_{(k,n-1)}p\gamma(1-p)^{n-m-1}$
$\displaystyle=\left\\{\pi_{(n-2,m-2)}(1-\gamma)+\sum\nolimits_{k=n-1}^{\infty}\pi_{(k,n-2)}p\gamma(1-p)^{n-m-1}\right\\}(1-\gamma)+\sum\nolimits_{k=n}^{\infty}\pi_{(k,n-1)}p\gamma(1-p)^{n-m-1}$
$\displaystyle=\pi_{(n-2,m-2)}(1-\gamma)^{2}+p\gamma(1-p)^{n-m-1}\left\\{(1-\gamma)\sum\nolimits_{k=n-1}^{\infty}\pi_{(k,n-2)}+\sum\nolimits_{k=n}^{\infty}\pi_{(k,n-1)}\right\\}$
$\displaystyle\quad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\vdots$
$\displaystyle=\pi_{(n-m+1,1)}(1-\gamma)^{m-1}+p\gamma(1-p)^{n-m-1}\left(\sum\nolimits_{j=0}^{m-2}(1-\gamma)^{j}\sum\nolimits_{k=n-j}^{\infty}\pi_{(k,n-1-j)}\right)$
$\displaystyle=\left\\{\pi_{(n-m,0)}p(1-\gamma)+\sum\nolimits_{k=n-m+1}^{\infty}\pi_{(k,n-m)}p\gamma(1-p)^{n-m-1}\right\\}(1-\gamma)^{m-1}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\quad+p\gamma(1-p)^{n-m-1}\left(\sum\nolimits_{j=0}^{m-2}(1-\gamma)^{j}\sum\nolimits_{k=n-j}^{\infty}\pi_{(k,n-1-j)}\right)$
(9)
$\displaystyle=\pi_{(n-m,0)}p(1-\gamma)^{m}+p\gamma(1-p)^{n-m-1}\left(\sum\nolimits_{j=0}^{m-1}(1-\gamma)^{j}\sum\nolimits_{k=n-j}^{\infty}\pi_{(k,n-1-j)}\right)$
(10)

where in (9), the boundary case given in the second row of (6) is substituted.

Equation (10) is used to determine the probabilities $\pi_{(n,m)}$, $n>m\geq
1$ in the end, after we obtain the explicit formulas of $\pi_{(n,0)}$, $n\geq
1$ and the infinite sums $\sum\nolimits_{n=m+1}^{\infty}\pi_{(n,m)}$ for each
$m\geq 1$.

Define

$f_{m}=\sum\nolimits_{n=m+1}^{\infty}\pi_{(n,m)}\qquad(m\geq 1)$ (11)

we derive the exact expressions of $f_{m}$ in the followings.

Let $n>m\geq 2$, using the relations in stationary equations (6), it shows
that

$\displaystyle f_{m}$
$\displaystyle=\sum\nolimits_{n=m+1}^{\infty}\pi_{(n,m)}$
$\displaystyle=\sum\nolimits_{n=m+1}^{\infty}\left\\{\pi_{(n-1,m-1)}(1-\gamma)+\sum\nolimits_{k=n}^{\infty}\pi_{(k,n-1)}p\gamma(1-p)^{n-m-1}\right\\}$
$\displaystyle=\left(\sum\nolimits_{n=m}^{\infty}\pi_{(n,m-1)}\right)(1-\gamma)+p\gamma\sum\nolimits_{n=m+1}^{\infty}(1-p)^{n-m-1}\left(\sum\nolimits_{k=n}^{\infty}\pi_{(k,n-1)}\right)$
$\displaystyle=f_{m-1}(1-\gamma)+p\gamma\sum\nolimits_{n=m+1}^{\infty}(1-p)^{n-m-1}f_{n-1}$
(12)

Do once iteration, we obtain the relation

$f_{m-1}=f_{m-2}(1-\gamma)+p\gamma\sum\nolimits_{n=m}^{\infty}(1-p)^{n-m}f_{n-1}$
(13)

Using equations (12) and (13), computing following difference

$\displaystyle(1-p)f_{m}-f_{m-1}$ $\displaystyle={}$ $\displaystyle
f_{m-1}(1-p)(1-\gamma)+p\gamma\sum\nolimits_{n=m+1}^{\infty}(1-p)^{n-m}f_{n-1}-f_{m-2}(1-\gamma)-p\gamma\sum\nolimits_{n=m}^{\infty}(1-p)^{n-m}f_{n-1}$
$\displaystyle={}$ $\displaystyle f_{m-1}(1-p)(1-\gamma)-p\gamma
f_{m-1}-f_{m-2}(1-\gamma)$ (14)

which is equivalent to

$(1-p)f_{m}-[(1-p)+(1-\gamma)]f_{m-1}+(1-\gamma)f_{m-2}=0$ (15)

Notice that (15) is a order two difference equation with constant
coefficients, its characteristic equation is

$(1-p)r^{2}-[(1-p)+(1-\gamma)]r+(1-\gamma)=(r-1)[(1-p)r-(1-\gamma)]=0$ (16)

and we can immediately obtain the two roots of the equation as

$r_{1}=1,\quad r_{2}=\frac{1-\gamma}{1-p}.$ (17)

According to the theory of difference equations, the general expression of
$f_{m}$ can be written as $f_{m}=c_{1}r_{1}^{m}+c_{2}r_{2}^{m}$, where $c_{1}$
and $c_{2}$ are the undetermined coefficients. Since all the stationary
probabilities add up to 1, we have

$1=\sum\nolimits_{m=0}^{\infty}\sum\nolimits_{n=m+1}^{\infty}\pi_{(n,m)}=\sum\nolimits_{m=0}^{\infty}f_{m}$
(18)

in which $f_{0}$ can be defined similarly as
$f_{0}=\sum\nolimits_{n=1}^{\infty}\pi_{(n,0)}$.

Therefore, if $|r_{i}|\geq 1$, the corresponding coefficient $c_{i}$ must be
zero. Otherwise, the infinite sum (18) cannot converge. As a result, we
conclude that

$f_{m}=c\left(\frac{1-\gamma}{1-p}\right)^{m}\qquad(m\geq 1)$ (19)

To determine $f_{m}$ completely, we have to find the first sum $f_{0}$ and the
unkonwn coefficient $c$ in equation (19).

Let $m=1$, from the second row of (6), $f_{1}$ is calculated as

$\displaystyle f_{1}$ $\displaystyle=\sum\nolimits_{n=2}^{\infty}\pi_{(n,1)}$
$\displaystyle=\sum\nolimits_{n=2}^{\infty}\left\\{\pi_{(n-1,0)}p(1-\gamma)+\sum\nolimits_{k=n}^{\infty}\pi_{(k,n-1)}p\gamma(1-p)^{n-2}\right\\}$
$\displaystyle=p(1-\gamma)f_{0}+p\gamma\sum\nolimits_{n=2}^{\infty}(1-p)^{n-2}f_{n-1}$
$\displaystyle=p(1-\gamma)f_{0}+p\gamma\sum\nolimits_{n=2}^{\infty}(1-p)^{n-2}c\left(\frac{1-\gamma}{1-p}\right)^{n-1}$
$\displaystyle=p(1-\gamma)f_{0}+cp\frac{1-\gamma}{1-p}$ (20)

Using the general expression (19) and combining with (20), we obtain that

$f_{1}=c\frac{1-\gamma}{1-p}=p(1-\gamma)f_{0}+cp\frac{1-\gamma}{1-p}$

which gives $f_{0}=c/p$.

Finally, since the sum of all the stationary probabilities is 1, we have
following equations

$\displaystyle 1$
$\displaystyle=\sum\nolimits_{m=0}^{\infty}\sum\nolimits_{n=m+1}^{\infty}\pi_{(n,m)}$
$\displaystyle=\sum\nolimits_{n=1}^{\infty}\pi_{(n,0)}+\sum\nolimits_{m=1}^{\infty}\sum\nolimits_{n=m+1}^{\infty}\pi_{(n,m)}$
$\displaystyle=f_{0}+\sum\nolimits_{m=1}^{\infty}f_{m}$
$\displaystyle=\frac{c}{p}+\sum\nolimits_{m=1}^{\infty}c\left(\frac{1-\gamma}{1-p}\right)^{m}$
$\displaystyle=\frac{c}{p}+\frac{c(1-\gamma)}{\gamma-p}$ (21)

from which we can solve that $c=\frac{p(\gamma-p)}{(1-p)\gamma}$.

So far, all the $f_{m}$, $m\geq 0$ are determined explicitly. We show that

$f_{m}=\sum\nolimits_{n=m+1}^{\infty}\pi_{(n,m)}=\begin{cases}\frac{\gamma-p}{(1-p)\gamma}&\quad(m=0)\\\
\frac{p(\gamma-p)}{(1-p)\gamma}\left(\frac{1-\gamma}{1-p}\right)^{m}&\quad(m\geq
1)\end{cases}$ (22)

Given the results (22), now the probabilities $\pi_{(n,0)}$ can be determined.
The third row of equations (6) shows

$\displaystyle\pi_{(n,0)}$
$\displaystyle=\pi_{(n-1,0)}(1-p)+f_{n-1}\gamma(1-p)^{n-1}$
$\displaystyle=\pi_{(n-1,0)}(1-p)+\frac{p(\gamma-p)}{1-p}(1-\gamma)^{n-1}\qquad(n\geq
2)$ (23)

Applying equation (23) iteratively, we have

$\displaystyle\pi_{(n,0)}$
$\displaystyle=\left(\pi_{(n-2,0)}(1-p)+\frac{p(\gamma-p)}{1-p}(1-\gamma)^{n-2}\right)(1-p)+\frac{p(\gamma-p)}{1-p}(1-\gamma)^{n-1}$
$\displaystyle=\pi_{(n-2,0)}(1-p)^{2}+\frac{p(\gamma-p)}{1-p}\Big{\\{}(1-p)(1-\gamma)^{n-2}-(1-\gamma)^{n-1}\Big{\\}}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\vdots$
$\displaystyle=\pi_{(1,0)}(1-p)^{n-1}+\frac{p(\gamma-p)}{1-p}\sum\nolimits_{j=0}^{n-2}(1-p)^{j}(1-\gamma)^{n-1-j}$
$\displaystyle=p\gamma
f_{0}(1-p)^{n-1}+\frac{p(\gamma-p)}{1-p}\sum\nolimits_{j=0}^{n-2}(1-p)^{j}(1-\gamma)^{n-1-j}$
(24)
$\displaystyle=\frac{p(\gamma-p)}{1-p}\sum\nolimits_{j=0}^{n-1}(1-p)^{j}(1-\gamma)^{n-1-j}$
$\displaystyle=\frac{p}{1-p}\Big{\\{}(1-p)^{n}-(1-\gamma)^{n}\Big{\\}}$ (25)

where in (24) we have used the last equation in (6), which says
$\pi_{(1,0)}=p\gamma f_{0}$. Then, expression given in (22) is substituted.

Since (25) holds for $n\geq 2$, we have to check that equation (25) also gives
$\pi_{(1,0)}$ when we let $n=1$. This verification is direct and we conclude
that the probability expression (25) is valid for all $n\geq 1$.

At last, by equation (10), the other probabilities $\pi_{(n,m)}$, $n>m\geq 1$
can be obtained as well. We have

$\displaystyle\pi_{(n,m)}=\pi_{(n-m,0)}p(1-\gamma)^{m}+p\gamma(1-p)^{n-m-1}\left(\sum\nolimits_{j=0}^{m-1}(1-\gamma)^{j}f_{n-1-j}\right)$
(26)

Since both the probability $\pi_{(n-m,0)}$ and $f_{n-1-j}$ are already known,
substituting them into (26) and finally we show that the probabilities
$\pi_{(n,m)}$ are determined to be

$\displaystyle\pi_{(n,m)}=\frac{p^{2}}{1-p}(1-p)^{n-m}(1-\gamma)^{m}-p\gamma(1-\gamma)^{n-1}+\frac{p(\gamma-p)}{(1-p)(1-\gamma)}\left(\frac{1-\gamma}{1-p}\right)^{m}(1-\gamma)^{n-m}\quad(n>m\geq
1)$ (27)

So far, all the stationary probabilities are solved and we complete the proof
of Theorem 1. ∎

Since the AoI is denoted by the first component of state vector, then the
probability that stationary AoI equals each $n$ can be obtained by merging all
the probabilities $\pi_{(n,m)}$ which have identical AoI-component $n$.

######  Theorem 2.

Assuming the queue model in discrete time status updating system is
Ber/Geo/1/$\infty$, then the stationary distribution of AoI
$\Delta_{Ber/Geo/1/\infty}$ is given as

$\displaystyle\Pr\\{\Delta_{Ber/Geo/1/\infty}=n\\}$ $\displaystyle={}$
$\displaystyle\frac{p\gamma}{\gamma-p}(1-p)^{n}-\left[\frac{p^{2}(1-\gamma)}{\gamma-p}+\gamma\right](1-\gamma)^{n-1}+\frac{\gamma-p}{1-p}\left(\frac{1-\gamma}{1-p}\right)^{n-1}-p\gamma(n-1)(1-\gamma)^{n-1}\quad(n\geq
1)$ (28)

and the average AoI $\overline{\Delta}_{Ber/Geo/1/\infty}$ is calculated to be

$\displaystyle\overline{\Delta}_{Ber/Geo/1/\infty}$
$\displaystyle=\frac{(1-p)(p+\gamma)}{p(\gamma-p)}+\frac{p(1-\gamma)(p-2\gamma)}{\gamma^{2}(\gamma-p)}-\frac{1}{\gamma}$
(29)
$\displaystyle=\frac{1}{\gamma}\left((1-\gamma)+\frac{1}{\rho_{d}}+\frac{\rho_{d}^{2}(1-\gamma)}{1-\rho_{d}}\right)$
(30)

in which $\rho_{d}=p/\gamma$ is the discrete traffic intensity.

###### Proof:

The probability that the AoI equals $n$ can be obtained by collecting all the
stationary probabilities $\pi_{(n,m)}$ where $0\leq m\leq n-1$. For $n\geq 2$,
we have

$\Pr\\{\Delta_{Ber/Geo/1/\infty}=n\\}=\pi_{(n,0)}+\sum\nolimits_{m=1}^{n-1}\pi_{(n,m)}$

where the latter sum is equal to

$\displaystyle\frac{p^{2}}{1-p}(1-p)^{n}\sum\nolimits_{m=1}^{n-1}\left(\frac{1-\gamma}{1-p}\right)^{m}-p\gamma(n-1)(1-\gamma)^{n-1}+\frac{p(\gamma-p)}{(1-p)(1-\gamma)}(1-\gamma)^{n}\sum\nolimits_{m=1}^{n-1}\left(\frac{1}{1-p}\right)^{m}$
$\displaystyle={}$
$\displaystyle\frac{p^{2}(1-\gamma)}{\gamma-p}\Big{\\{}(1-p)^{n-1}-(1-\gamma)^{n-1}\Big{\\}}-p\gamma(n-1)(1-\gamma)^{n-1}-\frac{\gamma-p}{1-p}\left\\{(1-\gamma)^{n-1}-\left(\frac{1-\gamma}{1-p}\right)^{n-1}\right\\}$
(31)

Combining equations (7) and (31), after some extra calculations, we show that
the result (28) is obtained. Notice that also we have to verify that when
$n=1$, expression (28) reduces to the probability $\pi_{(1,0)}$ because it is
the probability that AoI takes value 1. This verification is direct and very
easy. Therefore, we have obtained the stationary distribution of AoI
explicitly for the situation where the status updating system uses
$Ber/Geo/1/\infty$ queue.

Given the stationary distribution of AoI, its average value can be obtained
easily by the expectation formula. We show that

$\displaystyle\overline{\Delta}_{Ber/Geo/1/\infty}$
$\displaystyle=\sum\nolimits_{n=1}^{\infty}n\cdot\Pr\left\\{\Delta_{Ber/Geo/1/\infty}=n\right\\}$
$\displaystyle=\frac{p\gamma}{\gamma-p}\sum\nolimits_{n=1}^{\infty}n(1-p)^{n}-\left[\frac{p^{2}(1-\gamma)}{\gamma-p}+\gamma\right]\sum\nolimits_{n=1}^{\infty}n(1-\gamma)^{n-1}$
$\displaystyle\qquad+\frac{\gamma-p}{1-p}\sum\nolimits_{n=1}^{\infty}n\left(\frac{1-\gamma}{1-p}\right)^{n-1}-p\gamma\sum\nolimits_{n=2}^{\infty}n(n-1)(1-\gamma)^{n-1}$
(32)
$\displaystyle=\frac{(1-p)(p+\gamma)}{p(\gamma-p)}+\frac{p(1-\gamma)(p-2\gamma)}{\gamma^{2}(\gamma-p)}-\frac{1}{\gamma}$
(33)
$\displaystyle=\frac{(1-\rho_{d}\gamma)(\rho_{d}\gamma+\gamma)}{\rho_{d}\gamma(\gamma-\rho_{d}\gamma)}+\frac{\rho_{d}\gamma(1-\gamma)(\rho_{d}\gamma-2\gamma)}{\gamma^{2}(\gamma-\rho_{d}\gamma)}-\frac{1}{\gamma}$
$\displaystyle=\frac{1-\rho_{d}\gamma-\rho_{d}^{2}(1-\gamma)+\rho_{d}^{3}(1-\gamma)}{\gamma\rho_{d}(1-\rho_{d})}$
$\displaystyle=\frac{\rho_{d}(1-\gamma)(1-\rho_{d})+(1-\rho_{d})+\rho_{d}^{3}(1-\gamma)}{\gamma\rho_{d}(1-\rho_{d})}$
$\displaystyle=\frac{1}{\gamma}\left((1-\gamma)+\frac{1}{\rho_{d}}+\frac{\rho_{d}^{2}(1-\gamma)}{1-\rho_{d}}\right)$
(34)

Equations (33), (34) gives the results (29) and (30) in the Theorem. Notice
that during the computations of equation (32), the formula

$\sum\nolimits_{n=k}^{\infty}n(n-1)\cdots(n-k+1)(1-\xi)^{n-k}=\frac{k!}{\xi^{k+1}}\qquad(k\geq
1)$ (35)

is used directly to calculate two sums, where the real number $0<\xi<1$. For
instance, the last sum in (32) is determined as

$\sum\nolimits_{n=2}^{\infty}n(n-1)(1-\gamma)^{n-1}=(1-\gamma)\sum\nolimits_{n=2}^{\infty}n(n-1)(1-\gamma)^{n-2}=\frac{2(1-\gamma)}{\gamma^{3}}$

This completes the proof of Theorem 2. ∎

##  IV Numerical Simulations

In Figure 2, we depict the graphs of AoI’s stationary distribution and the
corresponding cumulative probabilities for the status updating system with
size 1 and size $\infty$, where the AoI’s mean and its distribution for size 1
system was obtained in our work [16]. We proved that

$\displaystyle\Pr\left\\{\Delta_{1}=n\right\\}$
$\displaystyle=\frac{p(1-p)\gamma^{3}[(1-p)^{n}-(1-\gamma)^{n}]}{(p+\gamma-p\gamma)(\gamma-p)^{2}}-\frac{(p\gamma)^{2}n(1-\gamma)^{n}}{(p+\gamma-p\gamma)(\gamma-p)}$
(36)

and

$\overline{\Delta}_{1}=\frac{1}{\gamma}\left((1-\gamma)+\frac{1}{\rho_{d}}+\frac{\rho_{d}}{1/(1-\gamma)+\rho_{d}}\right)$
(37)

In addition, in paper [7] the average continuous AoI of size 1 system and
infinite size system were determined as

$\overline{\Delta}_{M/M/1/1}=\frac{1}{\mu}\left(1+\frac{1}{\rho}+\frac{\rho}{1+\rho}\right)$
(38)

and

$\overline{\Delta}_{M/M/1/\infty}=\frac{1}{\mu}\left(1+\frac{1}{\rho}+\frac{\rho^{2}}{1-\rho}\right)$
(39)

According to equations (30), and (37)-(39), for two extreme cases where
system’s size is 1 and $\infty$, we plot the curves of AoI’s mean versus
traffic load $\rho$ and compare the average discrete and average continuous
AoI. Numerical results reveal following facts:

(i) when traffic load is small, typically lower than 0.5, the gap between
continuous AoI and its corresponding discrete AoI is insignificant, while as
$\rho$ gets large further, for both cases, the difference of discrete and
continuous AoI becomes large;

(ii) as $\rho$ becomes large, the mean of AoI, both continuous and discrete,
are monotonically decreasing for size 1 system, however, for infinite size
system, the curve of average AoI first falls down and then raises. There is an
optimal $\rho^{*}$ (has known $\approx 0.53$) such that the mean of AoI is
minimized. For the system with general size $c$, there must exist the
_critical size_ $c^{*}$, such that when $c<c^{*}$, the average AoI is always
decreasing when $\rho$ becomes large, but for $c\geq c^{*}$, the curve has a
valley, i.e., an optimal $\rho^{*}$ exists. It is interesting to determine
this critical size $c^{*}$, because for given service rate $\gamma$, according
to the criterion that increasing $\rho$ is always helpful for reducing average
AoI, it gives a dichotomy among the status updating systems who use
$Ber/Geo/1/c$ queues.

Actually, for the system with general $Ber/Geo/1/c$ queue, $c=1$ and
$c=\infty$ are two extreme cases. Combining the results in [16] and in current
paper, we have determined the “boundary” at both sides for AoI’s mean and
AoI’s stationary distribution. Thus, in Figure (2b), the curve of AoI’s
cumulative probabilities of a size $c$ system is between the red and blue
lines, and in Figure (2c), two blue lines give the upper and lower bounds of
average discrete AoI $\Delta_{Ber/Geo/1/c}$ of system with general size $c$.

(a) Distribution of AoI for size 1 and $\infty$ system

(b) Cumulative probabilities of two AoIs

(c) Average continuous and discrete AoI

Figure 2: Numerical results of discrete AoI for the systems with size 1 and
$\infty$ and the comparison of average continuous and discrete AoI.

Expressions (30) and (37)-(39) show that certain similarities exist between
average continuous and average discrete AoI. Loosely speaking, we give the
following possible relationship

$\mu\cdot\overline{\Delta}_{M/M/1/c}=\left.\gamma\cdot\overline{\Delta}_{Ber/Geo/1/c}\right|_{\gamma=0}\text{
then replacing $\rho_{d}$ by $\rho$}$ (40)

##  V Conclusion

In this paper, for the infinite size status updating system with
$Ber/Geo/1/\infty$ queue, we determine the explicit expression of both AoI’s
stationary distribution and the mean of AoI. The core observation is that for
a _lossless_ system, the age difference between successive packets is equal to
the packet interarrival time. Thus, the age of next packet can be determined
by the age of current packet and the interarrival time. A two-dimensional age
process is constituted to describe the random changes of system’s AoI, and all
the stationary probabilities are obtained by solving the stationary equations
directly. Combining the previous results about size 1 system and the results
obtained in current paper, for status updating system with $Ber/Geo/1/c$
queues, we determine the “boundary” at both sides for AoI’s mean and its
stationary distribution.

## References

  * [1] S. Kaul, M. Gruteser, V. Rai, and J. Kenney, “Minimizing age of information in vehicular networks,” in _8th Annu. IEEE Commun. Soc. Conf. Sensor, Mesh Ad-Hoc Commun. Netw. (SECOM)_ , Jun. 2011, pp. 350–358.
  * [2] R. D. Yates, Y. Sun, D. R. Brown, S. K. Kaul, E. Modiano, and S. Ulukus, “Age of information: An introduction and survey,” _IEEE J. Sel. Areas Commun._ , vol. 39, no. 5, pp. 1183–1210, 2021.
  * [3] J. P. Champati, H. Al-Zubaidy, and J. Gross, “Statistical guarantee optimization for aoi in single-hop and two-hop fcfs systems with periodic arrivals,” _IEEE Trans. Commun._ , vol. 69, no. 1, pp. 365–381, 2021.
  * [4] R. D. Yates and S. K. Kaul, “The age of information: Real-time status updating by multiple sources,” _IEEE Trans. Inf. Theory_ , vol. 65, no. 3, pp. 1807–1827, 2019.
  * [5] S. K. Kaul, R. D. Yates, and M. Gruteser, “Status updates through queues,” in _46th Annu. Conf. Inf. Sci. Syst._ , 2012, pp. 1–6.
  * [6] Y. Inoue, H. Masuyama, T. Takine, and T. Tanaka, “A general formula for the stationary distribution of the age of information and its application to single-server queues,” _IEEE Trans. Inf. Theory_ , vol. 65, no. 12, pp. 8305–8324, 2019.
  * [7] M. Costa, M. Codreanu, and A. Ephremides, “On the age of information in status update systems with packet management,” _IEEE Trans. Inf. Theory_ , vol. 62, no. 4, pp. 1897–1910, 2016.
  * [8] C. Kam, S. Kompella, G. D. Nguyen, J. E. Wieselthier, and A. Ephremides, “On the age of information with packet deadlines,” _IEEE Trans. Inf. Theory_ , vol. 64, no. 9, pp. 6419–6428, 2018.
  * [9] Y. Inoue, “Analysis of the age of information with packet deadline and infinite buffer capacity,” in _IEEE Int. Symp. Inform. Theory (ISIT)_ , 2018, pp. 2639–2643.
  * [10] M. Moltafet, M. Leinonen, and M. Codreanu, “On the age of information in multi-source queueing models,” _IEEE Trans. Commun._ , vol. 68, no. 8, pp. 5003–5017, 2020.
  * [11] O. Ayan, H. M. Gürsu, A. Papa, and W. Kellerer, “Probability analysis of age of information in multi-hop networks,” _IEEE Netw. Lett._ , vol. 2, no. 2, pp. 76–80, 2020.
  * [12] S. Farazi, A. G. Klein, and D. R. Brown, “Fundamental bounds on the age of information in multi-hop global status update networks,” _J. Commun. Netw._ , vol. 21, no. 3, pp. 268–279, 2019.
  * [13] V. Tripathi, R. Talak, and E. Modiano, “Age of information for discrete time queues,” _arXiv:1901.10463v1_ , 2019.
  * [14] A. Kosta, N. Pappas, A. Ephremides, and V. Angelakis, “The age of information in a discrete time queue: Stationary distribution and non-linear age mean analysis,” _IEEE J. Sel. Areas Commun._ , vol. 39, no. 5, pp. 1352–1364, 2021.
  * [15] N. Akar and O. Doğan, “Discrete-time queueing model of age of information with multiple information sources,” _IEEE Internet Things J._ , vol. 8, no. 19, pp. 14 531–14 542, 2021.
  * [16] Z. Jixiang and X. Yinfei, “On age of information for discrete time status updating system with ber/g/1/1 queues,” in _IEEE Inf. Theory Workshop (ITW)_ , 2021, pp. 1–6.