RECORD
AoII-Optimum Sampling of CTMC Information Sources Under Sampling Rate Constraints
Information Theory · Submitted 31 Jan 2024
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim We show that this relaxed problem can be solved with a novel CSMDP formulation based on the theory of absorbing MCs, with a computational complexity of $\mathcal{O}(N^4)$, allowing one to obtain optimum policies for general CTMCs with over a hundred states.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
We consider a sensor that samples an $N$-state continuous-time Markov chain (CTMC)-based information source process, and transmits the observed state of the source, to a remote monitor tasked with timely tracking of the source process. The mismatch between the source and monitor processes is quantified by age of incorrect information (AoII), which penalizes the mismatch as it stays longer, and our objective is to minimize the average AoII under an average sampling rate constraint. We assume a perfect reverse channel and hence the sensor has information of the estimate while initiating a transmission or preempting an ongoing transmission. First, by modeling the problem as an average cost constrained semi-Markov decision process (CSMDP), we show that the structure of the problem gives rise to an optimum threshold policy for which the sensor initiates a transmission once the AoII exceeds a threshold depending on the instantaneous values of both the source and monitor processes. However, due to the high complexity of obtaining the optimum policy in this general setting, we consider a relaxed problem where the thresholds are allowed to be dependent only on the estimate. We show that this relaxed problem can be solved with a novel CSMDP formulation based on the theory of absorbing MCs, with a computational complexity of $\mathcal{O}(N^4)$, allowing one to obtain optimum policies for general CTMCs with over a hundred states.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | We consider a sensor that samples an $N$-state continuous-time Markov chain (CTMC)-based information source process, and transmits the observed state of the source, to a remote monitor tasked with timely tracking of the source process. | background 0.96 | 0.28 | 0.02 | asserted 0.90 |
| s1 | The mismatch between the source and monitor processes is quantified by age of incorrect information (AoII), which penalizes the mismatch as it stays longer, and our objective is to minimize the average AoII under an average sampling rate constraint. | background 0.72 | 0.51 | 0.09 | asserted 1.00 |
| s2 | We assume a perfect reverse channel and hence the sensor has information of the estimate while initiating a transmission or preempting an ongoing transmission. | background 0.69 | 0.28 | 0.03 | asserted 1.00 |
| s3 | First, by modeling the problem as an average cost constrained semi-Markov decision process (CSMDP), we show that the structure of the problem gives rise to an optimum threshold policy for which the sensor initiates a transmission once the AoII exceeds a threshold depending on the instantaneous values of both the source and monitor processes. | result 0.64 | 0.94 | 0.50 | asserted 1.00 |
| s4 | However, due to the high complexity of obtaining the optimum policy in this general setting, we consider a relaxed problem where the thresholds are allowed to be dependent only on the estimate. | limitation 0.61 | 0.78 | 0.06 | asserted 0.92 |
| s5 | We show that this relaxed problem can be solved with a novel CSMDP formulation based on the theory of absorbing MCs, with a computational complexity of $\mathcal{O}(N^4)$, allowing one to obtain optimum policies for general CTMCs with over a hundred states. | contribution 0.62 | 0.95 | 0.29 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
We consider a sensor that samples an $N$-state continuous-time Markov chain (CTMC)-based information source process, and transmits the observed state of the source, to a remote monitor tasked with timely tracking of the source process. The mismatch between the source and monitor processes is quantified by age of incorrect information (AoII), which penalizes the mismatch as it stays longer, and our objective is to minimize the average AoII under an average sampling rate constraint. We assume a perfect reverse channel and hence the sensor has information of the estimate while initiating a transmission or preempting an ongoing transmission. First, by modeling the problem as an average cost constrained semi-Markov decision process (CSMDP), we show that the structure of the problem gives rise to an optimum threshold policy for which the sensor initiates a transmission once the AoII exceeds a threshold depending on the instantaneous values of both the source and monitor processes. However, due to the high complexity of obtaining the optimum policy in this general setting, we consider a relaxed problem where the thresholds are allowed to be dependent only on the estimate. We show that this relaxed problem can be solved with a novel CSMDP formulation based on the theory of absorbing MCs, with a computational complexity of $\mathcal{O}(N^4)$, allowing one to obtain optimum policies for general CTMCs with over a hundred states.
Human review
How the literature uses it
What this paper does with the arXiv papers it cites
What it cites · 2 sentences without a confident label
Builds on 1 paper
-
In this work, we extend the analytical model of [ref] to deterministic thresholds and we additionaly obtain the optimum thresholds.
Modeling AoII in Push- and Pull-Based Sampling of Continuous Time Markov Chains · Introduction · 0.89
Uses the method or tool of 1 paper
-
The value of $γ$ under which the budget is met is found by one-dimensional search using the analytical model of [ref] .
Modeling AoII in Push- and Pull-Based Sampling of Continuous Time Markov Chains · Numerical Results · 0.96
Cites as background 2 papers
-
In [ref] , system models with discrete-time Markov chain (DTMC) sources are studied.
Preempting to Minimize Age of Incorrect Information under Transmission Delay · Introduction · 0.81
-
Pull-based sampling of multiple heterogeneous CTMC-based sources are considered in [ref] where the monitors query the sources according to a Poisson process and optimum sampling rates for each source are obtained that maximize several information freshness metrics including weighted binary freshness.
Query-Based Sampling of Heterogeneous CTMCs: Modeling and Optimization with Binary Freshness · Introduction · 0.97
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.