Dual-Regime Absorbing Markov Chain Theory in Remote Estimation: Age-Minimizing Push Policies Sennur Ulukus
2
pt
em
I. Cosandal and S. Ulukus are with the University of Maryland, College Park, MD, USA. N. Akar is with Bilkent University, Ankara, Türkiye. Corresponding author: S. Ulukus (email: [email protected]). This work is done when N. Akar was on sabbatical leave as a visiting professor at the University of Maryland, MD, USA.
3
1
1
1
2
2
2
2
it
Remote sensing systems have been receiving considerable attention due to technological advances making sensors more affordable and applicable [1]. One of the main objectives in remote sensing systems is to keep the information fresh at the remote monitors. Recently, several freshness metrics have been proposed to quantify information freshness. The first of these metrics is the age of information (AoI) metric [2], [3] that quantifies information freshness by keeping track of how long ago the latest received information packet was generated. However, AoI may fall short of capturing freshness in certain estimation problems since it does not consider the dynamics of the sampled process [4]. Particularly, even when the latest received packet may have been generated a long time ago, it is possible that the source may not have changed since then, and therefore, the packet can still be fresh. Similarly, a recently received packet may contain stale information if the source has already changed its state after the packet was generated. Stemming from these drawbacks inherent to
1
sm
I. I NTRODUCTION
pre
Abstract—For a remote estimation system, we study the optimization of age of incorrect information (AoII), which is a recently proposed semantic-aware information freshness metric. In particular, we assume an information source that observes a discrete-time finite-state Markov chain (DTMC), and occasionally transmits status update packets to a remote monitor which is tasked with remote estimation of the source. For the forward channel from the source to the monitor, we assume the channel delay to be modeled by a general discrete-time phase-type (DPH) distribution, whereas the reverse channel from the monitor to the source is assumed to be perfect, ensuring that the source has perfect information on the AoII and the remote estimate at the monitor, at all times. Push-based transmissions are initiated when AoII exceeds a threshold depending on the current estimation value, i.e., multi-threshold policy. In this very general setting, our goal is to minimize a weighted sum of the time average of a polynomial function of AoII, depending on the remote estimate, and energy consumption from transmissions. We formulate the problem as a semi-Markov decision process (SMDP) with the same state-space of the original DTMC to obtain the optimal multi-threshold policy, whereas the parameters of the SMDP are obtained by using a novel stochastic tool called dual-regime absorbing Markov chain (DR-AMC), and its corresponding absorption time distribution named as dual-regime DPH (DR-DPH). The proposed method is validated with numerical examples using comparisons against other policies obtained by exhaustive search, and also various benchmark policies.
Nail Akar tran
arXiv:2606.32010v1 [cs.IT] 30 Jun 2026
Ismail Cosandal
channel
3
monitor proces
source process immediate feedback
Fig. 1. The remote estimation system involving the source process Xt , the monitor process X̂t , and the forward channel modeled by DPH(γ, G). The monitor updates its estimation with the received updates (marked with dashed circles).
AoI, [4] proposes an alternative freshness metric, namely, age of incorrect information (AoII) that penalizes the mismatch between the source and its estimation over time, and regardless of when it is sampled, it defines the estimation as fresh if it is the same as the source. Another prominent feature of AoII in contrast to AoI is that the monitor is not required to get a new sample to bring the age down to zero since the mismatch condition between the source and the monitor may as well be brought to an end upon a transition of the source to the estimated value at the monitor. Let us consider the remote estimation system in Fig. 1. For the source process Xt and its remote estimation X̂t at time t, the AoII process, denoted by AoIIt , is given by, AoIIt = t − sup{t′ : t′ ≤ t, Xt′ = X̂t′ },
(1)
which is in line with the original formulation in [4] for AoII, which considers a linear time penalty function with unit proportionality constant. In this paper, we focus on minimizing arbitrary functions of AoIIt and estimation value j which is denoted by fj (AoIIt ), named as the AoII penalty functions. This dependence of the AoII function on the estimation value is motivated by applications that follow the classical missile detection example in detection and estimation textbooks such as in [5], where incorrect estimation of the presence of a missile results in a higher cost than the incorrect estimation of its absence. A similar approach is used in [6], where different age functions are used for nodes in a gossip network. In the literature, it is proven that threshold-based policies, also known as switching-type policies, are optimal for a wide range of AoII problems. The works in [4], [7]– [9] consider symmetric discrete-time Markov chain (DTMC) sources, which are the most frequently studied type in the early AoII works, for which the optimum transmission policies are obtained in order to minimize the average AoII with and without energy constraints. These works propose the optimum policy in the form of a single threshold, and the optimization
problem is cast as a Markov decision process (MDP). On the other hand, in [10], a general continuous-time Markov chain (CTMC) source is studied for the first time, to the best of our knowledge. In [11], it is shown that using a single threshold push-based AoII policy is suboptimal for asymmetric sources, and it is proven that the optimal policy is a multi-threshold policy for which the threshold values depend on the states of both the source and estimation processes. In addition, the optimality of a similar threshold structure is derived for energy harvesting problems in [12]–[14], where the thresholds also depend on the battery level. Threshold-based policies are also proposed for the AoI metric [15] in different settings, and the metrics derived from AoII [16]–[18]. An absorbing Markov chain (AMC) is a Markov chain that has a number of transient and absorbing states, and the process starts operation in a transient state and evolves until an absorbing state is reached, upon which the process is said to be absorbed (or gets stuck) [19]. The distribution of the time until absorption for an absorbing Markov chain is known as a phase-type (PH) distribution, or more specifically discretetime PH (DPH) for discrete-time AMCs [20]. In this paper, we use the DPH distribution to model the general forward channel in Fig. 1. DPH distributions have recently been used for information freshness and networked control problems in several existing works. In [21]–[23], distributions of AoI and peak AoI processes are derived by making use of AMC and PH distributions. These works can be considered as an alternative to the stochastic hybrid systems (SHS) approach that is widely used to find the distribution of AoI [24], [25]. In another work [26], PH distributions are used to find the expected time before a certain number of consecutive packet failures occur in a wireless closed-loop control system. In this paper, we extend the well-established concepts of AMC and DPH, to the case where transient states and transition probabilities from the transient states are different depending on whether the elapsed time of the AMC is below or above a threshold, namely dualregime AMC (DR-AMC) and dual-regime DPH (DR-DPH), respectively. A similar approach is used for threshold-based server selection problem involving the AoI metric in [27], which involves more than two regimes. DR-AMC and DRDPH have the potential to be used for analysis and optimization of threshold policies involving information freshness. In [11], it was shown that finding the optimum state-andestimation based multi-threshold policy that minimizes the average AoII under an energy consumption constraint requires computation with complexity O(N 6 ), for a CTMC process with N states. Thus, such a multi-threshold policy may not be suitable for large N . On the other hand, a relaxed policy in which the threshold values only depend on the estimation process results in similar performance in comparison to the optimal policy in most cases with relatively lower complexity, i.e., O(N 3 ). Therefore, in this paper, we focus our attention to the estimation-based multi-threshold policy in which the source initiates the transmission only if the duration of the mismatch between the source and the estimation processes exceeds a threshold τj when the estimation is X̂t = j, and we
seek the optimum thresholds which minimize a weighted sum of the AoII cost and the consumed energy for transmissions, referred to as the transmission cost. We first formulate the problem as an SMDP [28] where the states are the embedded values at the embedded synchronization points, and the duration between two successive embedded points is random. Subsequently, we employ the DR-AMC theory to obtain the parameters of the SMDP. Finally, we obtain the optimum policy by the policy iteration algorithm. The contribution of our paper can be summarized as follows: We study the (unconstrained) AoII and transmission cost minimization problem under an estimation-based AoII penalty function, using a general DPH-distributed forward channel model. • We reduce the four-dimensional joint process composed of the state, estimation, channel phase, and age processes, to a one-dimensional embedded DTMC, which enables us to formulate the problem as an SMDP with reasonable complexity, and to obtain optimal push-based sampling policies using multiple thresholds, in an efficient manner. • We propose the novel DR-AMC and DR-DPH analytical frameworks to obtain the distribution of AoII throughout the duration between two successive embedded points, along with the transition probabilities at two successive embedded time points. Hence, we can calculate the average of an arbitrary function of AoII numerically, which is key to the SMDP formulation. Furthermore, we obtain closed-form expressions for the same quantity for the special case of polynomial functions of AoII. • We additionally propose a mixture policy to adapt the unconstrained optimization problem to the energyconstrained one. •
The organization of the paper is as follows. In Section II, we present preliminaries on notation, and the AMC, DPH and SMDP frameworks, which are needed for the development of the paper. In Section III, we present the mathematical frameworks of DR-AMC and DR-DPH that we introduce in this paper. The system model is described in Section IV. The optimization problem is formulated as an SMDP in Section V through an embedded DTMC whose parameters are derived in Section VI. We dedicate Section VII to the numerical results, and finally, we conclude in Section VIII. II. P RELIMINARIES A. Notation Throughout the paper, we use lowercase and uppercase bold characters for a vector, and a matrix, respectively. Specifically, am denotes the mth entry of the vector a, and amn denotes the (m, n)th element of the matrix A. The N × N identity matrix is denoted by IN , but the subscript can be omitted for convenience when the size of the matrix can be inferred. A 1 denotes a column vector of ones, ek denotes a column vector of zeros except for the kth entry, which is one. Finally, the operation ⊗ corresponds to the Kronecker product [29].
B. Absorbing Markov Chains and Phase-Type Distribution The AMC we study in this paper refers to a DTMC that has K transient and L absorbing states [30]. The process starts from a transient state (or phase) and evolves until reaching one of the absorbing states. Consider the AMC Yt ∈ {1, 2, . . . K, K + 1, . . . , K + L}, t = 0, 1, . . . , where the first K states are the transient states, and the last L states are the absorbing states. The transition matrix of this process can be written as A B Q= , (2) 0 0 where AK×K and BK×L are the transient probability transition sub-matrix (TPTS) and absorption probability transition sub-matrix (APTS) corresponding to the transition probabilities among the transient states, and from the transient states to the absorbing states, respectively. In this case, we say that Yt is an AMC characterized with the triple (β, A, B), i.e., Yt ∼ AMC(β, A, B), where β = {βi } is the 1 × K initial probability vector (IPV), and βi = P(Y0 = i),
i = 1, . . . , K.
(3)
We write the transient probability vector of the AMC Yt of size 1 × K at time k as follows, yt = yt,1 yt,2 · · · yt,K , yt,k = P(Yt = k), (4) which leads to the following closed-form expression for yt , yt = βAt ,
t ≥ 1.
(5)
A basic property about an AMC is that the expected number of visits to a transient state j starting from a transient state i is given by the (i, j)th entry of the fundamental matrix [19] F = (I − A)−1 .
(6)
We denote the time until absorption by T , which corresponds to the first time slot that the process is in any absorbing state, and mathematically it can be expressed as T = max(t|Xt−1 ∈ {1, . . . , K}, Xt ∈ {K + 1, . . . , K + L}). (7) Upon merging all the absorbing states into one, the distribution of T is known as the DPH distribution [30], i.e., T ∼ DPH(β, A). The absorption time T has cumulative distribution function (cdf) FT (t) = P(T ≤ t), and probability mass function (pmf) pT (t) = P(T = t), which can respectively be written as follows for any general absorption time t, FT (t) = 1 − yt 1 = 1 − βAt 1, pT (t) = FT (t) − FT (t − 1) = βA
(8) t−1
(1 − A1).
(9)
Several well-known distributions with finite/infinite support can be represented by DPH distributions; see Appendix A for various examples. The following definition is needed for the factorial moments. Definition 1 (Falling factorial power [31]) The falling fac-
torial power of x of order m, also called x to the m falling, denoted by xm , is given by xm = x(x − 1)(x − 2) · · · (x − m + 1).
(10)
The ith factorial moment of T , denoted by νT (i) = E[T i ], can be written in closed form through the following expression [20], νT (i) = E[ T (T − 1) · · · (T − i + 1) ],
(11)
= i! β(I − A)−i Ai−1 1.
(12)
C. Semi-Markov Decision Process (SMDP) This section describes the average-cost SMDP framework, and presents the policy iteration method based on [32], [33]. The discrete-time SMDP of interest to the current paper is the tuple (S, A, ρ, r, d) described below. • The state space S = {1, 2, . . . , S} of the SMDP is the finite set of states that are visited by the SMDP process. • The action space A is the set of actions that can be taken at a state. The use of different action sets at different states is not of interest to this paper, and is therefore not discussed. • ρ : S × A × S → [0, 1] is called the transition function of the SMDP. Particularly, when action a ∈ A is taken at current state s, a transition to state s′ occurs with probability ρ(s, a, s′ ). • r : S × A → [0, ∞) is the cost function which represents the average accumulated cost r(s, a) when action a is taken at state s, until the transition to the next state. • d : S × A → (0, ∞) is the sojourn time function which is the average time spent at state s when action a is taken, which is denoted by d(s, a). A deterministic policy ϕ : S → A is one that maps each state s ∈ S to a single action a ∈ A, i.e., we take the action ϕs when we are at state s. Let a deterministic policy ϕ be given. Let the embedded (at the decision epochs) Markov chain associated with the policy ϕ be denoted by Ztϕ , t ≥ 0 where Ztϕ is the state of the system at decision epoch t. Let Btϕ denote the total cost accumulated up to time t, t ≥ 0. If the embedded process Ztϕ has no two disjoint communicating classes, then for each initial state Z0ϕ = s, the limit Btϕ = rϕ , (13) t→∞ t exists, and is independent of the initial state s. The deterministic policy ϕ∗ that minimizes the long-run average cost in (13) is the optimum solution for the SMDP problem. Algortithm 1 presents the pseudo-code for the policy iteration algorithm to obtain ϕ∗ given the average-cost SMDP described by the tuple (S, A, ρ, r, d) [32]–[34]. lim
III. D UAL -R EGIME A BSORBING M ARKOV C HAINS AND P HASE - TYPE D ISTRIBUTIONS In this section, we introduce the analytical frameworks of DR-AMC and DR-DPH, which are the extensions of AMC and DPH, respectively, for which the TPTS, APTS, and the
Algorithm 1 Policy Iteration Algorithm for an SMDP Input: Initiate all actions uj j ∈ N with an arbitrary policy. Output: Policy ϕ∗ Step 1: (Initialization) Start with an initial arbitrary policy ϕ Step 2: (Relative Value Determination) For the present policy ϕ, solve the following linear system of equations for s = 1, 2, . . . , S − 1, for the relative values Vs and the longrun average cost rϕ of the policy ϕ, rϕ d(s, ϕs ) + Vs = r(s, ϕs ) +
S X
ρ(s, ϕs , s′ )Vs′ ,
(14)
the absorbing states into one. Hence, T is is characterized by the following 5-tuple, T ∼ DR-DPH (β1 , τ, Θ, A1 , A2 ) .
(18)
Theorem 1 The absorption time T of the DR-AMC Yt whose characterization is given in (18) has the following pmf, ( β1 At−1 t < τ, 1 (1 − A1 1), pT (t) = P(T = t) = (19) t−τ β2 A2 (1 − A2 1), t ≥ τ, where β2 is given in (16).
s′ =1
by setting VS = 0. Step 3: (Policy Improvement) For each state s = 1, 2, . . . , S, set the alternative action as to, ! S X 1 ′ r(s, a) + ρ(s, a, s )Vs′ − Vs arg min d(s, a) a∈A s′ =1 (15) Step 4: Update the policy ϕs = as for s = 1, 2, . . . , S Step 5: Stop when the two successive policies are the same and set ϕ∗ = ϕ. Otherwise, go to Step 2.
number of transient states depend on the regime associated with the elapsed time since the AMC starts evolution. More specifically, we define a process Yt that, when the elapsed time is strictly below a threshold τ , corresponds to the first τ − 1 time steps with time indices t = (0, . . . , τ −2), it is considered in regime 1. During this regime, it has K1 transient states and L absorbing states. We denote the TPTS and APTS for this regime by A1 and B1 , respectively, and the process starts from regime 1 with IPV β1 . Therefore, the process evolves from time indices t = (0, . . . , τ − 2) to t′ = (1, . . . , τ − 1) with A1 and B1 , thus if it is absorbed in regime 1, the absorption time is T < τ . On the other hand, if the process is not absorbed in regime 1, regime 2 starts from the τ th time slot (at t = τ − 1). Regime 2 has K2 transient states in addition to the same L absorbing states. Also, we define the intermediate transition matrix (ITM) denoted by Θ, a K1 ×K2 matrix, corresponding to the transition probabilities among the transient states of regimes 1 and 2, at the regime cross-over instance. Mathematically, the IPV of regime 2 is obtained by β2 = β1 Aτ −1 Θ.
(16)
Similar to regime 1, we denote the TPTS and APTS for regime 2 by A2 and B2 , respectively, and T ≥ τ indicates it is absorbed in regime 2. Finally, we characterize the DR-AMC with the 7-tuple, Yt ∼ DR-AMC (β1 , τ, Θ, A1 , A1 , B1 , B2 ) .
(17)
Next, we define the DR-DPH distribution that corresponds to the distribution of the absorption time T of the DR-AMC described by (17), which is obtained by means of merging
Proof: Let us define the two random variables T1 ∼ DPH(β1 , A1 ),
T2 ∼ DPH(β̂2 , A2 ),
(20)
where β̂2 is the IPV vector for the second regime conditioned on entrance to the second regime. Then, β̂2 = P(T11≥τ ) β2 . First, it is straightforward to see that the conditional distributions {T |t < τ } and {T1 |t < τ } are equivalent to each other, which proves the first case of (19) using the expression for the pmf of the DPH distribution in (9). The second case of (19) is equivalent to the probability that the AMC is not absorbed in the first regime, i.e., T1 ≥ τ , and it spends t − τ + 1 units of time without absorption in the second regime, which can be expressed as, P(T1 ≥ τ, T2 = t − τ + 1) = P(T1 ≥ τ )P(T2 = t − τ + 1) = P(T1 > τ )β̂2 At−τ 2 (1 − A2 1) = β2 At−τ 2 (1 − A2 1),
(21)
which completes the proof. ■ We also define the absorption vector in regime i, for i = 1, 2, denoted by σi , σi = σi1 σi2 · · · σiL , (22) where σij is the probability of absorption into absorbing statej stemming from a transition taking place in regime i. Notice that Ai , i = 1, 2 are sub-stochastic matrices with all their eigenvalues being strictly inside the unit circle, thus the matrix (I − Ai ) is invertible for i = 1, 2 which ensures that the perregime absorption vectors are non-zero. Lemma 1 For Yt ∼ DR-AMC (β1 , τ, Θ, A1 , A1 , B1 , B2 ), the two per-regime absorption vectors σ1 and σ2 are written in closed form as, σ1 = β1 (I − Aτ1 −1 )(I − A1 )−1 B1 ,
(23)
−1
(24)
σ2 = β2 (I − A2 )
B2 .
Proof: We first define the absorption probability vector ỹt , similar to the definition of yt in (4), at time t as, ỹt = ỹt,l · · · ỹt,L , (25) ỹt,l = P(Yt = Ki + l),
i = 1, 2.
(26)
Let us first focus on the transitions in regime 1, we have, A1 B1 k yt ỹt = β1 0 , 0 ≤ k ≤ τ1 . (27) 0 I
P(Ut+1 = 1|Ut = 0, ∆t < τ ) = q.
Therefore, for 0 ≤ t < τ , yt = β1 At1 , ỹt = β1
t−1 X
(28) Al1 B1 ,
(29)
l=0
= β1 (I − At1 )(I − A1 )−1 B1 .
(30)
Since ỹτ −1,j is the probability that absorption occurs into absorbing state-j from a transition in regime 1, we have σ1 = ỹτ −1 ,
(31)
= β1 (I − Aτ1 −1 )(I − A1 )−1 B1 .
(32)
Similarly, for regime 2, we can express yt , t ≥ τ as yt = β2 At−τ 2 ,
(33)
t−1 X
Al2 B2 ,
(34)
= σ1 + β2 (I − At2 )(I − A2 )−1 B2 .
(35)
ỹt = σ1 + β2
than a threshold τ or not. For this example, we consider when ∆t < τ , the value of Ut changes from 0 to 1 with probability q; mathematically its transition probability is expressed as
l=0
Notice that liml→∞ Al2 = 0 since A2 is a sub-stochastic matrix. Subsequently, we can write lim yt = σ1 + β2 (I − A2 )−1 B2 ,
t→∞
(36)
which gives the absorption probabilities in infinite horizon, i.e., from regime 1 or 2. Finally, we write, σ2 = β2 (I − A2 )−1 B2 ,
(37)
by extracting from (36) the absorption probabilities from regime 1. ■ Lemma 2 The mth factorial moment of T , denoted by νT (m) = E[T m ], is given in (39) located at the top of the next page. Additionally, the ordinary moments, denoted by µT (m) = E[T m ], can be obtained from the corresponding factorial moments as follows, µT (m) =
m X
S(m, r)νT (r),
(38)
(41)
In addition, when ∆t ≥ τ , the control variable reaches state 1 in D steps, where D is modeled with a mixture of geometric distributions, and it is denoted as MGD(p1 , p2 , w1 , w2 ). It can be considered as a communications problem under random channel conditions, where the channel is either in a good condition with probability w1 , and the transmission duration is distributed with Geo(p1 ), or in a bad condition with probability w2 , and the transmission duration is distributed with Geo(p2 ). For this example, we define the event Ut = 1 as the absorbing state, and duration until the absorption starting from (U0 = 0, ∆0 = 1) can be modeled as DR-DPH (β1 , τ, Θ, A1 , A2 ) with the following formulation: The first regime includes a single transient state that is responsible for continuing Ut = 0, and as a natural result β1 = 1. During the first regime, the absorption occurs with probability q, or it stays in the transient state with probability 1 − q. Therefore, TPTS and APTS of this regime are A1 = 1 − q , B1 = q . (42) At the (τ −1)th slot, the age value becomes τ , and the regime 2 starts. Transient states of regime 2 correspond to the channel condition. The probability of reaching this state is β1 Aτ1 −1 = (1 − q)τ −1 , and by multiplying the ITM, corresponding to the probability of the channel conditions, Θ = w1 w2 , (43) we get the IPV of the second regime as β2 = β1 Aτ1 −1 Θ = w1 (1 − q)τ −1 w2 (1 − q)τ −1
(44)
At any time slot of the second regime, the process continues until the absorption with probability pi when the channel condition is i = 1, 2. Therefore, we can express TPTS and APTS of the second regime as 1 − p1 0 p A1 = , B1 = 1 , (45) 0 1 − p2 p2 which finalizes the formulation.
r=0
where S(m, k) is the Stirling number of the second kind. The proof of Lemma 2 is given in Appendix B. Example 1 In this illustrative example, we formulate the distribution of a generic age process ∆t with a control variable Ut . We consider that the age process evolves based on the control variable Ut as ( ∆t−1 + 1, Ut = 0, ∆t = (40) 0, Ut = 1. Furthermore, we assume that transition probabilities of Ut change based on the age process ∆t , which is strictly less
We refer the reader to [11] and [27] for further extensions of DR-AMC and DR-DPH to the case of more than two regimes, namely multi-regime extensions, in continuous-time and discrete-time, respectively. IV. S YSTEM M ODEL We consider the time-slotted remote estimation system in Fig. 1 with an N -state DTMC information source process Xt ∈ N = {1, 2, . . . , N } which has an irreducible transition probability matrix Q, and the one-step transition probability from state i to state j is denoted by qij . With the generate-atwill (GAW) principle, the source can initiate a transmission of a status update packet carrying the observation value to the
( νT (m) =
Pτ −1 Pm m m−r β1 t=1 tm At−1 r!Ar2 (I − A2 )−r−1 (1 − A2 1), m ≤ τ, 1 (1 − A1 1) + β2 r τ Pτ −1 m t−1 Pr=0 m m r −r−1 m−τ m−r β1 t=1 t A1 (1 − A1 1) + β2 r=0 r m r!A2 (I − A2 ) A2 (1 − A2 1), m > τ,
remote monitor at the beginning of a time slot. We assume the events happen in the following order: i) the state of Xt changes just before the end of the time slot, and ii) an ongoing transmission is only completed at the end of the time slot. Therefore, if the source process changes when there is an ongoing transmission, the source preempts the ongoing transmission with a fresh packet, to avoid sending incorrect information. The ongoing transmission continues until the source state changes, or the transmission is successful. We assume instantaneous feedback from the monitor to the source. Therefore, the source is always aware of the estimation and AoII processes. Consequently, we propose an estimationbased multi-threshold transmission policy for which the source always initiates a new transmission, or continues thr ongoing transmission when AoII value exceeds the threshold τj when the estimation X̂t = j. We model the channel delay D to be distributed according to a DPH distribution, D ∼ (γ, G), with M transient states, called channel phases, and a single absorption state corresponding to successful transmission. When the transmission of a packet is initiated, the channel is in phase m with probability γm . If transmission is not preempted, or equivalently if the source stays the same, until the next time slot, the channel evolves to phase m′ which occurs with probability gmm′ , or the transmission is complete with probability hm . Otherwise, transmission of a new packet is initiated when the channel is in phase m with probability γm . As the estimator at the monitor, we employ the martingale estimator which uses the latest received information as its estimate, i.e., X̂t = Xt′ , where t′ is the generation time of the latest successful transmission [35]. Hence, in the martingale estimator, the estimate can only be updated at packet reception instances. This estimation rule is widely used in the literature due to its amenability to analysis and optimization. However, we refer to [36], [37] which additionally considers the maximum a posteriori (MAP) estimator in pull-based remote estimation systems for which the monitor can update its estimation as the maximum likely state, without having to receive a status update. The mismatch between Xt and X̂t is measured with the AoII process defined in (1), where fj (x) corresponds to the AoII penalty function for estimation j. In Fig. 2, an example √ scenario is given for N = 3, and penalty functions f1 (x) = x, f2 (x) = x2 , and f3 (x) = x, where x = AoIIt . We highlighted the time slots when there is an ongoing transmission with dashed boxes. Note that, transmissions at time slots 5 and 9 are preempted because of a state change in the next time slot. On the other hand, transmissions are successful at time slots 11 and 15, and they result in a change of the estimation process X̂t . Notice that, at time slot 6, AoII
preempted transmission
(39)
completed transmission
5 4 3 2 1 0
5
10
15
1
1
3
2
2
1
1
1
3
2
2
2
3
3
3
3
1
2
1
1
1
1
1
1
1
1
1
1
2
2
2
2
3
3
3
3
Fig. 2. Sample path of the processes Xt , X̂t , and AoII √ t for a general transmission policy, and AoII penalty functions f1 (x) = x, f2 (x) = x2 , and f3 (x) = x, where x = AoIIt . Successful transmissions are shown with blue arrows, and purple arrows indicate preempted transmissions. Time slots when the source is transmitting are illustrated with dashed boxes. AoII is reset upon synchronization, otherwise, it increases by one at every time slot as long as the mismatch condition between Xt and X̂t remains.
is reset without a successful transmission since the original process Xt transitions to the estimated value. The first objective of this work is to find a transmission policy for the source that minimizes the average cost, L
min
τ ∈ZN +
1X costt L→∞ L t=1 lim
(46)
where τ is the vector of threshold values, and costt = fX̂t (AoIIt ) + λδt ,
(47)
where δt is one if there is a transmission at time t, and zero otherwise, and λ denotes a relative weight assigned for the transmission cost. We also consider the following constrained optimization problem, L
min
τ ∈ZN +
1X fX̂t (AoIIt ) L→∞ L t=1 lim
(48)
1 s.t. lim δt ≤ α, L→∞ L where α denotes the sampling budget. V. E MBEDDED DTMC R EPRESENTATION The conventional way to obtain the optimum policy is to define an MDP with a four-dimensional state-space, namely (Xt , Pt , X̂t , AoIIt ), which is detailed in Appendix C. However, we take a different approach in this paper by obtaining an embedded DTMC whose state-space is the same as the original process Xt , as opposed to the four-dimensional state-space of Appendix C. Subsequently, we formulate the minimization problem in (46) as an SMDP. Additionally, with this approach, we avoid truncation of the state-space which would be required since AoIIt can take arbitrarily large values. In order to obtain the embedded DTMC, we first need to define embedded points (EP).
For each state Ej , the action is the value of the threshold τj ∈ Z+ , where Z+ denotes the set of positive integers, which constitutes the action space of the problem. • There are two costs for this problem, which are the age penalty cost, and the transmission cost. For state Ej and action τj , we denote them with a(Ej , τj ) = E[Aj ], and c(Ej , τj ) = E[Cj ], respectively, and the expected total cost of the problem is denoted by r(Ej , τj ) = a(Ej , τj )+ λc(Ej , τj ). • Similarly, the expected duration for state Ej for the same action equals d(Ej , τj ) = E[Dj ]. • Lastly, ρ(Ej , τj , Ei ) denotes the transition probability from state Ej to the next state Ei when action τj is applied. Once the parameters of the SMDP are found, it can be solved by using Algorithm 1. In the next section, we will obtain the SMDP parameters by employing the DR-AMC and DR-DPH frameworks.
3
•
regime 2
3
3
3
1
{ regime 1
1
1
{ 2
2
2
2
2
idle
3
phase-2 phase-1 phase-1
Fig. 3. A sample path of the cycle-2 with τ2 = 5. Distributions of H2 and T2 are detailed in Example 2.
Definition 2 (Embedded Point) A time point t0 is called an embedded point (EP) with embedded value (EV) Ej satisfying X̂t0 −1 ̸= Xt0 −1 , Xt0 = X̂t0 +1 . Thus, embedded time points correspond to the time index when the source and monitor processes just get to synchronize at value j. The interval between the EP with EV Ej and the next EP is called a cycle of type j, or cycle-j in short. Cycle-j is divided into two separate intervals with the first one called the in-sync interval with duration Hj which starts from the value Ej , and lasts until the first time slot at which synchronization between the source and the monitor is broken. At this time instant, the second interval gets to start and lasts until the beginning of the next cycle, called the out-of-sync interval, whose duration is denoted by Tj . During the out-of-sync interval, there is a transmission whenever AoIIt exceeds the threshold τj , which needs to be obtained for each j to minimize the objective function in (46). Additionally, we denote the duration cyclePTof j j by Dj = Hj + Tj , the total AoII cost by Aj = t=1 fj (t), and the total number of slots used for transmissions in cycle-j by Cj . A sample path of cycle-2 is illustrated in Fig. 3. At time t = 0 cycle-2 starts from E2 , and the in-sync interval lasts for H2 = 5 time slots. At time t = 5, the synchronization is broken with a state change of the source, and the out-of-sync interval starts. The first 4 time slots of this interval are the regime-1 when the source refrains from transmission. At time t = 9, AoIIt value reaches the threshold τ2 = 5 which initiates the regime 2. There is an ongoing transmission from t = 9 to t = 11, and the corresponding cycle and the out-of-sync interval are completed with the completion of the transmission at the end of t = 11. In this example, the total duration of the cycle is D2 = H2 + T2 = 12, the total P transmission cost is 7 C2 = 3, and the total AoII cost is A2 = t=1 f2 (t). Now, we construct an embedded DTMC whose states are the EVs Ei , i ∈ N , and subsequently an SMDP with the 5-tuple (S, Z+ , ρ, r, d) described in Section II-C as follows. •
Embedded points are the states of the problem with the state space S = {E1 , . . . , EN }.
VI. O BTAINING THE SMDP M ODEL In this section, we utilize the DR-AMC and DR-PH frameworks to obtain the SMDP parameters for the purpose of solving the unconstrained optimization problem given in (46). Then, we propose a method that adapts this solution to the constrained optimization problem given in (48). Specifically, we first model an embedded DTMC whose states are Ei , i ∈ N , and then calculate the quantities d(Ej , τj ), a(Ej , τj ), and ρ(Ei , τj , Ej ), for a given action τj . Each cycle-j starts with an EV Ej which indicates Xt = X̂t , and it stays in synchronization for a duration Hj . When synchronized, no transmission is initiated, and no penalty occurs, thus the total cost is zero. The synchronization is broken with the state change of Xt to any state i ̸= j, and it lasts until it reaches an EP. We define the process Yj (t) ∼ DR-AMC(βj1 , τj , Θ, Aj1 , Aj2 , Bj1 , Bj2 ) to represent the out-of-sync interval of cycle-j. Thus, the out-of-sync interval duration, denoted by Tj , has a DR-DPH distribution, i.e., Tj ∼ DR-PH(βj1 , τj , Θ, Aj1 , Aj2 ). Here, the transient state of the first regime corresponds to i ∈ N \j, enumerated as, {1, . . . , j − 1, j + 1, . . . , N },
(49)
and EVs Ei , i ∈ N are the absorption states. The first regime starts with the state transition of j → i of Xt with probability qji , j ̸= i. Thus, we define the IPV for this regime with a row vector βj1 , whose elements can be written as, qji , i ̸= j. (50) {βj1 }i = P k̸=j qjk During this regime, the source does not initiate any transmission, thus only the absorbing state Ej can be reached with a state change on Xt to the estimated value j. This regime lasts until an absorption to Ej occurs, or t reaches the threshold τ . Table I provides the transition probabilities from the transient state i from which the matrices Aj1 and Bj1 can be constructed. On the other hand, the transient states of the second regime are represented by the pair (i, m), where
TABLE I T RANSITION PROBABILITIES FOR THE PROCESS Yj (t) IN THE FIRST REGIME .
Transition probabilities from state i To Condition Probability i′ i′ ̸= i, j qii′ Ej qij Ei i′ ̸= j 0
(54)
There are N = 3 absorbing states {E1 , E2 , E3 }. However, since there is no transmission during this phase, only E2 can be reached with probability qi2 from transient state i = 1, 3, and B11 can thus be expressed as, 0 q12 0 B21 = . (55) 0 q32 0
TABLE II T RANSITION PROBABILITIES FOR THE PROCESS Yj (t) IN THE SECOND REGIME .
Transition probabilities from state (i, m) To Condition Probability (i, ℓ) qii gmℓ (i′ , ℓ) i′ ̸= i, j qii′ γℓ Ej qij Ei i′ ̸= j (1 − qii )hm
i ∈ N \j and m ∈ {1, . . . , M } correspond to the state of the source process and channel phase, respectively. We enumerate these states as follows, {(1, 1), (1, 2), . . . , (j − 1, M ), (j + 1, 1), . . . , (N, M )}. (51) Absorbing states in the second regime are the same as in the first regime. When the threshold is reached, the source transmits at each following time slot, and the first transmission starts at channel phase k with probability γk . Therefore, the boundary transition matrix is obtained as, Θ = IN −1 ⊗ γ.
removing the 2nd row and column of the Q, q q A21 = 11 13 . q31 q33
(52)
Different from the first regime, the process can be absorbed to Ei , i ̸= j if i) the state Xt does not change, and ii) the transmission succeeds without preemption. These transition probabilities again are provided in Table II from which the matrices Aj2 and Bj2 can be constructed similarly.
Example 2 Consider a source process with three states, N = 3, and the channel modeled by DPH(γ, G) with two phases, M = 2. For cycle-2 and given τ2 , we construct the corresponding AMC Y2 (t) ∼ DR-AMC(β21 , τ2 , Θ, A21 , A22 , B21 , B22 ) as follows. Transient states of the first regime are {1, 3}. The process is initiated when synchronization is broken, resulting in a state transition of the source from state 2 to one of these states where the IPV is given by, h q21 q23 i β21 = . (53) q21 + q23 q21 + q23 The transition probabilities among the transient states are the same as the original process, thus, A11 is obtained by
The transient states of the second regime are the pairs (i, m) in the order of {(1, 1), (1, 2), (3, 1), (3, 2)}. At the start of the second regime, the probability of the source being in state i can be obtained by β1 Aτ −1 . In addition, the channel process is initiated from phase m with probability γm . Since the initialization of the channel process is independent from the source state, the IPV for this regime can be written as β1 Aτ −1 Θ with γ γ2 0 0 Θ= 1 . (56) 0 0 γ 1 γ2 The transition probabilities among the transient states can be obtained from Table II as q11 g11 q11 g12 γ1 q13 γ2 q13 q11 g21 q11 g22 γ1 q13 γ2 q13 A22 = (57) γ1 q31 γ2 q31 q33 g11 q33 g12 γ1 q31 γ2 q31 q33 g11 q33 g12 q13 γ q11 G q13 γ (58) = q31 γ q33 G q31 γ Similar to the first regime, in this regime, the absorbing state E2 can be reached with probability qi2 from transient state i = 1, 3. On the other hand, the remaining absorbing states Ei , i = 1, 3 are reached from state (i, m) with probability qii hm , which is the product of the probabilities of the source staying in the same state and the successful transmission from channel phase m. Thus, APTS B22 can be written as, q11 h1 q12 0 q11 h2 q12 0 . B22 = (59) 0 q32 q33 h1 0 q32 q33 h2 A. Derivation of a(Ej , τj ) For any given AoII penalty function fj (t), the expected age cost can be calculated from the distribution in (19) as Tj Tj X X a(Ej , τj ) = E fj (t) = fj (t)pTj (t). (60) t=1
t=1
Next, we provide the closed-form expression for a(Ej , τj ) when the AoII penalty functions fj (t) are polynomial functions of t.
Lemma 3 (Polynomial AoII Penalty Functions) If the AoII penalty function for estimation value j is polynomial with PKj degree Kj , i.e., fj (t) = k=0 wk,j tk where wk,j are the polynomial coefficients, then the following closed-form expression holds for a(Ej , τj ), Kj X
k X S(m + 1, n + 1)
µTj (m).
(61)
Proof: The expression we want to calculate is Tj Kj Tj X X X E fj (t) = E wk,j tk
(62)
wk,j
n+1
m=1
k=0
t=1
k=0
=
Kj X
t=1
Tj X wk,j E tk .
k=0
(63)
t=1
Using Faulhaber’s formula [38], the expected value of a finite power sum from 1 to T can be written in terms of the ordinary moments of the random variable T as follows, " T # k X X S(m + 1, n + 1) k E t = E[T m ]. (64) n + 1 m=1 t=1 The proof is completed by using the relation between µjm and νjm in (38), and inserting (64) into (63). ■ B. Derivation of d(Ej , τj ) The expected duration of cycle-j, denoted by d(Ej , τj ), is the sum of E[Hj ] and E[Tj ]. The former term equals the expected number of trials until success with failure probability qjj , which is E[Hj ] = q1jj . The second term can be calculated from (39) for m = 1, which is written explicitly as τ −1 X
tβj1 At−1 j1 (1 − Aj1 1)
t=1 + βj2 τj (I − Aj2 )−1 + Aj2 (I − Aj2 )−2 (1 − Aj2 1). (65)
C. Derivation of c(Ej , τj ) Since transmission continues each time slot in the second regime, the expected duration of the transmissions equals the number of transient states visited in the second regime. From the fundamental matrix definition in (6), it can be shown that c(Ej , τj ) = β2 (I − Aj2 )−1 1.
(66)
D. Derivation of ρ(Ej , τj , Ei ) Consider the absorbing states j ̸= i which can only occur in the second regime. For the threshold value τj , its absorption probability can be calculated from (24) as ρ(Ej , τj , Ei ) = βj2 (I − Aj2 )−1 Bj2 ei ,
i ̸= j.
(67)
Then, the self-transition probability for Ej can be written as, X ρ(Ej , τj , Ej ) = 1 − ρ(Ej , τj , Ek ). (68) k̸=j
E. Solving the Constrained Problem SMDP formulation given above solves the unconstrained problem in (46) for a given coefficient λ. In this part, we adopt this solution for the constrained problem of (48). It is known from [39] that there exists a Lagrangian coefficient λ∗ such that the optimum policy obtained for the unconstrained problem is also optimum for the constrained problem either ∗ when (i) the constrained problem attains T C λ = α, or (ii) λ = 0 and T C 0 ≤ α, where T C λ is the time average of the transmission cost obtained from the unconstrained problem with coefficient λ. However, from the nature of the discretetime system, a deterministic policy on the boundary of the constraint set may not exist. For such cases, a mixture of multiple deterministic policies can be used to obtain an optimal policy for the constrained problem. Among many methods, we adopt the non-randomized past-dependent policy, namely, steering algorithm in [40]. In the steering algorithm, we consider two policies corresponding to coefficients λ− and λ+ such that T C λ− ≤ α ≤ T C λ+ , and the algorithm switches between the two policies based on the current sampling rate after each cycle. The general procedure of the algorithm is summarized in Algorithm 2 where D(m) and C (m) denote the duration and total number of transmission slots, respectively, in the mth cycle. Algorithm 2 Steering algorithm Input: λ− and λ+ such that T C λ− ≤ α ≤ T C λ+ Initialize: T C0 = 0; for m ← 1 to M do if T Cm−1 < α then Apply optimum thresholds obtained for λ+ ; else Apply optimum thresholds obtained for λ− ; end if Pm (n) n=1 C T Cm ← Pm (n) ; n=1 D end for
VII. N UMERICAL R ESULTS In this section, we present numerical examples for validating the SMDP model of the paper along with comparisons with two benchmark policies: i) single threshold (ST) policy for which the source waits for a single system-wide threshold τ while there is a mismatch between Xt and X̂t , which is a widely used approach in the literature [4], [7]–[9], and the value of τ which minimizes the overall cost is found by line search, ii) random sampling (RS) policy [11] in which transmission happens with probability ξ at any time during the out-of-sync interval, and again the value of ξ which minimizes the overall cost for RS is found by line search. In the first example, Xt has probability transition matrix Q1 0.65 0.35 Q1 = , (69) 0.25 0.75
Fig. 4. Each point shows the average AoII cost when using the threshold pair (τ1 , τ2 ) with a color map. Circle and cross markers are used to show the threshold values that minimize the average cost using exhaustive search and the proposed SMDP algorithm, respectively, for a given weight λ, the values of which are given along with the markers. As an example, when λ ∈ {68, . . . , 75}, the threshold pair (6, 11) is shown to be the optimum multi-threshold policy using both methods.
(a)
under the AoII penalty functions 1 7 2 3 1 1 x + x + , (70) f1 (x) = x2 + x + , f2 (x) = 2 3 10 5 2 and we consider a geometrically distributed channel delay with parameter 0.8. Fig. 4 illustrates the overall cost for each threshold pair (τ1 , τ2 ) (obtained analytically) illustrated with a color map in Fig. 4. For each integer λ between 0 and 75, the threshold pair that minimizes (46) is obtained with exhaustive search, and shown with a red circle. In addition, the optimum threshold pair obtained by the proposed SMDP method is marked with a cross. The perfect match between these marks verifies the optimality of our algorithm. In the second numerical example, we study two DTMC information sources. The first 3-state source has a probability transition matrix Q2 0.7 0.2 0.1 Q2 = 0.3 0.6 0.1 , (71) 0.2 0.3 0.5 and we employ AoII penalty functions 1 1 1 1 1 f1 (x) = x2 + , f2 (x) = x2 + x, f3 (x) = x2 + . 2 2 2 3 4 (72) The second source with N = 10 states has a probability transition matrix Q3 whose diagonal elements are linearly spread in the interval [0.4, 0.6], and similarly, off-diagonal elements 1−qnn nn are linearly spread in the interval [0.5 1−q N −1 , 1.5 N −1 ]. For this source, we consider the AoII penalty functions fn (x) = 1 2 1 n x + N +1−n x for state n. We use the same channel model as before. Then, for a given weight parameter λ, the proposed SMDP algorithm obtains the multi-threshold optimum policy. The average cost obtained with the SMDP algorithm along with the RS and ST policies is depicted in Fig. 6. For ST and SMDP policies, both analytical and simulation results
(b) Fig. 5. Comparison of benchmark policies with proposed SMDP policy with varying λ for a) Q2 (N = 3), and b) Q3 (N = 10).
are obtained, and the strong agreement between them verifies our analytical results. Since all AoII penalty functions are polynomials in the examples, we employed the closed-form expression (61) for finding the parameters of the SMDP model. On the other hand, only simulation results are used for RS. We observe that our proposed SMDP-based policy outperforms both benchmark policies substantially, and all converge to the same policy when λ → 0 which corresponds to the always transmit policy. We additionally observe that the performance gain increases with λ, for instance, average cost of SMDP at λ = 4 for the process Q3 is around 25% less than ST policy, and 30% less than PS policy. In the final example, we study a two-phase channel delay distributed according to DPH(γ, G) with parameters, 0.7 0.2 γ= 1 0 , G= , (73) 0.1 0.6 for the process
0.6 Q4 = 0.25 0.2
0.25 0.55 0.3
0.15 0.2 , 0.5
(74)
VIII. C ONCLUSIONS
Fig. 6. Comparison of benchmark policies with proposed SMDP policy with varying λ for Q4 under the two-phase channel DPH(γ, G), which is defined in (73).
We solve the cost minimization problem for a push-based remote estimation system that consists of a DTMC source process, a monitor, and a forward delay channel modeled by a DPH distribution. In the proposed setting, the source initiates a transmission when the AoII value exceeds an estimation-based threshold that is to be obtained for each estimation to solve the cost minimization problem. Initiated transmission lasts until it is successful, or it is preempted, and a new transmission is initiated if the source process changes. We formulate the problem as an SMDP with the same statespace as the original DTMC process, using the embedded DTMC approach. To obtain the parameterization of the SMDP, we propose to utilize the DR-AMC and DR-DPH frameworks that can further be adapted to analyze other freshness metrics for threshold-based policies. Cost of the problem is defined as the weighted combination of transmission cost and any estimation-based functions of AoII. In addition, closed-form expressions are obtained for polynomial functions. Furthermore, a mixture of policy methods, namely the steering algorithm, is adapted to solve the constrained problem. Analytical methods and optimality are verified by numerical results by comparing the proposed approach against exhaustive search and benchmark policies. Results from the exhaustive search verify the optimality of our proposed algorithm. We additionally observe that the performance gain in using the proposed multi-threshold approach against the single threshold and random sampling policies increases with increasing cost of the transmission, which makes it advantageous for settings where the sampling is rare because of low energy availability. A PPENDIX A E XAMPLES OF DPH DISTRIBUTIONS
Fig. 7. Applying the steering algorithm for λ− = 1.134, λ+ = 1.135, Q4 and α = 0.5, and comparing with the deterministic policies. The long-term sampling rates are denoted with dashed lines.
and the linear AoII penalty functions 1 f1 (x) = x + , 2
f2 (x) =
1 x + 1, 2
f3 (x) =
1 1 x+ . 3 4 (75)
The results are depicted in Fig. 6 for which we observe trends between benchmark policies and the optimal policy, similar to what we have obtained before. Finally, for the same setting, we solve the constrained problem in (48) for α = 0.5. We obtain coefficients λ− = 1.134 and λ+ = 1.135 with the correand sponding sampling rates T C − =0.5182, T C + = 0.4726, optimum threshold values τ− = 1 1 4 , τ+ = 1 1 5 . Fig. 7 illustrates the simulation results for the mixture of these policies obtained by the steering algorithm in Alg. 2. We observe that the transmission cost of the mixture policy converges to the budget at a similar rate to the deterministic policies obtained for the coefficients λ− and λ+ .
Here, we obtain the DPH representation of the geometric distribution, mixture of geometric distributions, and bounded support distributions, which are used to model channel delays in this paper. a) Geometric distribution: When the channel delay D is distributed according to Geo(θ), at each slot, the transmission is complete with probability θ, and fails to complete with probability 1 − θ. In other words, we have the representation D ∼ DPH(γ, G) where we have a single phase, and γ = 1,
G = 1 − θ.
(76)
b) Mixture of geometric distribution (MGD): There are K geometric distributions Geo(θk ) with mixture weights wk , for k = 1, . . . , K. Channel delay D is said to have an MGD distribution characterized by the parameters {θk }K k=1 and {wk }K i=1 when the delay D is geometrically distributed with parameter θk with probability wk . For each transmission, the channel is in one of the K conditions, and the weights represent the probability of experiencing the condition. The representation D ∼ DPH(γ, G) has K phases where γ = w1 · · · w K , (77)
1 − θ1 0 G= . ..
0 1 − θ2
··· ··· .. .
···
0
0 0
.
TABLE III S TIRLING NUMBERS OF THE SECOND KIND S(n, m) FOR n, m ≤ 4.
(78) n\m 1 2 3 4
1 − θK
1 1 1 1 1
2
3
4
1 c) Bounded support distribution: Consider a channel 3 1 delay D described by a finite probability vector ζ, i.e., 7 6 1 transmission duration is k slots with probability ζk for k ≤ P . The representation D ∼ DPH(γ, G) has P phases where γ = 1 ··· 0 , (79) a) Case τ ≥ m: By changing variable d = t − τ and applying identity (84), we get ζ1 0 1 − PP ζ 0 ··· 0 p=1 p ∞ ∞ X X ζ2 0 0 1 − PP ζ ··· 0 m t−τ A = t (t + τ )m Ad2 (86) p p=2 2 . .. t=τ d=0 . G = . . . ∞ X m X m m−r r d ··· 1 − PPζP −1 ζ 0 = τ d A2 (87) p=P −1 p r r=0 d=0 0 ··· 0 m ∞ X m m−r X r d (80) = τ d A2 (88) r r=0 d=0 A PPENDIX B m X m m−r M OMENTS OF DR-DPH D ISTRIBUTIONS = τ r!Ar2 (I − A2 )−r−1 . (89) r r=0 The mth factorial moment of T distributed according to DR-DPH(τ, β, Θ, A1 , A2 , B1 , B2 ) is equivalent to νT (i) =
τ −1 X
tm β1 At−1 1 (1 − A1 1)
t=1 ∞ X
+
m
t
β2 At−τ 2 (1 − A2 1) .
∞ X
(81) t=τ
t=τ
|
{z
Im
}
The first term is a finite sum which can be calculated for finite τ . The term Im , on the other hand, includes an infinite summation, and special transformations are required to obtain an expression for it in closed-form. We rewrite this term as ! ∞ X m t−τ Im = β2 (1 − A2 1). (82) t A2 t=τ
P∞ In order to evaluate the sum term t=τ tm At−τ 2 , we utilize the following identity for falling factorials [31], xm = (a + b)m =
m X
S(m, n)xm ,
n=1 m X n=0
m m−n n a b , n
(83) (84)
where S(m, n) is the second kind Stirling number whose values for m, n ≤ 4 are presented in Table III. In addition, from (12), one can obtain the identity ∞ X
nm An =m!Am (I − A)−m−1 .
n=0
We now have two separate cases as τ ≥ m and τ < m.
We obtain (87) and (89) by applying (84) and (85), respectively. Finally, we end up with νm for τ ≥ m by inserting (89) into (82) and (81), subsequently. b) Case τ < m: For this case, we need to divide the sum term to avoid τ k for any k > τ as
(85)
tm At−τ = 2
m−1 X
tm At−τ + 2
t=τ
∞ X
tm At−τ 2 .
(90)
t=m
Again, the finite sum can be calculated efficiently, and applying the previous steps to the infinite sum, we get ∞ m X X m m t−τ t A2 = mm−r r!Ar2 (I − A2 )−r−1 Am−τ . 2 r t=m r=0 (91) We conclude the proof by applying the identity (83) to obtain ordinary moments from the factorial moments as µT (m) =
m X
S(m, r)νT (r).
(92)
r=0
A PPENDIX C S TANDARD MDP F ORMULATION The conventional way to obtain the optimum policy is to define an MDP with the 5-tuple (S, A, c, ρ), which is a special case of the SMDP formulation in Section II-C with unit sojourn times. First, we denote the channel phase process by Pt , where Pt ∈ M = {1, . . . M } which is defined as follows. When the channel is not actively used (if no transmission is initiated yet, or the packet is just preempted with a state change on the source), Pt = m with probability γm . During the transmission of a packet, it evolves from Pt = m to
Pt+1 = m′ with probability gmm′ , or transmission succeeds with probability hm . The states of the problem are the values of the fourdimensional joint process st = (Xt , Pt , X̂t , AoIIt ), thus the state-space of this problem is S = {N × M × N × N}, where N is the set of non-negative integers. The action space of this MDP is A = {0, 1}, and the action is δt ∈ A. The cost function can be defined as r(st , δt ) = AoIIt +λδt . The formulation can be finalized with the transition probability function ρ(s, a, s′ ) for s = (i, m, j, k), δ = u, and s = (i′ , m′ , j ′ , k ′ ) as γm′ qii′ , u = 0, i′ ̸= i, i ̸= j, j ′ = j k ′ = k + 1, u = 0, i′ = j ̸= i, j ′ = j, k ′ = 0, γm′ qii′ , γm′ qii′ , u = 1, i′ ̸= i, i ̸= j, j ′ = j k ′ = k + 1, gmm′ qii , u = 1, i′ = i, i ̸= j, j ′ = j, k ′ = k + 1, h γ ′ q , u = 1, i′ = i, i ̸= j, j ′ = i k ′ = 0. m m ii (93) Notice that the state-space of this formulation includes infinitely many elements since AoIIt can take any non-negative value. Therefore, in order to obtain the optimum policy using dynamic programming, the AoIIt process should be truncated, giving rise to deviation from the optimality unless truncation is done properly. R EFERENCES [1] A. Bharathidasan and V. A. S. Ponduru, “Sensor networks: An overview,” Dept. Comput. Sci., Univ. California, Davis, CA, USA, Tech. Rep., 2002. [2] S. Kaul, R. Yates, and M. Gruteser, “Real-time status: How often should one update?” in IEEE Infocom, March 2012. [3] 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, May 2021. [4] A. Maatouk, S. Kriouile, M. Assaad, and A. Ephremides, “The age of incorrect information: A new performance metric for status updates,” IEEE/ACM Trans. Netw., vol. 28, no. 5, pp. 2215–2228, October 2020. [5] H. V. Poor, An Introduction to Signal Detection and Estimation. Springer Science & Business Media, 2013. [6] H. Xu, J. Pan, Y. Xu, S. Shao, and T. Song, “Timely gossip on lines: Hybrid ageing,” in IEEE ISIT, July 2025. [7] Y. Chen and A. Ephremides, “Preempting to minimize age of incorrect information under random delay,” 2022, available online at arXiv:2209.14254. [8] A. Maatouk, M. Assaad, and A. Ephremides, “The age of incorrect information: An enabler of semantics-empowered communication,” IEEE Trans. Wireless Comm., vol. 22, no. 4, pp. 2621–2635, October 2022. [9] K. Bountrogiannis, A. Ephremides, P. Tsakalides, and G. Tzagkarakis, “Age of incorrect information with hybrid ARQ under a resource constraint for N -ary symmetric Markov sources,” IEEE/ACM Trans. on Netwk., vol. 33, no. 2, pp. 640–653, November 2024. [10] I. Cosandal, N. Akar, and S. Ulukus, “Modeling AoII in push- and pullbased sampling of continuous time Markov chains,” in IEEE Infocom, May 2024. [11] ——, “Multi-threshold AoII-optimum sampling policies for continuoustime Markov chain information sources,” IEEE Trans. Inf. Theory, vol. 71, no. 9, pp. 6968–6988, July 2024. [12] A. Zakeri, M. Moltafet, and M. Codreanu, “Semantic-aware sampling and transmission in real-time tracking systems: A POMDP approach,” IEEE Trans. Commun., vol. 73, no. 7, pp. 4898–4913, December 2024. [13] A. Arafa, J. Yang, S. Ulukus, and H. V. Poor, “Age-minimal transmission for energy harvesting sensors with finite batteries: Online policies,” IEEE Trans. Inf. Theory, vol. 66, no. 1, pp. 534–556, September 2019.
[14] ——, “Timely status updating over erasure channels using an energy harvesting sensor: Single and multiple sources,” IEEE Trans. Green Comm. Netwk., vol. 6, no. 1, pp. 6–19, August 2021. [15] I. Kahraman, A. Köse, M. Koca, and E. Anarim, “Age of information in internet of things: A survey,” IEEE Internet Things J., vol. 11, no. 6, pp. 9896–9914, October 2023. [16] J. Luo and N. Pappas, “On the cost of consecutive estimation error: Significance-aware non-linear aging,” IEEE Trans. Inf. Theory, vol. 71, no. 10, pp. 7976–7989, July 2025. [17] B. Joshi, R. V. Bhat, B. N. Bharath, and R. Vaze, “Minimization of age of incorrect estimates of autoregressive Markov processes,” in WiOpt, October 2021. [18] C. Schiavo, M. Favero, A. Buratto, and L. Badia, “Bidirectional age of incorrect information: A performance metric for status updates in virtual dynamic environments,” in MetaCom, August 2025. [19] J. G. Kemeny and J. L. Snell, Finite Markov Chains. Springer, 1960. [20] L. Lakatos, L. Szeidl, and M. Telek, Introduction to Queueing Systems with Telecommunication Applications, 2nd ed. New York, NY, USA: Springer, 2019. [21] N. Akar and E. O. Gamgam, “Distribution of age of information in status update systems with heterogeneous information sources: An absorbing Markov chain-based approach,” IEEE Commun. Lett., vol. 27, no. 8, pp. 2024–2028, May 2023. [22] N. Akar and S. Ulukus, “Age of information in a single-source generateat-will dual-server status update system,” IEEE Trans. Commun., vol. 73, no. 9, pp. 7431–7444, February 2025. [23] O. Gursoy and N. Akar, “Energy-age of incorrect information trade-off with timer-based sleep-wake scheduling,” in IEEE PIMRC, September 2025. [24] R. D. Yates, “The age of information in networks: Moments, distributions, and sampling,” IEEE Trans. Inf. Theory, vol. 66, no. 9, pp. 5712–5728, May 2020. [25] M. Moltafet, M. Leinonen, and M. Codreanu, “Moment generating function of age of information in multisource M/G/1/1 queueing systems,” IEEE Trans. Commun., vol. 70, no. 10, pp. 6503–6516, August 2022. [26] L. Scheuvens, T. Hößler, P. Schulz, N. Franchi, A. N. Barreto, and G. P. Fettweis, “State-aware resource allocation for wireless closed-loop control systems,” IEEE Trans. Commun., vol. 69, no. 10, pp. 6604–6619, July 2021. [27] N. Akar, I. Cosandal, and S. Ulukus, “Age-dependent server selection in a dual-server status update system,” in Asilomar Conference, October 2025. [28] D. J. White, Markov Decision Processes. John Wiley & Sons, 1993. [29] G. Strang, Linear Algebra and Its Applications. Cengage Learning, 2006. [30] G. Latouche and V. Ramaswami, Introduction to Matrix Analytic Methods in Stochastic Modeling. SIAM, 1999. [31] R. L. Graham, Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley, 1994. [32] S. M. Ross, Applied Probability Models with Optimization Applications. Dover Publications, 1992. [33] O. Ibe, Markov Processes for Stochastic Modeling. Newnes, 2013. [34] H. C. Tijms, A First Course in Stochastic Models. Wiley, N.Y., 2003. [35] N. Akar and S. Ulukus, “Query-based sampling of heterogeneous CTMCs: modeling and optimization with binary freshness,” IEEE Trans. Commun., vol. 72, no. 12, pp. 7705–7714, December 2024. [36] I. Cosandal, S. Ulukus, and N. Akar, “Joint age-state belief is all you need: Minimizing AoII via pull-based remote estimation,” in IEEE ICC, May 2025. [37] ——, “Which sensor to observe? Timely tracking of a joint Markov source with model predictive control,” in IEEE ISIT, June 2025. [38] S. Bagui and K. Mehra, “The Stirling numbers of the second kind and their applications,” Ala. J. math., vol. 47, no. 1, pp. 1–22, 2024. [39] D. J. Ma, A. M. Makowski, and A. Shwartz, “Estimation and optimal control for constrained Markov chains,” in IEEE CDC, December 1986. [40] K. W. Ross, “Randomized and past-dependent policies for Markov decision processes with multiple constraints,” Operations Research, vol. 37, no. 3, pp. 474–477, May 1989.