# Age-Dependent Differential Privacy

Meng Zhang, , Ermin Wei, , Randall Berry, , Jianwei Huang  Part of this work
has been presented in ACM Sigmetrics/IFIP Performance 2022 [1]. Meng Zhang is
with Zhejiang University, (E-mail: mengzhang@intl.zju.edu.cn). Ermin Wei and
Randall Berry are with Northwestern University (E-mail:
<EMAIL_ADDRESS>rberry@northwestern.edu). Jianwei Huang is with
The Chinese University of Hong Kong, Shenzhen and the Shenzhen Institute of
Artificial Intelligence and Robotics for Society. (E-mail:
jianweihuang@cuhk.edu.cn). Corresponding authors are Randall Berry and Jianwei
Huang.
This work is supported by the Zhejiang University/University of Illinois at
Urbana-Champaign Institute Starting Fund, the Shenzhen Science and Technology
Program (Project JCYJ20210324120011032), Guangdong Basic and Applied Basic
Research Foundation (Project 2021B1515120008), the Shenzhen Institute of
Artificial Intelligence and Robotics for Society, and NSF grant ECCS-2030251.

###### Abstract

The proliferation of real-time applications has motivated extensive research
on analyzing and optimizing data freshness in the context of age of
information. However, classical frameworks of privacy (e.g., differential
privacy (DP)) have overlooked the impact of data freshness on privacy
guarantees, which may lead to unnecessary accuracy loss when trying to achieve
meaningful privacy guarantees in time-varying databases. In this work, we
introduce age-dependent DP, taking into account the underlying stochastic
nature of a time-varying database. In this new framework, we establish a
connection between classical DP and age-dependent DP, based on which we
characterize the impact of data staleness and temporal correlation on privacy
guarantees. Our characterization demonstrates that aging, i.e., using stale
data inputs and/or postponing the release of outputs, can be a new strategy to
protect data privacy in addition to noise injection in the traditional DP
framework. Furthermore, to generalize our results to a multi-query scenario,
we present a sequential composition result for age-dependent DP under any
publishing and aging policies. We then characterize the optimal tradeoffs
between privacy risk and utility and show how this can be achieved. Finally,
case studies show that to achieve a target of an arbitrarily small privacy
risk in a single-query case, combing aging and noise injection only leads to a
bounded accuracy loss, whereas using noise injection only (as in the benchmark
case of DP) will lead to an unbounded accuracy loss.

##  I Introduction

###  I-A Background

Fresh data has become indispensable for ubiquitous real-time applications,
including Internet-of-things (IoT) systems (e.g., healthcare wearables),
cyber-physical systems (e.g., autonomous transportation systems), and
financial services. For instance, real-time location and velocity information
of motor vehicles is the key to realize reliable and safe autonomous driving,
and real-time stock quotes are essential for developing effective high-
frequency trading strategies in financial markets. The increasing importance
of fresh data has been driving research on a new metric, Age of information
(AoI), to measure the timeliness of the information that a receiver has about
the status of a remote source [2].

An unpredecented amount of personal data is generated in such real-time
applications. This may severely compromise user privacy, as an adversary may
take advantage of this data to infer information about a user. This privacy-
sensitive information may include user identities and user properties, whose
leakage may lead to undesireable consequences. For instance, burglars can use
real-time electricity usage readings (in smart grid systems) to infer whether
there are people at private homes before attempting burglaries; stalkers may
access real-time GPS location data from location-based service providers to
track mobile users.

To combat such privacy leakage, researchers have proposed numerous solutions,
varying in terms of the level of data protection and implementation complexity
(see a survey in [12]). A widely used analytical framework is differential
privacy (DP) [3], which quantifies the level of individual privacy leakage due
to releasing aggregate information from a database. Several companies and
government agencies, such as Apple [4], Google [5], Microsoft [7], and the
U.S. Census Bureau [6], have adopted the framework of DP in their practices.
The key idea of DP is to provide strong privacy guarantees by injecting
tunable levels of noise into the aggregate information before its release,
with the goal of maintaining a proper tradeoff between privacy and statistical
utility of databases.

Despite its privacy guarantees against arbitrary adversaries, existing DP
techniques (and other related classes of privacy metrics such as $k$-Anonymity
[8] and $t$-Closeness [9]) have largely overlooked the impact of data
freshness for time-varying databases. Intuitively, as some data has
diminishing value over time, releasing outdated data may lead to less privacy
leakage if a user only focuses on protecting its real-time status. As an
example, for a mobile user trying to protect its real-time location, the
accuracy of an adversary’s inference (hence the user’s privacy leakage) will
significantly drop as the location data becomes outdated. In a more concrete
example in Section III, we show that the accuracy of an adversary’s estimate
diminishes quickly to a level of no privacy concerns due to data aging,
whereas the classical DP framework can only provide a very loose upper bound
(as high as $88\%$) for the probability an adversary’s estimate is correct.

Figure 1: An age-dependent differential privacy mechanism.

This observation motivates the following key question:

######  Question 1.

How should one quantify the impact of data timeliness on data privacy
protection?

Motivated by Question 1 and the notions of AoI and DP, this work proposes an
age-related generalization of DP that provides more meaningful guarantees for
time-varying datasets. We name it age-dependent differential privacy.

Our new framework is applicable to a wide range of privacy-sensitive
applications with time-varying datasets, such as (i) location-based services
[10], (ii) smart meter readings [11], (iii) medical information, and (iv)
stock holdings in financial markets. Other types of privacy-sensitive
information that are time-invariant (e.g., genome information) can be well
understood under the classical DP notion, hence are not the main focus of this
paper.

Whereas existing studies largely rely on injecting noise to achieve DP [3],
our proposed framework provides a new direction to protect privacy, namely
aging, which postpones the release of outputs. Figure 1 presents an example of
age-dependent differentially private mechanism that combines both the new
method (aging) and the existing one (noise injection). This also raises
another challenge in designing privacy-persevering mechanisms:

######  Question 2.

How should one characterize age-dependent privacy guarantees by leveraging
aging along with classical methods (e.g., noise injection)?

To answer this question, we provide theoretic guarantees achieved by classical
DP mechanisms when adopted in our new age-dependent DP framework. This
establishes a connection between the classical DP notion and our proposed age-
dependent generalization. Additionally, it enables us to derive the achievable
age-dependent privacy guarantees by exploiting both classical methods (e.g.,
noise injection) and aging (e.g., timing inputs and outputs).

The operation of real-time systems involving frequent data updates raises the
necessity of understanding the performance of privacy-preserving mechanisms
with sequential queries, a topic that has been studied for conventional DP
mechanisms through work on sequential composition [41]. Age-dependent DP
mechanisms bring two new challenges compared to these classical results.
First, our characterization further depends on the timing of both inputs (how
stale the input database is for all queries) and outputs (when to release the
outputs of all queries). In contrast, the classical composition results only
depend on the number of queries. The second challenge is that optimally
trading off privacy and utility now depends on optimizing over such timing as
well as any noise that is added, both of which may impact utility and privacy
in different ways. In light of the above challenges, our final key question is

######  Question 3.

How should one characterize the optimal tradeoffs between privacy and utility
for multi-query mechanisms?

To this end, we construct multi-query mechanisms by a combination of single-
query mechanisms, and derive the corresponding privacy guarantees over time
considering the independent guarantees achieved by these single-query
mechanisms and the corresponding timings of inputs and outputs. By deriving
and exploiting a special structure of the optimal solutions, we are then able
to formulate a tractable optimization problem that makes tradeoffs between
privacy and utility.

###  I-B Contributions

We summarize the key contributions of this work in the following:

  * •

Age-dependent DP. To the best of our knowledge, age-dependent DP is the first
performance metric of privacy protection that accounts for the potentially
diminishing privacy leakage of delayed data.

  * •

Privacy guarantee analysis. By establishing the connection between the
classical DP notion and our proposed age-dependent DP, we derive the
achievable privacy guarantees when one exploits aging along with classical DP
mechanisms. We also characterize the key factor that determines the decaying
rate of age-dependent privacy risks over time.

  * •

Composition. We further address how age-dependent DP guarantees compose over
multiple queries, depending on the timing of both inputs and outputs. Even for
infinitely many queries, we show that the peak privacy risk can be upper
bounded under a characterizable condition.

  * •

Tradeoffs. We present two case studies to understand tradeoffs between privacy
and utility. Our numerical studies reveal that, when approaching an arbitrary
small privacy risk in a single-query case, our proposed scheme (of combing
aging and noise injection) only incurs a bounded accuracy loss, whereas the
loss incurred by a benchmark (using noise injection only) grows unbounded.

We organize the rest of this paper as follows. In Section II, we review
related studies. Section III describes the model. In Section IV, we introduce
the definition of age-dependent DP for a single-query mechanism and
characterize its properties. In Section V, we generalize our definition and
results to multi-query mechanisms and characterize how age-dependent DP
guarantees compose. We further present two heuristic examples in Section VI
and finally conclude in Section VII.

##  II Related Work

###  II-A Age of Information

Many works in recent years considered the analysis and optimization for data
freshness, measured by AoI, for different networked systems (e.g., [31, 32,
33, 34, 35, 36, 37, 38, 39, 40] and a survey in [2]). Most studies in this
literature have not considered privacy protection. One exception is [40], in
which Jin et al. studied the an age-minimal mobile crowd sensing system for
location-based services while achieving DP. However, [40] did not consider an
age-based variant of DP, nor the impact of data freshness or temporal
correlation on privacy protection, which we do here.

###  II-B Differential Privacy

There has been a lot of work on DP (see [3]) and we will only survey some
related studies here.

Variants of differential privacy. The initial work on DP [3] makes no
distributional assumption on the data. A number of existing variants of DP
assumed specific knowledge of data generating distributions, which can provide
more meaningful privacy protection under considered scenarios (e.g., [13, 14,
15, 16]). For instance, Rinaldo et al. in [13] studied how data distributions
affect the characterizations of privacy guarantees. Kifer et al. in [16]
proposed a Bayesian framework for defining privacy, the Pufferfish. Yang et
al. in [14] further studied the influence of data correlations on privacy in
the Pufferfish framework. Our approach assumes the knowledge of an underlying
probabilistic model for the time-varying data, whereas these variants mainly
did not account for the impact of data timeliness.

Privacy analysis of dynamic databases. Related studies of DP for dynamic
databases have focused on a limited class of problems (e.g., [18, 22, 23, 24,
26]). Both [18] and [23] adapted the notion of DP to streaming environments,
where each entry in the database is a single bit, and bits arrive one per unit
time. In [22], Smith et al. extended this technique to maintain private sums
of real vectors arriving online in a stream. Mechanisms proposed in [18, 22,
23] are non-adaptive, in the sense that they answer a single query repeatedly
on a dynamic database. Cummings et al. extended in [24] the results to an
adaptive analysis. Nevertheless, this line of work did not characterize the
impact of data timeliness or temporal correlation on data privacy protection.
Reference [26] is the only exception, in which Cao et al. studied the privacy
leakage accounting for continuous data release with time correlation (but not
data timeliness). The composition result in [26] did not account for different
data publishing and aging policies, which we consider in this work.

###  II-C Time-Based Privacy Metrics

Another line of related work considers time-based metrics for privacy, which
only includes a few studies [28, 27, 29]. In [28], Wright et al. proposed a
time-based metric that measures the time until the adversary’s success, which
in fact assumed that the adversary will eventually succeed. On the other hand,
Hoh et al. in [27] considered the mean time to confusion, which measures the
time during which the adversary’s uncertainty stays below a confusion
threshold. For an adversary aiming to track a target’s location over time,
Sampigethaya et al. in [29] considered the maximum tracking time to measure
the adversary’s tracking ability. These studies did not account for the
impacts of the temporal correlation of data or data timeliness on data
privacy.

##  III Model and Preliminary

In this section, we introduce the model of the users, the adversary, and the
stochastic processes of the users’ privacy-sensitive and time-varying
databases. After reviewing the classical notion of DP, we use an illustrative
example to show that DP may not provide an informative description of privacy
protection for time-varying databases. We summarize all key parameters in
Table I.

###  III-A Model

System Overview: We consider a set $\mathcal{I}=\\{1,\dots,I\\}$ of users and
an infinite-horizon discrete-time model with time $t\in\mathbb{N}$. The system
starts to operate at time $t=0$, and $\mathbb{N}$ denotes the set of all non-
negative integers.

User: For each user $i$, its privacy-sensitive data is captured by a discrete-
time stationary process $\\{x_{i,t}\\}_{t\in\mathbb{N}}$. We assume this
process take values in a finite state space, $\mathcal{X}_{i}$. Due to the
stationarity, there exists a stationary probability distribution
$\pi_{i}:\mathcal{X}_{i}\rightarrow[0,1]$, such that $\pi_{i}(x)={\rm
Pr}(x_{i,t}=x)$ for all $t\in\mathbb{N}$. We denote the $t$-step transition
probability by $P_{i,t}(x,y)\triangleq{\rm Pr}[x_{i,t}=y|x_{i,0}=x]$ for all
$t\in\mathbb{N}$ and all $x,y\in\mathcal{X}_{i}$. We further use
$\hat{P}_{i,t}(x,y)$ to denote the $t$-step transition probability of the
reversed process, which satisfies that

$\displaystyle\hat{P}_{i,t}(x,y)=\frac{\pi_{i}(y)P_{i,t}(y,x)}{\pi_{i}(x)},\forall
x,y\in\mathcal{X}_{i},t\in\mathbb{N},i\in\mathcal{I}.$ (1)

If $\hat{P}_{i,t}(x,y)={P}_{i,t}(x,y)$ for all $t\in\mathbb{N}$ and
$x,y\in\mathcal{X}_{i}$, then $\\{x_{i,t}\\}_{t\in\mathbb{N}}$ is reversible
[42].

A class of random processes of particular interest is time-invariant Markov
chains, which are characterized via a time-invariant transition probability
matrix $P_{i}(x,y)$ for each user $i$ and states $x$ and $y$.

Aggregate Database: We use $\\{X_{t}\\}_{t\in\mathbb{N}}$ to denote the
aggregate process across all users, where
$X_{t}\triangleq\\{x_{i,t}\\}_{i\in\mathcal{I}}$ is the random variable of the
(aggregate) database of all users at time $t$, belonging to the (aggregate)
state space $\mathcal{X}=\prod_{i\in\mathcal{I}}\mathcal{X}_{i}$. Throughout
this paper, a database is referred to as the aggregate data of all users
sampled at a time, $X_{t}$. Assuming that the processes are independent across
users, then the corresponding $t$-step transition probability is
$P_{t}(X,Y)=\prod_{i\in\mathcal{I}}P_{i,t}(x_{i},y_{i})$, the stationary
probability is $\pi(X)\triangleq\prod_{i\in\mathcal{I}}\pi(x_{i})$, and the
$t$-step transition probability of the reversed process is $\hat{P}_{t}(X,Y)$,
for all $X=\\{x_{i}\\}_{i\in\mathcal{I}}$, $Y=\\{y_{i}\\}_{i\in\mathcal{I}}$,
and $t\in\mathbb{N}$.

| User $i$’s transition matrix | $P_{i}(\cdot,\cdot)$
---|---|---
| User $i$’s $t$-step transition matrix | $P_{i,t}(\cdot,\cdot)$
| User $i$’s $t$-step transition matrix of the reversed process | $\hat{P}_{i,t}(\cdot,\cdot)$
| User $i$’s stationary distribution | $\pi_{i}(\cdot)$
| Single-query mechanism | $M(\cdot)$
| Multi-query mechanism | $\mathcal{M}_{t}(\cdot,\cdot)$
| Publishing policy | $\mathcal{S}$
| Aging policy | $\mathcal{A}$
| Max. total variation distance | $\Delta(t)$
| Classical DP risk | $\epsilon_{C}$
| Age-dependent privacy risk | $\epsilon(t)$
TABLE I: Key Parameters

Event-Level Privacy Protection Goal: Users seek to protect their data privacy
against a type of adversaries that aim to infer about the current status
$X_{t}$ at each time slot $t\in\mathbb{N}$. That is, the key focus is to
protect each user’s single data point at time $t\in\mathbb{N}$, which is
referred to as the event-level privacy protection [18, 26]. Answering a query
using database $X_{t^{\prime}}$ for some $t^{\prime}<t$ thus leads to less
privacy leakage than using database $X_{t}$, even if $X_{t^{\prime}}$ and
$X_{t}$ may be correlated.

The consideration of such adversaries is practical in a wide range of
application scenarios. Examples include real-time electricity consumption
data, real-time GPS data, and financial data. This can be distinguished from
user-level privacy protection, where an adversary is interested in obtaining
the entire history (or its subset) of a user’s location database
$\\{X_{t}\\}_{t\in\mathcal{T}}$ for some $\mathcal{T}$, e.g., to determine if
a user ever visited a given location with a given time window. We will leave
the modeling of this more general class of adversaries and the corresponding
analysis for future work.

In our analysis, we consider the worst-case scenario where the adversary has
knowledge of the underlying probability models
$\\{P_{i,t}(x,y)\\}_{i\in\mathcal{I}}$, which provides a strong guarantee. We
assume that the platform also has knowledge of
$\\{P_{i,t}(x,y)\\}_{i\in\mathcal{I}}$ and can use it to determine how data
can be released. The platform may gain such knowledge, for example, from
analyzing historical data from the same set of users.

###  III-B Differential Privacy

Here we review the classical notion of DP [3], which can be viewed as if
applying to databases that consist of a single element from a joint-state
space $\mathcal{X}$:

######  Definition 1 (Differential Privacy (DP)).

Given any $\epsilon_{C}>0$, a mechanism (algorithm)
${M}:\mathcal{X}\rightarrow\mathcal{Y}$ is $\epsilon_{C}$-DP if for all pairs
$X,X^{\prime}\in\mathcal{X}$ which differ only in one user’s data, the
following inequality holds

$\displaystyle{\rm Pr}[{M}(X)\in\mathcal{W}]\leq\exp(\epsilon_{C}){\rm
Pr}[{M}(X^{\prime})\in\mathcal{W}],~{}\forall\mathcal{W}\subset\mathcal{Y},$
(2)

where the probability is taken over the randomness of the output of mechanism
$M$.

We use subscript $C$ to indicate that $\epsilon_{C}$ stands for the classical
privacy risk, so as to distinguish it from the privacy risk achievable in our
framework.

DP requires that changing each user’s data will have little impact on the
output when $\epsilon$ is small. It provides a strong and mathematically
rigorous robustness against an arbitrary adversary, but may come at the
expense of the statistical utility (e.g., the accuracy) of the output.

To achieve DP, a well-known approach is to inject Laplace or Gaussian noise to
the database output [3]. Formally, we review the following definitions:

######  Definition 2 (Sensitivity).

For any function $f:\mathcal{X}\rightarrow\mathbb{R}^{d}$, the
$\ell_{1}$-sensitivity of $f$ is defined as

$\displaystyle S^{(f)}=\max_{X,X^{\prime}}\left\lVert
f(X)-f(X^{\prime})\right\rVert_{1},$ (3)

where $X$ and $X^{\prime}$ are neighbouring databases, i.e., $X$ and
$X^{\prime}$ differ only in one user’s data.

######  Definition 3 (Laplace Mechanism).

For any function $f:\mathcal{X}\rightarrow\mathbb{R}^{D}$, the Laplace
mechanism (associated with $f$) is defined as

$\displaystyle\mathcal{M}_{L}(X)=f(X)+\boldsymbol{n},$ (4)

where $\boldsymbol{n}=\\{n_{k}\\}_{k=1}^{D}$ are independent ${\rm
Laplace}(S^{(f)}/\epsilon_{C})$ random variables. A random variable has a
${\rm Laplace}(b)$ distribution if its probability density function is

$\displaystyle
p_{\mathcal{L}}(x|b)=\frac{1}{2b}\exp\left(-\frac{|x|}{b}\right).$ (5)

######  Proposition 1 (Classical Privacy Guarantee [3]).

For any function $f:\mathcal{X}\rightarrow\mathbb{R}^{D}$ with a sensitivity
given in (3), the corresponding Laplace mechanism is $\epsilon_{C}$-DP.

As an example, consider function $f(X)=\sum_{i\in\mathcal{I}}X_{i}/I$, where
$X_{i}\in\\{0,1\\}$ for every $i\in\mathcal{I}$. From Definition 2, we have
$S^{(f)}=1/I$. We use the variance of its outcome to characterize the $L_{2}$
accuracy loss (mean square error) of the Laplace mechanism in (4), given by
${\rm Var}(\mathcal{M}_{L}(X))=2/(\epsilon_{C}^{2}I^{2})$. This implies that a
higher degree of privacy protection (i.e., a small $\epsilon_{C}$) requires a
larger statistical utility loss (i.e., a larger variance ${\rm
Var}(\mathcal{M}_{L}(X))$).

Next we present an example to illustrate that the classical DP privacy
guarantee may not be practical for time-varying databases, as it does not
capture the impact of data freshness on privacy leakage.

###  III-C A Motivating Example

In this subsection, we consider an illustrative example to motivate our
alternative privacy notion.

Consider the following example.111Our example is the same as the motivational
example in [15] except that we consider time-varying databases. There are two
towns: $A$ and $B$. The databases $X,X^{\prime}$ consist of two profiles of
resident income values of town $A$. There is a billionaire $x^{\prime}$ whose
income is orders of magnitude higher than other individuals in either town.
The billionaire occasionally travels between two towns, and the probability
that the billionaire travels to the other town after each day is $10\%$. An
adversary wishes to track down the current location of the billionaire. The
adversary observes the mean income $w$ of town $A$ sanitised by an
$\epsilon_{C}$-DP mechanism. The result $w$ is only published at time $t=0$.
Using a Bayesian estimator, the probability of the adversary being correct is

$\displaystyle P(A)=\frac{1}{1+\exp(-\epsilon_{C})}.$ (6)

For an $\epsilon_{C}$-DP mechanism with $\epsilon_{C}=2$, the attack accuracy
is as high as $P(A)=88\%$.

However, if the adversary obtains this message after $t$ days (still using the
same $\epsilon_{C}$-DP mechanism), we can express the eventual accuracy
$P_{t}(A)$ in the following:

$\displaystyle\begin{bmatrix}P_{t}(A)\\\
1-P_{t}(A)\end{bmatrix}=\begin{bmatrix}P(A)\\\
1-P(A)\end{bmatrix}\cdot\begin{bmatrix}90\%&10\%\\\
10\%&90\%\end{bmatrix}^{t}.$ (7)

That is, the probability of a successful attack becomes $P_{t}(A)\approx 65\%$
when $t=3$ days, $P_{t}(A)\approx 58\%$ when $t=6$ days, and $P_{t}(A)\approx
53\%$ when $t=10$ days. Therefore, the probability of a successful attack
decreases over time and eventually converges to $50\%$ (which corresponds to a
pure random guess).

Moreover, the probability of a successful attack when it receives $w$
immediately with $\epsilon_{C}=0.3$ is approximately the same as when it
observes $w$ after $t=6$ days with $\epsilon_{C}=2$. This shows that aging
provides an alternative to increasing the noise variance for increasing
privacy protection. This motivates us to design an age-dependent
generalization that takes the data timeliness into account in the next
sections.

##  IV Age-Dependent Differential Privacy: The Single-Query Case

In this section, we start with introducing the definition of age-dependent
differential privacy for a single-query mechanism. In the age-dependent DP
framework, we characterize the privacy guarantees achieved by any DP mechanism
considering data freshness and the temporal correlation.

###  IV-A Definitions

Throughout Section IV, we focus on single-query (time-invariant) mechanisms
$M:\mathcal{X}\rightarrow\mathcal{Y}$, where
$\mathcal{X}=\prod_{i\in\mathcal{I}}\mathcal{X}_{i}$ denotes the state space
of an aggregate database (at a specific time instance) and $\mathcal{Y}$ is
the set of all possible outcomes. In Section V, we will provide an extension
to multi-query mechanisms.

We first formally introduce age-dependent DP under the single-query case:

######  Definition 4 (Age-Dependent Differential Privacy).

A single-query mechanism ${M}$ is $(\epsilon,t)$-age-dependent DP for a given
random process $\\{X_{t}\\}$, if, for any pair
${X},{X}^{\prime}\in\mathcal{X}$ which differ only in one user’s data, the
following is true:

$\displaystyle{\rm Pr}[{M}(X_{0})\in\mathcal{W}|X_{t}=X]\leq\exp(\epsilon){\rm
Pr}[{M}(X_{0})\in\mathcal{W}|X_{t}=X^{\prime}],\forall\mathcal{W}\subset\mathcal{Y},$
(8)

where the probability takes into account the randomness of both the output of
mechanism $M$ and the stochastic process of $\\{X_{t}\\}_{t\in\mathbb{N}}$.

Different from classical DP (Definition 1), age-dependent DP (Definition 4)
also accounts for the evolution of the stochastic process
$\\{X_{t}\\}_{t\in\mathbb{N}}$. This also implies that the classical
$\epsilon_{C}$-DP is a special case of the age-dependent DP, i.e.,
$(\epsilon_{C},t=0)$-age-dependent DP. Due to the time homogeneity of
mechanism $M$ and the process $\\{X_{t}\\}_{t\in\mathbb{N}}$, the inequality
(8) still holds when we replace $X_{0}$ and $X_{t}$ in (8) by $X_{k}$ and
$X_{k+t}$, respectively, for any $k\in\mathbb{N}$.

In (8), we interpret $t$ as the age of the output $M(X_{0})$. In particular,
for a process $\\{X_{t}\\}_{t\in\mathbb{N}}$ satisfying some ergodicity or
mixing properties (see Appendix A-F), we have that ${\rm
Pr}[X_{0}|X_{t}]\approx\mu(X_{0})$ as $t$ increases (i.e., $X_{0}$ becomes
more outdated). In other words, as the output data $M(X_{0})$ gets more
outdated, the probabilities conditional on $X_{t}=X$ and $X_{t}=X^{\prime}$
become indistinguishable and hence mechanism $M$ asymptotically becomes
perfectly privacy-preserving.

For any mechanism $M$ achieving $(\epsilon,t)$-age-dependent DP, it is also
possible to construct another mechanism that achieves $\epsilon$-DP:

######  Definition 5 (Artificially Aging Mechanism).

The aging mechanism $M^{t}_{A}$ associated to any arbitrary mechanism $M$ and
a given random process $\\{X_{t}\\}$, is given by

$\displaystyle M^{t}_{A}(X)\triangleq M(X_{-t}),$ (9)

where $X_{-t}$ is a random database generated based on the reversed process
$\hat{P}_{t}$, i.e., $X_{-t}\sim\hat{P}_{t}(X,\cdot)$.

From the definitions of DP and age-dependent DP, we can show that

######  Corollary 1.

An aging mechanism $M^{t}_{A}$ is $\epsilon_{C}$-DP if and only if $M$ is
$(\epsilon_{C},t)$-age-dependent DP.

###  IV-B Properties

Age-dependent DP satisfies some basic properties of the classical DP,
including post-processing resilience (see Appendix A-A). In this subsection,
we will focus on presenting analytical results to understand how privacy
guarantees evolve over time.

####  IV-B1 Total Variation Distance

To understand the temporal correlation of databases, we first present an
important quantity to measure the statistical distance between two probability
distributions.

######  Definition 6 (Total Variation Distance).

The total variation distance between probability distributions $\mu$ and $\pi$
on a finite set $\mathcal{X}$ is defined as

$\displaystyle\delta(\mu,\pi)=\max_{A\subset\mathcal{X}}|\mu(A)-\pi(A)|=\frac{1}{2}\sum_{X\in\mathcal{X}}|\mu(X)-\pi(X)|.$
(10)

To derive age-dependent privacy guarantees for all mechanisms that satisfy the
classical DP, we also need the following definition:

######  Definition 7 (Maximal Total Variation Distance).

The maximal total variation distance $\Delta(t)$ (between any user’s two
$t$-step transition probability distributions of the reversed process) is
defined as

$\displaystyle\Delta(t)\triangleq\max_{i\in\mathcal{I}}\max_{x_{i,0},x_{i,0}^{\prime}\in\mathcal{X}_{i}}\delta\left(\hat{P}_{i,t}(x_{i,0},\cdot),\hat{P}_{i,t}(x_{i,0}^{\prime},\cdot)\right),\forall
t\in\mathbb{N},$ (11)

where $\hat{P}_{i,t}(\cdot,\cdot)$ represents the $t$-step transition
probability matrix of user $i$’s reversed process.

We will use $\Delta(t)$ to characterize the privacy risk, i.e., $\epsilon$ in
Definition 4. A wide range of stochastic processes have a diminishing value of
$\Delta(t)$ over time at some specific rate. As an example, a wide range of
Markov chains satisfy the following related and extensively studied property
[43, 44]:

######  Definition 8 (Geometric Ergodicity [43]).

A Markov chain $\\{X_{t}\\}_{t\in\mathbb{N}}$ with stationary distribution
$\pi(\cdot)$ has the geometric ergodicity property if

$\displaystyle|{\rm Pr}(X_{t}=Y|X_{0}=X)-\pi(Y)|\leq
a(X)\cdot\rho^{-t},~{}\forall t\in\mathbb{N},\forall Y\in\mathcal{X},$ (12)

for some function $a(X)$ and some decay coefficient $\rho<1$.

In addition to ergodicity, another related notation with a potential property
leading to a diminishing value of $\Delta(t)$ is mixing. We present details in
Appendix A-F.

####  IV-B2 Mechanism-Dependent Guarantee

We start with the following theorem to characterize the formal privacy
protection guarantee:

######  Theorem 1 (Mechanism-Dependent Guarantee).

If a mechanism $M$ is $\epsilon_{C}$-DP, then it is also
$(\epsilon(t),t)$-age-dependent DP, where $\epsilon(t)$ satisfies

$\displaystyle\epsilon(t)=\ln\left(1+\Delta(t)\cdot(\exp(\epsilon_{C})-1)\right),~{}\forall
t\in\mathbb{N}.$ (13)

Theorem 1 characterizes an age-dependent privacy guarantee based on the
maximal total variation distance $\Delta(t)$ of the underlying process and the
classical DP guarantee $\epsilon_{C}$. The proof of Theorem 1 mainly involves
showing that two transition probability matrices that are close (i.e.,
$\Delta(t)$ is small) lead to a bounded difference in the likelihoods of the
observed value. We defer the complete proof to Section IV-C.

The significance of Theorem 1 is two-fold. First, it establishes the
connection between the privacy guarantees achieved by classical DP and age-
dependent DP. This provides a methodology to attain privacy guarantees in
(13), by combining noise injection and aging. Second, it indicates that we
only need the maximal total variation distance $\Delta(t)$ of the process
$\\{X_{t}\\}_{t\in\mathbb{N}}$ to characterize such a bound. Note that Theorem
1 holds for any arbitrary processes $\\{X_{t}\\}_{t\in\mathbb{N}}$. When a
process has some additional properties, such as satisfying certain mixing or
geometric ergodicity (aperiodic and recurrent Markov chains on finite state
spaces) properties, $\Delta(t)$ converges to zero at a certain rate (e.g., a
geometric rate). In this case, since $\lim_{x\rightarrow 0}\ln(1+x)/x=1$, (13)
further implies that the age-dependent privacy risk $\epsilon(t)$ converges to
zero at the same rate as $(\exp(\epsilon_{C})-1)\Delta(t)$. Finally, as we
will demonstrate in Section VI, aging along with noise injection may not
necessarily reduce the data utility comparing with noise injection alone.

It is also possible to achieve age-dependent DP without requiring mechanism
$M$ to be $\epsilon_{C}$-DP, as we show next.

######  Theorem 2 (Mechanism-Independent Guarantee).

If each agent $i$’s time-varying database is an irreducible, aperiodic, and
reversible Markov chain $\\{x_{i,t}\\}_{t\in\mathbb{N}}$, any mechanism ${M}$
is $(\epsilon(t),t)$-age-dependent DP satisfying
$\epsilon(t)=\mathcal{O}(\lambda_{*}^{t})$. Here,
$\lambda_{*}=\max\\{\lambda_{1},|\lambda_{m-1}|\\}$, where $\lambda_{1}$ and
$\lambda_{m-1}$ are specific eigenvalues of $P$ (see Lemma 4 in the Appendix).

We present the proof of Theorem 2 in Appendix A-C. In Theorem 2, we use a
different proof technique from the one we use in Theorem 1, which cancels out
the impact of the degree of DP achieved by $M$.

Theorem 2 implies that, even without noise injection, using aging alone can
ensure an age-dependent privacy guarantee with a similar convergence rate.

###  IV-C Proof of Theorem 1

In this subsection, we present the complete proof of Theorem 1. We first
introduce lemmas to characterize the change in expected value when one
introduces a small change in probability distribution (based on the maximal
total variation distance $\Delta(t)$). We then bound the privacy risk
$\epsilon(t)$ based on the privacy risk of DP, $\epsilon_{C}$, and
$\Delta(t)$.

We start with an expected value version of a DP-like probability distribution
bound:

######  Lemma 1.

If $M$ is $\epsilon_{C}$-DP, then for any
${z_{i}},z_{i}^{\prime}\in\mathcal{X}_{i}$, we have

$\displaystyle\mathbb{E}_{\boldsymbol{z}_{-i}\sim\hat{{P}}_{-i,t}(\boldsymbol{x}_{-i},\cdot)}[{\rm
Pr}(\mathcal{M}(z_{i},\boldsymbol{z}_{-i})\in\mathcal{W})]\leq\exp(\epsilon_{C})\mathbb{E}_{\boldsymbol{z}_{-i}\sim\hat{{P}}_{-i,t}(\boldsymbol{x}_{-i},\cdot)}[{\rm
Pr}(\mathcal{M}(z_{i}^{\prime},\boldsymbol{z}_{-i})\in\mathcal{W})],$ (14)

where $\hat{{P}}_{-i,t}(\boldsymbol{x}_{-i},\boldsymbol{z}_{-i})=\prod_{j\neq
i}\hat{P}_{t}({x}_{j},{z}_{j})$ for all $t\in\mathbb{N}$,
$\boldsymbol{x}_{-i}$, $\boldsymbol{z}_{-i}$, and $i\in\mathcal{I}$.

We present the proof in Appendix A-B.

The following Lemma 2 characterizes an upper bound for the change in the
expected value of $x_{i}\in\mathcal{X}_{i}$ when the probability distribution
has a small change (characterized by the maximal total variation distance
$\Delta(t)$):

######  Lemma 2.

Assume that every $x_{i}\in\mathcal{X}_{i}$ satisfy
$~{}~{}~{}\underline{x}_{i}\leq x_{i}\leq\bar{x}_{i}$. Consider a probability
distribution $p(x_{i})$ satisfying $\sum_{x_{i}\in\mathcal{X}_{i}}p(x_{i})=1$,
and the following optimization problem:

$\displaystyle\max_{\boldsymbol{\delta}=\\{\delta(x_{i}):x_{i}\in\mathcal{X}_{i}\\}}\quad$
$\displaystyle\sum_{x_{i}\in\mathcal{X}_{i}}({p}(x_{i})+{\delta}(x_{i})){x}_{i},$
(15a) $\displaystyle{\rm s.t.}\quad$
$\displaystyle\frac{1}{2}\sum_{x_{i}\in\mathcal{X}_{i}}|\delta(x_{i})|=\Delta(t),\sum_{x_{i}\in\mathcal{X}_{i}}{\delta(x_{i})}=0.$
(15b)

The optimal solution is $\delta^{*}(\bar{x}_{i})=\Delta(t)$,
$\delta^{*}(\underline{x}_{i})=-\Delta(t)$, and
$\delta^{*}({x}_{i}^{\prime})=0$ for all other
$x_{i}^{\prime}\in\mathcal{X}_{i}$. The maximal objective value of (15) is

$\displaystyle\sum_{x_{i}\in\mathcal{X}_{i}}p(x_{i})x_{i}+\Delta(t)(\bar{x}_{i}-\underline{x}_{i}).$
(16)

###### Proof.

We prove Lemma 2 by contradiction. Suppose that there exists an optimal
solution $\boldsymbol{\delta}^{*}$ such that $\delta^{*}(x_{i})\neq 0$ for a
$x_{i}\notin\\{\bar{x}_{i},\underline{x}_{i}\\}$. We consider the following
two cases:

  * •

Suppose that there exists an
$x_{i}^{\prime}\notin\\{\bar{x}_{i},\underline{x}_{i}\\}$ such that
$\delta^{*}(x_{i}^{\prime})>0$. We can always construct a new solution
$\bar{\boldsymbol{\delta}}=\\{\delta(x_{i}):x_{i}\in\mathcal{X}_{i}\\}$ such
that $\bar{\delta}({x}_{i}^{\prime})=0$,
$\bar{\delta}(\bar{x}_{i})=\delta^{*}(x_{i}^{\prime})+\delta^{*}(\bar{x}_{i})$,
and $\bar{\delta}(x_{i})=\delta^{*}(x_{i})$ for all other
$x_{i}\notin\\{\bar{x}_{i},{x}_{i}^{\prime}\\}$. It is easy to check that
$\bar{\boldsymbol{\delta}}$ is feasible. In addition, since
$x_{i}^{\prime}<\bar{x}_{i}$, we see
$\sum_{x_{i}\in\mathcal{X}_{i}}x_{i}{\delta}^{*}(x_{i})<\sum_{x_{i}\in\mathcal{X}_{i}}{x}_{i}\bar{{\delta}}(x_{i})$.
Therefore, it contradicts with existence of
$x_{i}^{\prime}\notin\\{\bar{x}_{i},\underline{x}_{i}\\}$ such that
$\delta^{*}(x_{i}^{\prime})>0$ at the optimal solution.

  * •

Suppose that there exists an
$x_{i}^{\prime}\notin\\{\bar{x}_{i},\underline{x}_{i}\\}$ such that
$\delta^{*}(x_{i}^{\prime})<0$. We can always construct a new solution
$\bar{\boldsymbol{\delta}}=\\{\bar{\delta}(x_{i}):x_{i}\in\mathcal{X}_{i}\\}$
such that $\bar{\delta}(x_{i}^{\prime})=0$,
$\bar{\delta}(\underline{x}_{i})=\delta^{*}(x_{i}^{\prime})+\delta^{*}(\underline{x}_{i})$,
and $\bar{\delta}(x_{i})=\delta^{*}(x_{i})$ for all other
$x_{i}\notin\\{\underline{x}_{i},{x}_{i}^{\prime}\\}$. It is easy to check
that $\bar{\boldsymbol{\delta}}$ is feasible. In addition, since
$\underline{x}_{i}<x_{i}^{\prime}$, we see
$\sum_{i\in\mathcal{I}}{x}_{i}{\delta}^{*}(x_{i})<\sum_{i\in\mathcal{I}}{x}_{i}\bar{{\delta}}(x_{i})$.
Therefore, it contradicts with the existence of
$x_{i}^{\prime}\notin\\{\bar{x}_{i},\underline{x}_{i}\\}$ such that
$\delta^{*}(x_{i}^{\prime})<0$ at the optimal solution.

Combining the above two cases, we show that all optimal solutions
$\boldsymbol{\delta}^{*}$ satisfy $\delta^{*}(x_{i}^{\prime})=0$ for all
$x_{i}^{\prime}\notin\\{\bar{x}_{i},\underline{x}_{i}\\}$. It is readily
verified that such an optimal solution should be
$\delta^{*}(\bar{x}_{i})=\Delta(t)$,
$\delta^{*}(\underline{x}_{i})=-\Delta(t)$, which proves Lemma 2. ∎

That is, for any probability distribution $p^{\prime}$ on $\mathcal{X}_{i}$,
such that that total variation distance satisfies
$\delta(p,p^{\prime})\leq\Delta(t)$, Lemma 2 provides an upper bound of
$\sum_{x_{i}\in\mathcal{X}}p^{\prime}(x_{i})x_{i}$ in (16).222In this case,
(16) is only an upper bound, but not necessarily the same maximal value, as we
still need to consider the non-negative constraint that $1\geq
p^{\prime}(x_{i})\geq 0$ for all $x_{i}\in\mathcal{X}_{i}$, which is not
captured by Lemma 2.

In the following, we define
$f(z_{i})=\mathbb{E}_{\boldsymbol{z}_{-i}\sim\hat{P}_{-i,t}(\boldsymbol{x}_{-i},\cdot)}[{\rm
Pr}(\mathcal{M}(z_{i},\boldsymbol{z}_{-i})\in\mathcal{W})]$ and
$p(z_{i})=\hat{P}_{i,t}(x_{i}^{\prime},z_{i})$ for all $i\in\mathcal{I}$. We
set $\underline{z}_{i}\triangleq\arg\min_{z_{i}\in\mathcal{X}_{i}}f({z}_{i})$
and $\bar{z}_{i}\triangleq\arg\max_{z_{i}\in\mathcal{X}_{i}}f({z}_{i})$. It
follows that $1\leq f(z_{i})/f(\underline{z}_{i})\leq\exp(\epsilon)$ for all
$z_{i}\in\mathcal{X}_{i}$ from the definition of $\epsilon$-DP.

For all $z_{i}\in\mathcal{X}_{i}$, all pairs of $x_{i}^{\prime}$ and
${x}_{i}\in\mathcal{X}$, and all $\hat{P}_{i,t}$ with the maximal total
variation distance given in (11), it follows that, for all users $i$,

$\displaystyle\ln\left(\frac{\sum_{{z}_{i}\in\mathcal{X}}\hat{P}_{i,t}(x_{i},z_{i})\sum_{\boldsymbol{z}_{-i}\in\mathcal{X}_{-i}}\prod_{j\neq
i}\hat{P}_{i,t}(x_{j},z_{j}){\rm
Pr}[\mathcal{M}(\boldsymbol{z})\in\mathcal{W}]}{\sum_{{z}_{i}\in\mathcal{X}}\hat{P}_{i,t}(x_{i}^{\prime},z_{i})\sum_{\boldsymbol{z}_{-i}\in\mathcal{X}_{-i}}\prod_{j\neq
i}\hat{P}_{i,t}(x_{j},z_{j}){\rm
Pr}[\mathcal{M}(\boldsymbol{z})\in\mathcal{W}]}\right)$ $\displaystyle=$
$\displaystyle\ln\left(\frac{\mathbb{E}_{z_{i}\sim\hat{P}_{i,t}(x_{i},\cdot)}[f(z_{i})]}{\mathbb{E}_{z_{i}\sim\hat{P}_{i,t}(x_{i}^{\prime},\cdot)}[f(z_{i})]}\right)$
$\displaystyle\overset{(a)}{\leq}$
$\displaystyle\ln\left(\frac{\sum_{z_{i}\neq\\{\underline{z}_{i},\bar{z}_{i}\\}}p(z_{i})f(z_{i})+(\Delta(t)+p(\bar{z}_{i}))f(\bar{z}_{i})+(p(\underline{z}_{i})-\Delta(t))f(\underline{z}_{i})}{\sum_{z_{i}}p(z_{i})f(z_{i})}\right)$
$\displaystyle\overset{(b)}{\leq}$
$\displaystyle\ln\left(\frac{\sum_{z_{i}\neq\\{\underline{z}_{i},\bar{z}_{i}\\}}p(z_{i})f(z_{i})+(\Delta(t)+p(\bar{z}_{i}))f(\bar{z}_{i})+(p(\underline{z}_{i})-\Delta(t))f(\underline{z}_{i})-\sum_{z_{i}\in\mathcal{X}_{i}}p(z_{i})(f(z_{i})-f(\underline{z}_{i}))}{\sum_{z_{i}\in\mathcal{X}_{i}}p(z_{i})f(z_{i})-\sum_{z_{i}\in\mathcal{X}_{i}}p(z_{i})(f(z_{i})-f(\underline{z}_{i}))}\right)$
$\displaystyle=$
$\displaystyle\ln\left(\frac{\Delta(t)f(\bar{z}_{i})+(\sum_{z_{i}\in\mathcal{X}_{i}}p(z_{i})-\Delta(t))f(\underline{z}_{i})}{\sum_{z_{i}\in\mathcal{X}_{i}}p(z_{i})f(\underline{z}_{i})}\right)$
$\displaystyle\overset{(c)}{\leq}$
$\displaystyle\ln\left(1+\Delta(t)(\exp(\epsilon_{C})-1)\right),$ (17)

where $(a)$ is from Lemma 2, $(b)$ is due to the fact that $a/b<(a-c)/(b-c)$
when $a>b>c>0$, and (c) is from Lemma 1.

This completes the proof of Theorem 1.

###  IV-D Summary

This section introduced the notion of age-dependent DP. We characterized how
the age-dependent privacy risk evolves over time and how to achieve age-
dependent DP by exploiting the classical DP and aging. Our analysis reveals
that the key factor of $\\{X_{t}\\}_{t\in\mathbb{N}}$ that determines the
decaying rate is $\Delta(t)$. The analysis in this section is only applicable
to a single-query mechanism $M$, whereas the deployment of real-time
applications in practice relies on publishing data updates frequently. This
motivates us to study the more general case of multiple queries next.

##  V Age-Dependent Differential Privacy: Sequential Composition

In this section, we introduce a more general notion of age-dependent DP for
multi-query mechanisms (e.g., for real-time applications that publish updates
frequently) and present a sequential composition theorem. We will further
discuss how to best trade off privacy and utility (characterized by age of
information).

###  V-A The General Definition and Composition

In a multi-query scenario, the history of all published outputs are visible to
the adversary, which brings a new challenge in characterizing the privacy risk
over time. A fundamental problem in the DP literature is how the overall
privacy level degrades when combining multiple queries, where each query meets
a certain DP guarantee. Such a combination of multiple queries is known as
composition. Characterizing classical sequential composition results usually
depend on the total number of queries (e.g., [41]). As an example, Dwork et
al. in [3] showed that:

######  Proposition 2 (Basic Composition [3]).

Let $M_{n}$ be an $\epsilon_{C,n}$-DP mechanism for all $n\in[N]$. The
composition ${M}^{\prime}(X)$ defined as
${M}^{\prime}(X)=\\{M_{n}(X)\\}_{n=1}^{N}$ is $\epsilon_{C}$-DP for
$\epsilon_{C}=\sum_{n=1}^{N}\epsilon_{C,n}$.

Proposition 2 can only provide a loose privacy guarantee in our case since it
does not capture the impacts of data freshness and the temporal correlation.
Another challenge of analyzing time-varying databases comes from the need to
consider timings of both inputs and outputs: how stale is each input database
used for each query and when each output is published.

To this end, we consider the following notations of an aging policy and a
publishing policy. We use $\mathcal{A}=\\{A_{n}\\}_{n\in\mathbb{N}}$ to denote
the aging policy, where $A_{n}$ indicates the age of the $n$-th input database
used for the $n$-th query. We further use
$\mathcal{S}=\\{S_{n}\\}_{n\in\mathbb{N}}$ to denote the publishing policy,
i.e., $S_{n}$ indicates the time instance that the $n$-th outcome is
published. Given a publishing policy, we name the time interval
$[S_{n},S_{n+1})$ as the $n$-th epoch for all $n$.

Let $\mathcal{H}_{t}$ be the history up to time $t$, given by

$\displaystyle\mathcal{H}_{t}(\mathcal{S},\mathcal{A})$
$\displaystyle\triangleq\\{X_{S_{n}-A_{n}}:n\in\mathbb{N},S_{n}\leq t\\},$
(18)

and let

$\displaystyle N_{t}$ $\displaystyle\triangleq\max~{}n,\quad{\rm s.t.}\quad
S_{n}\leq t,$ (19)

be the the number of queries $N_{t}$ up to time $t$. Furthermore, we define
the general class of (potential multi-query) mechanisms as follows:

######  Definition 9 (Multi-query Mechanism).

A multi-query mechanism $\mathcal{M}_{t}$ is given by

$\displaystyle\mathcal{M}_{t}(\mathcal{H}_{t}(\mathcal{S},\mathcal{A}))$
$\displaystyle\triangleq\\{M_{n}(X_{S_{n}-A_{n}}):n\in\mathbb{N},S_{n}\leq
t\\},$ (20)

where $M_{n}:\mathcal{X}\rightarrow\mathcal{Y}$ is a single-query mechanism
used for the $n$-th query.

Figure 2: Illustration of (a) privacy risks of age-dependent DP and (b) age of
information for a multi-query mechanism.

A multi-query mechanism is constructed based on potentially infinitely many
single-query mechanisms. The $n$-th query uses dataset $X_{S_{n}-A_{n}}$ as
its input, with $S_{n}-A_{n}$ representing the time stamp of the input
dataset, and uses (single-query) mechanism $M_{n}$ and publishes its output at
time $S_{n}$. Further, we label the multi-query mechanism with a time stamp
$t$ so that $\mathcal{M}_{t}(\mathcal{H}_{t}(\mathcal{S},\mathcal{A}))$ stands
for the history of all outputs published no later than time $t$.

We next present the general definition of age-dependent DP associated to
$\mathcal{M}_{t}$, characterized by not only $t$ and $\epsilon$, but also the
publishing and the aging policies:

######  Definition 10 (Age-Dependent Differential Privacy).

A multi-query mechanism $\mathcal{M}_{t}$ is
$(\epsilon(t),{t},\mathcal{S},\mathcal{A})$-age-dependent DP for a given
random process $\\{X_{t}\\}$ if for all $t$, the following inequality holds:

$\displaystyle{\rm
Pr}[\mathcal{M}_{t}(\mathcal{H}_{t}(\mathcal{S},\mathcal{A}))\in\mathcal{W}_{t}|X_{t}=X]\leq\exp(\epsilon){\rm
Pr}[\mathcal{M}_{t}(\mathcal{H}_{t}(\mathcal{S},\mathcal{A}))\in\mathcal{W}_{t}|X_{t}=X^{\prime}],$
(21)

for each pair $X,X^{\prime}\in\mathcal{X}$ which differ only in one user’s
data, and for all output histories
$\mathcal{W}_{t}\subset\mathcal{Y}^{N_{t}}$. We let ${S_{0}}=0$ and
$\epsilon(t)=0$ for all $t\in[0,S_{1})$.

To characterize how the information freshness evolves over time given
$\mathcal{S}$ and $\mathcal{A}$, we consider the following definition of age
of information:

######  Definition 11 (Age of Information [2]).

Given the publishing policy $\mathcal{S}$ and the aging policy $\mathcal{A}$,
we define age of information ${\rm{AoI}(t)}$ as

$\displaystyle{\rm AoI}(t+1)\triangleq\begin{cases}A_{n},&~{}{\rm
if}~{}t+1=S_{n},\\\ {\rm AoI}(t)+1,&~{}{\rm otherwise}.\\\ \end{cases}$ (22)

In other words, age of information represents the time elapsed since the time
stamp of the input database for the most recently published output. It has
been used to estimate the value (e.g., accuracy) of the output of
$M_{n}(X_{S_{n}-A_{n}})$ [2].

Before we present the formal characterization of how the age-dependent privacy
guarantee evolves over time for any multi-query mechanisms, we present an
illustrative example of what the age of information in (22) and the privacy
risk guarantees may look like. As shown in Figure 2, the privacy risk
$\epsilon(t)$ decreases within each epoch (for any $\Delta(t)$ diminishing in
$t$) and spikes at the beginning of the next epoch. Therefore, we define
$\epsilon(S_{n})$ as the in-epoch peak privacy risk for the $n$-th epoch. On
the other hand, the age of information increases within each epoch.

######  Theorem 3 (Composition).

For any multi-query mechanism $\mathcal{M}_{t}$ given in (20), in which each
single-query mechanism $M_{n}$ is $\epsilon_{C,n}$-DP for all
$n\in\mathbb{N}$, and the process $\\{X_{t}\\}_{t\in\mathcal{N}}$ is
Markovian, then mechanism $\mathcal{M}_{t}$ is
$(\epsilon(t),{t},\mathcal{S},\mathcal{A})$-age-dependent DP, where

$\displaystyle\epsilon(t)=\ln\left(1+\Delta\left(t-S_{n}+A_{n}\right)\cdot\left(\exp(\epsilon_{C,n}+\epsilon(S_{n}-A_{n}))-1\right)\right),~{}\forall
t\in[S_{n},S_{n+1}),n\in\mathbb{N},$ (23)

where $\Delta(t)$ is given in (11).

We present the proof of Theorem 3 in Appendix A-D. The result in Theorem 3 has
a recurrent form: the privacy risk $\epsilon(t)$ in the $n$-th epoch (i.e.,
the time interval $[S_{n},S_{n+1})$ depends on some previous in-epoch privacy
risk, $\epsilon(S_{n}-A_{n}))$, as well as the privacy risk of the $n$-th
(single-query) mechanism, $\epsilon_{C,n}$.

Intuitively, similar to Theorem 1, the maximal total variation distance
$\Delta(t-S_{n}+A_{n})$ characterizes the impact of data timeliness on the
privacy guarantee. Theorem 1 generalizes the result in Proposition 2, as (23)
becomes $\epsilon(t)=\epsilon_{C,n}+\epsilon(S_{n}-A_{n})$ when
$\Delta\left(t-S_{n}+A_{n}\right)=1$ (as in a static database). This result in
fact coincides with the basic composition result (for static databases). On
the other hand, several existing studies have provided state-of-art
improvements on composition (e.g., [41, 24]) by considering more sophisticated
composition techniques (e.g. adaptive composition as in [24]). Hence, it may
also be possible to obtain a tighter bound than (23) by combining
sophisticated composition techniques and the impact of data timeliness, which
will be left for future work.

###  V-B Tradeoff Between Privacy and Utility

Theorem 3 only characterizes a privacy risk for each specific time. To
facilitate our analysis of tradeoffs, we need another metric to capture the
overall privacy protection performance over the entire time horizon. We thus
consider the (overall) peak privacy risk:333We note that the literature of age
of information has extensively used peak age of information as their overall
performance metric as well. [2].

$\displaystyle\epsilon^{*}\triangleq\sup_{n}\epsilon(S_{n}).$ (24)

To make the optimal tradeoff between the privacy and utility, we let
$\bar{S}_{n}\triangleq S_{n+1}-S_{n}$ denote the inter-publish time between
the $n$-th and the $(n+1)$-th updates, for all $n\in\mathbb{N}$.

We further define a (noise-aware) peak age penalty, denoted by

$\displaystyle f(\max_{t}{\rm
AoI}(t),\epsilon_{C})=f(A+\bar{S},\epsilon_{C}),$ (25)

where $f(t,\epsilon)$ is increasing in $t$ and decreasing in $\epsilon_{C}$.
Function $f$ measures the accuracy loss of
$M_{t}(\mathcal{H}_{t}(\mathcal{S}^{E},\mathcal{A}^{E}))$ due to data
staleness (characterized by the peak age of information $A+\bar{S}$) and the
injected noise (characterized by $\epsilon_{C}$).

We consider the following optimization problem:

$\displaystyle\min\quad$ $\displaystyle\sup_{n\in\mathbb{N}}\epsilon(S_{n})$
(26a) $\displaystyle\rm{s.t.}\quad$ $\displaystyle
f(A_{n}+\bar{S}_{n},\epsilon_{C,n})\leq\bar{f},\forall n\in\mathbb{N},$ (26b)
$\displaystyle\rm{var.}\quad$ $\displaystyle\epsilon_{n}\geq 0,{A}_{n}\geq
0,\bar{S}_{n}\geq 0,\forall n\in\mathbb{N},$ (26c)

where (26b) stands for an peak age penalty constraint. The challenge in
solving Problem (26) mainly lies in the difficulty of dealing with the
recurrent form of $\epsilon(S_{n})$ instead of a closed form. To optimally
solve Problem (26), we will show in the following that a specific class of
solutions $(\mathcal{S},\mathcal{A},\boldsymbol{\epsilon})$ are optimal. We
can then express $\sup\epsilon(S_{n})$ in a closed form.

Specifically, we consider the following simplified mechanism, defined as:

######  Definition 12 (Simplified Multi-Query Mechanism).

A simplified multi-query mechanism
$(\mathcal{S}^{E}=\\{S_{n}^{E}\\}_{n\in\mathbb{N}},\mathcal{A}^{E}=\\{A_{n}^{E}\\}_{n\in\mathbb{N}})$
is a mechanism in which

$\displaystyle A^{E}_{n}=A,\quad S^{E}_{n+1}-S^{E}_{n}=\bar{S},~{}{\rm
and}~{}\epsilon_{C,n}=\epsilon_{C},~{}\forall n\in\mathbb{N},$ (27)

for some ($A,\bar{S},\epsilon_{C}$).

In other words, a simplified mechanisms is one in which updates are published
at regular intervals and every update is aged the same amount and sent using
the same single-query DP mechanism. By exploiting that the monotonicity of
$\epsilon(S_{n})$ in $n$ and the existence of an optimal solution that have
identical values of $(A_{n}^{*},\bar{S}_{n}^{*},\epsilon_{C,n}^{*})$, we can
prove the existence of an optimal solution satisfying (27) which leads to the
following theorem:

######  Theorem 4.

There exists an optimal solution to (26) that is a simplified multi-query
mechanism, i.e., $A_{n}^{*}=A^{*}$, $\bar{S}_{n}^{*}=\bar{S}^{*}$ and
$\epsilon_{C,n}^{*}=\epsilon_{C}^{*}$ for some
$(A^{*},\bar{S}^{*},\epsilon_{C}^{*})$.

We present the complete proof of Theorem 4 in Appendix A-G. Theorem 4
indicates that there is no need to vary polices across different epoches, and
hence we only need to focus on optimizing three variables
$(A,\bar{S},\epsilon_{C})$.

Figure 3: An illustrative example of the privacy risk $\epsilon(t)$ and the
peak privacy risk for equal-spacing policies. We set $A=2$, $\bar{S}=4$, and
$\epsilon_{C}=0.5$.

In light of Theorem 4, the following shows the peak privacy risk in (24) for a
simplified multi-query mechanism:

######  Proposition 3 (Peak Privacy Risk).

If the process $\\{X_{t}\\}_{t\in\mathbb{N}}$ is Markovian, for a simplified
multi-query mechanism
$\mathcal{M}_{t}(\mathcal{H}_{t}(\mathcal{S}^{E},\mathcal{A}^{E}))$ with an
equal-spacing policy $(\mathcal{S}^{E},\mathcal{A}^{E})$ and each single-query
mechanism $M_{n}$ being $\epsilon_{C}$-DP for all $n\in\mathcal{N}$, the peak
privacy risk is given by the unique fixed point satisfying

$\displaystyle\epsilon^{*}=\ln\left(1+\frac{\Delta(A)\cdot(\exp(\epsilon_{C})-1)}{1-\Delta(A)\Delta(\bar{S}-A)\exp(\epsilon_{C})}\right),$
(28)

whenever $\Delta(A)\Delta(\bar{S}-A)\exp(\epsilon_{C})<1$. Furthermore, the
following fixed-point iteration constitutes a contraction mapping:

$\displaystyle\epsilon(S_{n})=\ln\left(1+\Delta(A)\cdot\left(\exp(\epsilon_{C})\exp(\epsilon(S_{n-1}-A)))-1\right)\right).$
(29)

From (28), we note that $\Delta(A)\Delta(\bar{S}-A)\exp(\epsilon_{C})<1$ is
the condition for the existence of a finite value of $\epsilon^{*}$. That is,
when the inter-publishing time $\bar{S}$ is sufficiently long and the privacy
leakage for each query $\epsilon_{C}$ is sufficiently small, then such a
unique fixed point in (28) exists. Otherwise, the privacy risk
$\epsilon(S_{n})$ diverges to infinity.

###### Proof.

The fixed point expression in (28) comes directly from (23) and (24). In
addition, define

$F(\epsilon)\triangleq\ln\left(1+\Delta(A)\cdot\left(\exp(\epsilon_{C})\exp(\epsilon))-1\right)\right).$

It follows that

$\displaystyle
0<\frac{dF(\epsilon)}{d\epsilon}=\frac{\Delta(A)\cdot\exp(\epsilon_{C})\exp(\epsilon)}{\Delta(A)\cdot\left(\exp(\epsilon_{C})\exp(\epsilon)-1\right)+1}<1,$
(30)

which implies that $F(\epsilon)$ has a Lipschitz constant $0<L<1$. Therefore,
(29) is a contraction mapping. ∎

We present an illustration in Figure 3. We observe that the in-epoch peak
privacy risk $\epsilon(S_{n})$ increases in $n$ and converges to the fixed
point in (28). It only takes $5$ epoches for the privacy risk to approximately
attain the fixed point.

###  V-C Optimization Algorithms

In the following, we consider an optimization problem that accounts for
tradeoffs between privacy and utility. Since many practical stochastic
processes may have a geometrically decaying $\Delta(t)$ as we have shown in
Appendix A-F and Section IV, we are motivated to focus on the following
specific form:

$\displaystyle\Delta(t)=c\cdot\rho^{t},\forall t\in\mathbb{N},$ (31)

for coefficients $\rho\in(0,1)$ and $c\geq 1$.

Instead of (26), we consider the following peak age risk minimization problem:

$\displaystyle\min\quad$
$\displaystyle\ln\left(1+\frac{c\rho^{A}(\exp(\epsilon_{C})-1)}{1-c^{2}\rho^{\bar{S}}\exp(\epsilon_{C})}\right)$
(32a) $\displaystyle{\rm s.t.}~{}\quad$ $\displaystyle
c^{2}\rho^{\bar{S}}\exp(\epsilon_{C})<1,$ (32b) $\displaystyle
f(A+\bar{S},\epsilon_{C})\leq\bar{f},$ (32c) $\displaystyle{\rm var.}\quad$
$\displaystyle\epsilon_{C}\geq 0,A\geq 0,\bar{S}\geq 0,$ (32d)

where the constraint in (32c) indicates that the peak age-of-information
penalty is upper-bounded by a threshold $\bar{f}$. Note that we can drop
constraint $\bar{S}\geq 0$ because (32b) implies that $\bar{S}$ must be
positive. For trackability in (32), we relax the integer constraints on $A$
and $\bar{S}$. After obtaining the optimal solution
($\epsilon_{C}^{*},A^{*},\bar{S}^{*}$) to (32), we can round $A^{*}$ and
$\bar{S}^{*}$ to their respective nearest integers to obtain an approximate
solution.

######  Proposition 4.

When the constraint, $A\geq 0$, is not binding, the optimal solution to
Problem (32) satisfies

$\displaystyle\rho^{\bar{S}}\exp(\epsilon_{C})=\frac{1}{2c^{2}},$ (33)

or equivalently, $\ln(\rho^{-1})\bar{S}=\ln(2c^{2})+\epsilon_{C}$.

This shows that when aging is used ($A>0$), then as $\epsilon_{C}$ decreases
(more privacy due to adding noise) then $\bar{S}$ also decreases meaning that
data is published more often. We prove Proposition 4 by exploiting the
Karush–Kuhn–Tucker conditions of Problem (32), and present the proof in
Appendix A-E.

1

2Initialize $\phi$, $K$, and $\bar{\epsilon}$; for  _$k=\\{1,2,...,K\\}$ _ do

3 Set $\epsilon_{C}(k)=\frac{\bar{\epsilon}k}{K}$ and
$\bar{S}(k)=(\ln(2c^{2})+\epsilon_{C}(k))/\ln(\rho^{-1})$;

// Exhaustive search for $\epsilon_{C}$

4 Set $A_{L}=0$ and $A_{H}=\tilde{A}$, where $\tilde{A}$ satisfies that
$\lim_{\epsilon_{C}\rightarrow\infty}f(\tilde{A},\epsilon_{C}(k))=\bar{f}$;

5 while  _$A_{H}-A_{L}\leq\phi$_ do

// Bisection search for $A$

6 if  _$f(A+\bar{S},\epsilon_{C}(k))\leq\bar{f}$_ then

7 Set $A_{L}=A(k)$;

8 else

9

10 Set $A_{H}=A(k)$;

11 end if

12

13 end while

14

15 end for

16Select $k^{*}=\arg\min\rho^{A(k)}\cdot(\exp(\epsilon_{C}(k))-1)$;

17 return the solution $\\{\epsilon_{C}(k^{*}),A(k^{*}),\bar{S}(k^{*})\\}$.

Algorithm 1 Heuristic Solution to (34)

In light of Proposition 4, we solve the reduced optimization problems of (32)
in the following two cases, depending on whether constraint $A\geq 0$ in (32)
is binding or not:

####  V-C1 When the constraint $A\geq 0$ is not binding

Substituting (33) into Problem (32), we have the following equivalent
reformulated problem:

$\displaystyle\min\quad$ $\displaystyle\rho^{A}\cdot(\exp(\epsilon_{C})-1)$
(34a) $\displaystyle{\rm s.t.}\quad$
$\displaystyle\ln(\rho^{-1})\bar{S}=\ln(2c^{2})+\epsilon_{C},$ (34b)
$\displaystyle f(A+\bar{S},\epsilon_{C})\leq\bar{f},$ (34c) $\displaystyle{\rm
var.}\quad$ $\displaystyle\epsilon_{C}\geq 0,A\geq 0,\bar{S}\geq 0.$ (34d)

Problem (34) is a convex problem whenever $f(t,\epsilon_{C})$ is convex in
$(t,\epsilon_{C})$, in which case Problem (34) can be readily solved by
standard solvers (e.g., CVX [50]). When $f(t,\epsilon_{C})$ is non-convex, we
present a heuristic algorithm to solve Problem (34) as shown in Algorithm 1.
The computational complexity of Algorithm 1 is $\mathcal{O}(K\log(1/\phi))$,
where $K$ comes from the exhaustive search for $\epsilon_{C}$ and
$\log(1/\phi)$ comes from the bisection search for $A$.

####  V-C2 When the constraint $A\geq 0$ is binding

Substituting $A=0$ into Problem (32), we have the following equivalent
reformulated problem:

$\displaystyle\min\quad$
$\displaystyle\frac{\exp(\epsilon_{C})-1}{1-c^{2}\cdot\rho^{\bar{S}}\exp(\epsilon_{C})}$
(35a) $\displaystyle{\rm s.t.}~{}~{}\quad$ $\displaystyle
c^{2}\cdot\rho^{\bar{S}}\exp(\epsilon_{C})<1,$ (35b) $\displaystyle
f(\bar{S},\epsilon_{C})\leq\bar{f},$ (35c) $\displaystyle{\rm var.}\quad$
$\displaystyle\epsilon_{C}\geq 0,\bar{S}\geq 0.$ (35d)

1 Initialize $\phi$, $K$, and $\bar{\epsilon}$;

2

3for  _$k\in\\{1,2,...,K\\}$ _ do

// Exhaustive search for $\epsilon_{C}$

4 Set $\epsilon_{C}(k)=k\bar{\epsilon}/K$;

5 Set $\bar{S}_{L}=0$ and $\bar{S}_{H}=\bar{B}$, where $\bar{B}$ satisfies
that $\lim_{\epsilon_{C}\rightarrow\infty}f(\bar{B},\epsilon_{C})=\bar{f}$ ;

6 while  _$\bar{S}_{H}-\bar{S}_{L}\leq\phi$_ do

// Bisection search for $\bar{S}$

7 if  _$f(\bar{S},\epsilon_{C})\leq\bar{f}$_ then

8 Set $\bar{S}_{L}=\bar{S}(k)$;

9 else

10 Set $\bar{S}_{H}=\bar{S}(k)$;

11 end if

12

13 end while

14

15 end for

16Select
$k^{*}=\arg\min\frac{\exp(\epsilon_{C}(k))-1}{1-c^{2}\cdot\rho^{\bar{S}(k)}\exp(\epsilon_{C}(k))}$;

return the solution $\\{\epsilon_{C}(k^{*}),A=0,\bar{S}(k^{*})\\}$;

Algorithm 2 Heuristic Solution to (35)

We solve Problem (35) in Algorithm 2, in which we set $A=0$ and search for the
optimal $\epsilon_{C}$ exhaustively and use a bisection search for the optimal
$\bar{S}$. Specifically, for each $\epsilon_{C}$, we use a bisection method to
search for the corresponding $\bar{S}$ such that
$f(\bar{S},\epsilon_{C})=\bar{f}$. We then select $\epsilon_{C}$ and the
corresponding optimal $\bar{S}$ to attain the minimal value of the objective
in (35a). Similarly, the complexity of Algorithm 2 is also
$\mathcal{O}(K\log(1/\phi))$.

###  V-D Possibility of No Tradeoffs

Intuitively, increasing privacy will lead to a decrease of utility (measured
by an increase in the peak age penalty function $f$). However, unlike the
single-query mechanism, this tradeoff between privacy and utility in the
multi-query scenario may not exist, i.e., there may be cases where increasing
the bound on the penalty ($\bar{f}$) does not lead to greater peak privacy
risk. We provide a sufficient condition for the non-existence of a tradeoff in
the following corollary:

######  Corollary 2.

If
$f\left(\frac{\ln(\exp(\epsilon_{C})-1)+\epsilon_{C}}{\ln(\rho^{-1})}+a,\epsilon_{C}\right)$
is monotonically decreasing in $\epsilon_{C}$ for any coefficient $a$, then an
increase in $\bar{f}$ does not decrease the minimal objective value in Problem
(32).

We present the proof of Corollary 2 in Appendix A-H. The main idea of the
proof involves showing the possibility of constructing a new solution
$f(A^{\prime}+\bar{S}^{\prime},\epsilon_{C}^{\prime})<f(A+\bar{S},\epsilon_{C})$
while maintaining the peak privacy risk under the condition in Corollary 2.
Corollary 2 implies that sacrificing one of the metrics (privacy or utility)
does not necessarily improve the performance of another. In Section Section
VI-A, we will present concrete examples that satisfy and violate the condition
in Corollary 2.

##  VI Numerical and Experimental Examples

In this section, we consider two concrete examples of modeling the process
$\\{X_{t}\\}$. We first consider a two-state Markov chain, to study the
tradeoffs between age-dependent DP and accuracy loss achieved by our proposed
scheme (by aging and noise injection) and the classical scheme. We further
consider an experiment of our proposed scheme applied to electricity
consumption data. We also consider an autoregressive model and show how our
analysis can also be extended to continuous-valued processes in Appendix A-I.

###  VI-A Two-State Markov Chain

In this subsection, we first consider the following example with two states
[17]:

######  Example 1.

Consider a system of $I$ agents and two locations. We use
$x_{i,t}\in\\{-1,1\\}$ to denote the location at time $t$ of agent $i$ and let
$X_{t}=\\{x_{i,t}\\}_{i\in\mathcal{I}}$. Each agent $i$’s time-varying
database is given by an identical discrete-time Markov chain, with the
following transition probability matrix444We drop the index $i$ in the
matrices for Example 1, as agents’ time-varying databases are identical.:

$\displaystyle P=\begin{pmatrix}1-p&p\\\ q&1-q\end{pmatrix},$ (36)

which can be verified to be reversible. Assuming $|1-p-q|<1$,555If $p=q=0$,
the Markov chain is reducible. If $p=q=1$, the Markov chain is periodic. it
follows that the stationary distribution is $\pi(0)=\frac{q}{p+q}$ and
$\pi(1)=\frac{p}{p+q}$, and the $t$-step transition probability matrix is:

$\displaystyle{P}_{t}$ $\displaystyle=\frac{1}{p+q}\begin{pmatrix}q&p\\\
q&p\end{pmatrix}+\frac{(1-p-q)^{t}}{p+q}\begin{pmatrix}p&-p\\\
-q&q\end{pmatrix}.$ (37)

It follows that

$\displaystyle\left\lVert P_{t,-1}-\pi\right\rVert$
$\displaystyle=\frac{p}{p+q}|1-p-q|^{t},$ (38) $\displaystyle\left\lVert
P_{t,1}-\pi\right\rVert$ $\displaystyle=\frac{q}{p+q}|1-p-q|^{t},$ (39)

where $P_{t,x}(y)=P_{t}(x,y)$ for all $x$, $y\in\\{-1,1\\}$. Therefore, the
maximal total variation distance satisfies

$\displaystyle\Delta(t)$ $\displaystyle=|1-p-q|^{t},\forall t\in\mathbb{N}.$
(40)

Such a two-state Markov chain model may capture several practical scenarios,
e.g., i) the status of a home being empty or not, ii) a user being on a road
at one of two locations. In the latter example, an analyst aims at designing a
mechanism to estimate the current aggregate traffic congestion levels of two
locations (e.g., to estimate the traffic conditions), whereas users may try to
preserve their own location privacy.

We consider a common single-query aggregation mechanism ${M}$ that estimates
the average value of $x_{i,t}$ across all users, e.g., to analyze the overall
traffic conditions:

$\displaystyle M(X_{0})=\frac{1}{I}\sum_{i\in\mathcal{I}}x_{i,0}+n,$ (41)

where $n$ is a ${\rm Laplace}(\frac{1}{\epsilon_{C}I})$ random variable (which
ensures $M$ to be $\epsilon_{C}$-DP by Proposition 1). Based on (41), we
consider two utility metrics:

  * •

Mean-Square Error: We assume no prior information is available and simply use
the given released data $M(X_{0})$ as the estimate. The mean-square error
(MSE) is given by[48]:

$\displaystyle f_{\rm
MSE}(t,\epsilon_{C})=\mathbb{E}\left[\left(M(X_{0})-\frac{1}{I}\sum_{i}x_{i,t}\right)^{2}\right].$
(42)

Such a mean-squared (estimation) accuracy loss is a commonly used age penalty
function (e.g., [2, 30]).

  * •

Failure Rate: Motivated by the age of incorrect information proposed in [53],
we consider a binary estimator. Specifically, based on the outcome of the
mechanism $M(X_{0})$, we seek to determine whether $\sum_{i}x_{i,t}/I\geq 0$
is true (e.g., whether a the traffic at a specific location is congested). Let
$z_{t}$ be an indicator random variable for the event that
$\sum_{i}x_{i,t}/I\geq 0$. The maximum likelihood estimate of $z_{t}$ is given
by:

$\displaystyle g_{\rm MLE}(M(X_{0}))\triangleq\arg\max_{x\in\\{0,1\\}}{\rm
Pr}[z_{t}=x|{M}(X_{0})].$ (43)

We use the following definition of the failure rate (conditional on the
initial state $X_{0}$) as our noise-aware age penalty:

$\displaystyle f_{\rm MLE}(t,\epsilon_{c})={\rm Pr}[g_{\rm MLE}(M(X_{0}))\neq
z_{t}|X_{0}].$ (44)

####  VI-A1 The single-query case

Combining (40) and Theorem 2, we can characterize the achievable privacy
guarantee in the single-query case as follows:

######  Corollary 3.

Any $\epsilon_{C}$-DP single-query ${M}$ under (41) is $(\epsilon(t),t)$-age-
dependent DP, where $\epsilon(t)$ satisfies

$\displaystyle\epsilon(t)=\ln\left(1+|1-p-q|^{t}(\exp(\epsilon_{C})-1)\right),\forall
t\in\mathbb{N}.$ (45)

Figure 4: Numerical results for Example 1 with mean-square errors for single-
query mechanisms. We set $p=q=0.1$ and $I=20$.

####  VI-A2 The multi-query case

We further consider a multi-query mechanism with an equal-spacing policy
described in (27). The privacy guarantee result follows from Proposition 5:

######  Corollary 4.

Any $\epsilon_{C}$-DP multi-query $\mathcal{M}_{t}$ based on (41) is
$(\epsilon(t),{t},\mathcal{S},\mathcal{A})$-age-dependent DP with a peak
privacy risk given by

$\displaystyle\epsilon^{*}=\ln\left(1+\frac{|1-p-q|^{A}\cdot(\exp(\epsilon_{C})-1)}{1-|1-p-q|^{\bar{S}}\exp(\epsilon_{C})}\right).$
(46)

####  VI-A3 Numerical Results

To understand the tradeoffs between privacy and utility for Example 1, we
present numerical results for the mean-squared error and the failure rate
scenarios in Figs. 4 and 5, respectively.

In the mean-square error scenario, we present the accuracy loss and privacy
risk at different ages $t$ in Figs. 4(a) and 4(b), respectively, and the
tradeoffs between privacy risk and accuracy loss in Figure 4(c). In Figure
4(a), we show that the accuracy loss increases in $t$, and for a given
$\epsilon_{C}$, it converges to an upper bound as $t\rightarrow\infty$. This
implies that aging does not necessarily incur significant accuracy loss in
terms of the mean-square error. On the other hand, Figure 4(b) shows that
privacy risks decrease in $t$ and converge to $0$, which is mainly because
$\Delta(t)$ converges to $0$. In Figure 4(c), we compare our proposed
mechanisms against a classical noise only benchmark that only injects Laplace
noise, whose accuracy loss is given by $2/(\epsilon_{C}^{2}I^{2})$. We show
that, to achieve an arbitrary small privacy risk, the accuracy loss incurred
by the benchmark grows unbounded. The large loss is partially because of the
lack of prior information in the considered mean-square error scenario. Our
proposed scheme combines both aging and noise injection and is able to achieve
a finite accuracy loss, as the privacy risk approaches $0$. We note that this
is partially because our age-dependent DP protects privacy specifically from
adversaries seeking to infer $X_{t}$, whereas DP does not assume any type of
data distributions or adversaries.

Figure 5: Numerical results for Example 1 with the failure rate for single-
query mechanisms. Here $p=q=0.1$ and $I=20$.

In the failure rate scenario, we present the accuracy loss and privacy risk
for a single query mechanism at different ages $t$ in Figure 5(a), and the
tradeoffs between privacy risk and accuracy loss in Figures 5(b)(c). Figure
5(a) shows that the accuracy loss increases in $t$ as it does in Figure 4(a),
but at a different rate. The accuracy loss eventually converges to $0.5$ as
$t\rightarrow\infty$. We note that the privacy risks for a given $t$ and
$\epsilon_{C}$ are the same as in the mean-squared error scenario (Figure
4(b)). In terms of the tradeoffs between privacy and accuracy loss, we show
that our proposed scheme can achieve less accuracy loss compared to the noise
only benchmark. In addition, Figure 5(b) also shows that different utility-
privacy pairs require different $t$ and $\epsilon_{C}$. In Figure 5(c), we
present the optimal tradeoffs between privacy and accuracy loss. Compared to
the noise only benchmark, this shows that our proposed scheme can achieve a
reduction up to $1/3$ in accuracy loss given the same privacy risk.

Figure 6: Numerical results for Example 1 with for multi-query mechanisms with
(a) mean-square errors and (b) the failure rate. We set $p=q=0.1$ and $I=20$.

Finally, Figure 6 presents the tradeoffs between privacy and utility in the
multi-query scenario. Figure 6(a) show that there exists a pair that minimizes
both the peak accuracy loss and the peak privacy risk. This is mainly because
the condition in Corollary 2 holds in this case and hence the tradeoff between
privacy and utility does not exist. Figure 6(b) demonstrates the existence of
the optimal tradeoffs between privacy and utility for multi-query mechanisms
in the failure rate scenario, as the condition in Corollary 2 does not hold in
this case. That is, a smaller achievable peak privacy risk leads to a larger
achievable peak accuracy loss.

###  VI-B Electricity Consumption Forecast

In this experiment, we use electricity consumption readings of households in
London provided by [54] to evaluate our proposed scheme. UK Power Networks
recorded Power consumption (in kWh) every 30 minutes between November 2011 and
February 2014. We selected 40 households, with $28,000$ readings per household
on average. We quantized the power values into 12 intervals, resulting in a
Markov chain with $12$ states for each household. Related studies also
considered such a Markov chain formulation of electricity consumption readings
[17]. Our goal is to publish a privacy-preserving approximation to forecast
households’ average electricity consumption. In particular, to evaluate the
privacy risks, we use the following result to estimate an upper bound for the
total variation distance between the transition probability and the stationary
probability:

######  Proposition 5 (Bounds on variation distance [44]).

Let $\\{X_{t}\\}_{t\in\mathbb{N}}$ be an irreducible, aperiodic, and
reversible Markov chain on a finite set $\mathcal{X}$. Then for all
$X\in\mathcal{X}$, $t\in\mathbb{N}$,

$\displaystyle
4\cdot\delta(P_{t}(X,\cdot),\pi)^{2}\leq\frac{1-\pi(X)}{\pi(X)}\lambda_{*}^{2t}.$
(47)

Based on Proposition 5, we can bound the maximal total variation distance
$\Delta(t)$, i.e.,

$\displaystyle\Delta(t)\leq\min\left\\{1,\max_{i\in\mathcal{I}}\max_{x_{i}\in\mathcal{X}_{i}}\sqrt{\frac{1-\pi_{i}(x_{i})}{\pi_{i}(x_{i})}}\lambda_{i,*}^{t}\right\\},$
(48)

where $1-\lambda_{i,*}$ represents the spectral gap of household $i$’s time-
varying database $\\{x_{i,t}\\}_{t\in\mathbb{N}}$.

Figure 7: Experimental results for electricity consumption data of London
households.

In Figure 7, we study the accuracy loss (measured by the MSE between the
released data mean usage and the true mean usage) and the privacy risks of our
single-query mechanism applied to the electricity power dataset for different
$\epsilon_{C}$ values. As shown in Figure 7(a), the accuracy loss first
increases rapidly in $t$ and then remains a relatively constant level, for all
choices of $\epsilon_{C}$ values. In Figure 7(b), we observe that the upper
bound on the privacy risks in (48) are first the same as their corresponding
classical DP risks and then decrease when the age is greater than $18$ hours.
This mainly results from (48), in which the second term
$\max_{i\in\mathcal{I}}\max_{x_{i}\in\mathcal{X}_{i}}\sqrt{\frac{1-\pi_{i}(x_{i})}{\pi_{i}(x_{i})}}$
only becomes less than $1$ when $t\geq 18$ hours.666It is possible to derive a
tighter bound than (48), which is, however, out of the scope of this paper.
Finally, Figure 7(c) depicts the achievable tradeoffs between privacy and
accuracy loss. Similarly, the accuracy loss incurred by the DP benchmark grows
unbounded as the privacy risk approaches zero, while a finite accuracy loss is
always achievable under our proposed scheme that combines both noise injection
and aging.

##  VII Conclusion

In this paper, we proposed an age-dependent generalization of differential
privacy. We characterized the impact of data staleness on data privacy
guarantees and showed that aging provides a new direction to protect data
privacy (in addition to noise injection) based on stale data. Motivated by
frequent data updates in real-time applications, we further characterized how
age-dependent privacy risks compose, given any publishing and aging policies.
Finally, our case studies showed that mechanisms combining aging and noise
injection may significantly outperform the classical mechanisms (that inject
noise only), when making tradeoffs between privacy and utility.

As a first study on understanding the impact of data freshness on privacy,
there are many future research directions. First, our work assumes that the
adversary is only interested in keeping track on the most current state of
some user. One potential direction is to extend our results to different
adversary models, e.g., adversaries that aim to infer a subset of the entire
history of users’ databases. Second, it is interesting to study adaptive
composition to enhance the privacy guarantees for multi-query mechanisms.

## References

  * [1] M. Zhang, E. Wei, R. Berry, and J. Huang, “Age-dependent differential privacy”, ACM Sigmetrics/IFIP PERFORMANCE, pp. 115-116, June 2022.
  * [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 Journal on Selected Areas in Communications, vol. 39, no. 5, pp. 1183-1210, 2021.
  * [3] C. Dwork, “Differential privacy,” Proc. 33rd International Colloquium on Automata, Languages and Programming, part II (ICALP 2006), vol. 4052, pp. 1–12, Venice, Italy, July 2006.
  * [4] Differential Privacy Team Apple, Learning with privacy at scale. Technical report, Apple, 2017.
  * [5] Ú. Erlingsson, V. Pihur, and A. Korolova, “Rappor: Randomized aggregatable privacy-preserving ordinal response,” in Proc. ACM SIGSAC Conf. Comput. Commun. Sec. (CCS), pp. 1054–1067, 2014.
  * [6] J. M. Abowd, “The challenge of scientific reproducibility and privacy protection for statistical agencies,” Census Scientific Advisory Committee, 2016.
  * [7] B. Ding, J. Kulkarni, and S. Yekhanin, “Collecting telemetry data privately,” in Proc. Advances in Neural Information Processing Systems (NIPS), 2017.
  * [8] P. Samarati and L. Sweeney, “Generalizing data to provide anonymity when disclosing information,” in Proc. ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS), Seattle, WA, USA, 1998.
  * [9] N. Li, Tiancheng Li, and S. Venkatasubramanian, “t-Closeness: Privacy beyond k-anonymity and l-diversity,” in Proc. IEEE Int. Conf. Data Engineering (ICDE’), IEEE, 106–115.
  * [10] R. Shokri, G. Theodorakopoulos, J. Y. Le Boudec, and J. P. Hubaux, “Quantifying location privacy,” in Proc. 2011 IEEE symposium on security and privacy (pp. 247-262), 2011, May.
  * [11] I. Rouf, H Mustafa, M. Xu, W. Xu, R. Miller, and M. Gruteser, “Neighborhood watch: Security and privacy analysis of automatic meter reading systems,” in Proc. ACM Conf Comput. Commun. Sec., pp. 462-473, 2012, October.
  * [12] I. Wagner and D. Eckhoff, “Technical privacy metrics: a systematic survey,” ACM Computing Surveys (CSUR), 51(3), pp.1-38, 2018.
  * [13] R. Hall, A. Rinaldo, and L. Wasserman, “Random differential privacy,” 2011. ArXiv preprint: 1112.2680.
  * [14] B. Yang, I. Sato, and H. Nakagawa, “Bayesian differential privacy on correlated data,” in Proc. ACM SIGMOD international conference on Management of Data, pp. 747-762, May 2015.
  * [15] A. Triastcyn and B. Faltings, “Bayesian differential privacy for machine learning,” in International Conf. Machine Learning (PMLR), (pp. 9583-9592). 2020, November.
  * [16] D. Kifer and A. Machanavajjhala, “Pufferfish: A framework for mathematical privacy definitions,” ACM Trans. Database Syst., vol. 39, no. 1, pp. 3-36, Jan. 2014.
  * [17] S. Song, Y. Wang, and K. Chaudhuri, “Pufferfish privacy mechanisms for correlated data,” in Proc. the 2017 ACM International Conference on Management of Data (SIGMOD ’17), New York, NY, USA, 1291–1306, 2017.
  * [18] C. Dwork, M. Naor, T. Pitassi, and G. N. Rothblum, “Differential privacy under continual observation,” in Proc. ACM symposium on Theory of computing (STOC), pp. 715-724, June 2010.
  * [19] A. Blum, K. Ligett, and A. Roth, “A learning theory approach to non-interactive database privacy,” in Proc. ACM symposium on Theory of computing (STOC), pp. 609–618, 2008.
  * [20] M. Hardt and G. N. Rothblum. “A multiplicative weights mechanism for privacy-preserving data analysis,” in Proc. IEEE Symposium on Foundations of Computer Science (FOCS), pp. 61–70, 2010.
  * [21] C. Dwork, V. Feldman, M. Hardt, T. Pitassi, O. Reingold, and A. Roth, “The reusable holdout: Preserving validity in adaptive data analysis,” Science, vol. 349, no. 6248, pp: 636–638, 2015.
  * [22] A. Smith and A. G. Thakurta, “(Nearly) optimal algorithms for private online learning in full information and bandit settings,” in Proc. Advances in Neural Information Processing Systems (NIPS), pp. 2733—2741, 2013.
  * [23] T.-H. H. Chan, E. Shi, and D. Song, “Private and continual release of statistics,” ACM Trans. Info. Syst. Sec., 14(3):26, 2011.
  * [24] R. Cummings, S. Krehbiel, K. A. Lai, and U. Tantipongpipat, “Differential privacy for growing databases,” in Advances in Neural Information Processing Systems, pp. 8864–8873, 2018.
  * [25] F. Farokhi, “Temporally discounted differential privacy for evolving datasets on an infinite horizon,” in Proc. ACM/IEEE International Conference on Cyber-Physical Systems (ICCPS), 2020.
  * [26] Y. Cao, M. Yoshikawa, Y. Xiao and L. Xiong, “Quantifying differential privacy in continuous data release under temporal correlations,” in IEEE Transactions on Knowledge and Data Engineering, vol. 31, no. 7, pp. 1281-1295, 1 July 2019.
  * [27] B. Hoh, M. Gruteser, H. Xiong, and A. Alrabady, “Preserving privacy in GPS traces via uncertainty-aware path cloaking,” in Proc. ACM conference on Computer and communications security (CCS). New York, NY, USA, 161–171. 2007.
  * [28] M. Wright, M. Adler, B. N. Levine, and C. Shields, “An analysis of the degradation of anonymous protocols,” in Proc. Network and Distributed System Security Symp. (NDSS’02), Vol. 2. 39–50, 2002.
  * [29] K. Sampigethaya, L. Huang, M. Li, R. Poovendran, K. Matsuura, and K. Sezaki, “ARAVAN: Providing location privacy for VANET,” in Embedded Security in Cars (ESCAR’05). 29–37, 2005.
  * [30] 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, Mar. 2019.
  * [31] Q. He, D. Yuan, and A. Ephremides, “Optimal link scheduling for age minimization in wireless systems,” IEEE Trans. Inf. Theory, vol. 64, no. 7, pp. 5381-5394, July 2018.
  * [32] C. Kam, S. Kompella, and A. Ephremides, “Age of information under random updates,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), 2013.
  * [33] Y. Sun, E. Uysal-Biyikoglu, R. D. Yates, C. E. Koksal, and N. B. Shroff, “Update or wait: How to keep your data fresh,” IEEE Trans. Inf. Theory, vol. 63, no. 11, pp. 7492-7508, Nov. 2017.
  * [34] A. M. Bedewy, Y. Sun, S. Kompella, N. B. Shroff, “Optimal sampling and scheduling for timely status updates in multi-source networks,” IEEE Trans. Inf. Theory, vol. 67, no. 6, pp. 4019-4034, June 2021
  * [35] R. Talak, S. Karaman and E. Modiano, “Optimizing Information Freshness in Wireless Networks Under General Interference Constraints,” in IEEE/ACM Trans. Netw., vol. 28, no. 1, pp. 15-28, Feb. 2020
  * [36] I. Kadota, A. Sinha and E. Modiano, “Scheduling Algorithms for Optimizing Age of Information in Wireless Networks With Throughput Constraints,” in IEEE/ACM Trans. Netw., vol. 27, no. 4, pp. 1359-1372, Aug. 2019.
  * [37] Y. Sun and B. Cyr, “Sampling for data freshness optimization: Non-linear age functions,” J. Commun. Netw., vol. 21, no. 3, pp. 204-219, 2019.
  * [38] M. Zhang, A. Arafa, J. Huang and H. V. Poor, “Pricing Fresh Data,” IEEE Journal on Selected Areas in Communications, vol. 39, no. 5, pp. 1211-1225, May 2021.
  * [39] M. Zhang, A. Arafa, E. Wei and R. Berry, “Optimal and Quantized Mechanism Design for Fresh Data Acquisition,” IEEE Journal on Selected Areas in Communications, vol. 39, no. 5, pp. 1226-1239, May 2021.
  * [40] R. Jin, X. He and H. Dai, “Minimizing the Age of Information in the Presence of Location Privacy-Aware Mobile Agents,” IEEE Trans. Commun., vol. 69, no. 2, pp. 1053-1067, Feb. 2021.
  * [41] P. Kairouz, S. Oh, and P. Viswanath, “The composition theorem for differential privacy,” in International conference on machine learning, pp. 1376-1385, PMLR, 2015.
  * [42] D. A. Levin and Y. Peres. “Markov chains and mixing times,” vol. 107. American Mathematical Soc., 2017.
  * [43] R. C. Bradley, “Basic properties of strong mixing conditions. A survey and some open questions,” arXiv preprint math/0511078, 2005.
  * [44] P. Diaconis and D. Stroock, “Geometric bounds for eigenvalues of Markov chains,” The Annals of Applied Probability, pp.36-61, 1991.
  * [45] H. J. Landau and A. M. Odlyzko, “Bounds for eigenvalues of certain stochastic matrices,” Linear algebra and its Applications, 38, pp.5-15, 1981.
  * [46] S. Cambanis and I. Fakhre-Zakeri, “Forward and reversed time prediction of autoregressive sequences,” Journal of applied probability, vol. 33, no. 4, pp.1053-1060, 1996.
  * [47] A. Triastcyn, B. Faltings, “Bayesian Differential Privacy for Machine Learning,” in Proc. International Conference on Machine Learning, 2020.
  * [48] D. Guo, S. Shamai, and S. Verdú, “Mutual information and minimum mean-square error in Gaussian channels,” IEEE Trans. Inf. Theory, 51(4), pp.1261-1282, 2005.
  * [49] Fintel, “Berkshire Hathaway Inc - Filing History”. Avaiable: https://fintel.io/i13fs/berkshire-hathaway.
  * [50] M. Grant, S. Boyd, and Y. Ye, CVX: Matlab software for disciplined convex programming, 2009.
  * [51] S. Boyd and L. Vandenberghe, Convex optimization. Cambridge university press, 2004.
  * [52] Stroock, Daniel W. Probability theory: an analytic view. Cambridge university press, 2010.
  * [53] 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, 2020.
  * [54] UK Power Networks, “SmartMeter Energy Consumption Data in London Households,” 2013. Available: https://data.london.gov.uk/dataset/smartmeter-energy-use-data-in-london-households

##  Appendix A Appendix

###  A-A Basic Properties

######  Proposition 6 (Post-processing).

Let $M:\mathcal{X}\rightarrow\mathcal{Y}$ be a single-query
$(\epsilon,t)$-age-dependent differentially private mechanism. Then, for any
mapping $f:\mathcal{Y}\rightarrow\mathcal{Y}^{\prime}$,
$f(M(\mathcal{X}_{0}))$ is $(\epsilon,t)$-age-dependent differentially
private.

###### Proof.

By the definition of age-dependent DP in Definition 4, we have:

$\displaystyle{\rm
Pr}[{M}(X_{0})\in\mathcal{W}|X_{t}=\boldsymbol{x}]\leq\exp(\epsilon){\rm
Pr}[{M}(X_{0})\in\mathcal{W}|X_{t}=\boldsymbol{x}^{\prime}],$ (49)

for any set of outcomes $\mathcal{W}\subset\mathcal{Y}$.

For a mapping $f(\cdot)$, it follows that

$\displaystyle{\rm Pr}[f({M}(X_{0}))\in\mathcal{T}|X_{t}=\boldsymbol{x}]$
$\displaystyle={\rm Pr}[{M}(X_{0})\in\mathcal{W}|X_{t}=\boldsymbol{x}]$
$\displaystyle\leq\exp(\epsilon){\rm
Pr}[{M}(X_{0})\in\mathcal{W}|X_{t}=\boldsymbol{x}^{\prime}]$
$\displaystyle=\exp(\epsilon){\rm
Pr}[f({M}(X_{0}))\in\mathcal{T}|X_{t}=\boldsymbol{x}^{\prime}]$ (50)

where $\mathcal{W}=f^{-1}[\mathcal{T}]$, i.e. $\mathcal{S}$ is the preimage of
$\mathcal{T}$ under mapping $f$. ∎

###  A-B Proof of Lemma 1

It follows from the definition of $\epsilon_{C}$-DP that

$\displaystyle\hat{{P}}_{-i,t}(\boldsymbol{x}_{-i},\boldsymbol{z}_{-i}){\rm
Pr}(\mathcal{M}(z_{i},\boldsymbol{z}_{-i})\in\mathcal{W})\leq\exp(\epsilon_{C})\hat{{P}}_{-i,t}(\boldsymbol{x}_{-i},\boldsymbol{z}_{-i}){\rm
Pr}(\mathcal{M}(z_{i}^{\prime},\boldsymbol{z}_{-i})\in\mathcal{W})$ (51)

for all $\boldsymbol{x}_{-i}$,
$\boldsymbol{z}_{-i}\in\mathcal{X}_{-i}\triangleq\prod_{j\neq
i}\mathcal{X}_{j}$, and any pair of $z_{i}$ and
$z_{i}^{\prime}\in\mathcal{X}_{i}$. Summing (51) over all
$\boldsymbol{z}_{-i}\in\mathcal{X}_{-i}$ yields Lemma 1.

###  A-C Proof of Theorem 2

In Lemma 2, we bound
$\sum_{i\in\mathcal{X}_{i}}\left(p(x_{i})+\delta(x_{i})\right)x_{i}$ based on
both the constraint on $\delta(x_{i})$ and the bound of $x_{i}$. The key
difference in this proof from that of Theorem 1 is that we consider a lemma
which does not require the bound of $x_{i}$, based on which we can prove
Theorem 2. We start with such a lemma:

######  Lemma 3.

For any part of vectors with lengths $K$ denoted by
$\\{a_{1},a_{2},...,a_{k}\\}$ and $\\{b_{1},b_{2},...,b_{k}\\}$, if
$g\leq\frac{a_{k}}{b_{k}}\leq G,$ then
$g\leq\frac{\sum_{k=1}^{K}a_{k}}{\sum_{k=1}^{K}b_{k}}\leq G.$

###### Proof.

We can prove Lemma 3 by summing $b_{k}g\leq{a_{k}}\leq b_{k}G$ all over $1\leq
k\leq K$, and the dividing the all sides of the resultant inequality by
$\sum_{k=1}^{K}b_{k}$. ∎

Without loss of generality, we assume that $X$ and $X^{\prime}$ only differs
in the $i$-th user’s data, i.e., we have $X=\\{x_{i}\\}_{i\in\mathcal{I}}$ and
$X^{\prime}=\\{x_{1},...,x_{i-1},x_{i}^{\prime},x_{i},...,x_{I}\\}$. It
follows that

$\displaystyle\ln\left(\frac{{\rm Pr}[M(X_{0})\in\mathcal{W}|X_{t}=X]}{{\rm
Pr}[M(X_{0})\in\mathcal{W}|X_{t}=X^{\prime}]}\right)=$
$\displaystyle\ln\left(\frac{\sum_{\boldsymbol{z}\in\mathcal{X}}{\rm
Pr}[M(\boldsymbol{z})\in\mathcal{W}]{\rm
Pr}[X_{0}=\boldsymbol{z}|X_{t}=X]}{\sum_{\boldsymbol{z}\in\mathcal{X}}{\rm
Pr}[M(\boldsymbol{z})\in\mathcal{W}]{\rm
Pr}[X_{0}=\boldsymbol{z}|X_{t}=X^{\prime}]}\right)$ $\displaystyle=$
$\displaystyle\ln\left(\frac{\sum_{{z}_{i}\in\mathcal{X}_{i}}\hat{P}_{i,t}(x_{i},z_{i})\sum_{\boldsymbol{z}_{-i}\in\mathcal{X}_{-i}}\prod_{j\neq
i}\hat{P}_{j,t}(x_{j},z_{j}){\rm
Pr}[M(\boldsymbol{z})\in\mathcal{W}]}{\sum_{{z}_{i}\in\mathcal{X}_{i}}\hat{P}_{i,t}(x_{i}^{\prime},z_{i})\sum_{\boldsymbol{z}_{-i}\in\mathcal{X}_{-i}}\prod_{j\neq
i}\hat{P}_{j,t}(x_{j},z_{j}){\rm Pr}[M(\boldsymbol{z})\in\mathcal{W}]}\right)$
$\displaystyle=$
$\displaystyle\ln\left(\frac{\mathbb{E}_{z_{i}\sim\hat{P}_{i,t}(x_{i},\cdot)}\\{\mathbb{E}_{\boldsymbol{z}_{-i}\sim\hat{P}_{i,t}(\boldsymbol{x}_{-i},\cdot)}[{\rm
Pr}(M(\boldsymbol{z})\in\mathcal{W})]\\}}{\mathbb{E}_{z_{i}\sim\hat{P}_{i,t}(x_{i}^{\prime},\cdot)}\\{\mathbb{E}_{\boldsymbol{z}_{-i}\sim\hat{P}_{i,t}(\boldsymbol{x}_{-i},\cdot)}[{\rm
Pr}(M(\boldsymbol{z})\in\mathcal{W})]\\}}\right)$
$\displaystyle\overset{(a)}{\leq}$
$\displaystyle\ln\left(\max_{x_{i},x_{i}^{\prime},z_{i}}\frac{\hat{P}_{i,t}(x_{i},z_{i})}{\hat{P}_{i,t}(x^{\prime}_{i},z_{i})}\right)$
$\displaystyle\overset{(b)}{\leq}$
$\displaystyle\max_{{x}_{i},{x}_{i}^{\prime},{z}_{i}}\frac{P_{i,t}(z_{i},x_{i})-P_{i,t}(z_{i},x_{i}^{\prime})}{P_{i,t}(z_{i},x_{i}^{\prime})}$
$\displaystyle\overset{(c)}{\leq}$
$\displaystyle\max_{z_{i}}\frac{\sqrt{\frac{1-\pi(z_{i})}{\pi(z_{i})}}\lambda_{*}^{t}}{\pi(z_{i})-\sqrt{\frac{1-\pi(z_{i})}{4\pi(z_{i})}}\lambda_{*}^{t}}=\mathcal{O}(\lambda_{*}^{t}),$
(52)

where (a) is due to Claim 1 and the fact that $X$ and $X^{\prime}$ only
differs in the $i$-th user’s data; (b) is because $\ln(1+x)\leq x$; (c) is
from Proposition LABEL:P1.

This completes the proof of Theorem 2.

###  A-D Proof of Theorem 3

Let us first rewrite
$\mathcal{M}_{t}(\mathcal{H}_{t}(\mathcal{S},\mathcal{A}))$ into
$[\mathcal{M}_{S_{n-1}}(\mathcal{H}_{S_{n-1}}(\mathcal{S},\mathcal{A}))~{}~{}M_{n}(X_{S_{n}-A_{n}})]$
for $t\in(S_{n-1},S_{n}]$. For notational simplicity in this proof, we denote
$\mathcal{M}_{S_{n-1}}$ by $\mathcal{M}^{\prime}$ and $M_{n}$ by ${M}$,
respectively. We further denote $\mathcal{H}_{t}(\mathcal{S},\mathcal{A})$ and
$X_{S_{n}-A_{n}}$ by $\boldsymbol{z}^{(1)}$ and $\boldsymbol{z}^{(2)}$,
respectively.

For

$\displaystyle\ln\left(\frac{{\rm
Pr}[\mathcal{M}^{\prime}\in\mathcal{W}_{t},{M}(X_{S_{n}-A_{n}})\in\mathcal{W}_{S_{n}-A_{n}}|X_{t}=X]}{{\rm
Pr}[\mathcal{M}^{\prime}\in\mathcal{W}_{t},{M}(X_{S_{n}-A_{n}})\in\mathcal{W}_{S_{n}-A_{n}}|X_{t}=X^{\prime}]}\right)$
$\displaystyle=$
$\displaystyle\ln\left(\frac{\sum_{\boldsymbol{z}^{(1)}}\sum_{\boldsymbol{z}^{(2)}}{\rm
Pr}[\mathcal{M}^{\prime}(\boldsymbol{z}^{(1)})\in\mathcal{W}_{1}]{\rm
Pr}[M(\boldsymbol{z}^{(2)})\in\mathcal{W}_{2}]{\rm
Pr}[X_{S_{n-1}}=\boldsymbol{z}^{(1)},X_{S_{n}-A_{n}}=\boldsymbol{z}^{(2)}|X_{t}=X]}{\sum_{\boldsymbol{z}^{(1)}}\sum_{\boldsymbol{z}^{(2)}}{\rm
Pr}[\mathcal{M}^{\prime}(\boldsymbol{z}^{(1)})\in\mathcal{W}_{1}]{\rm
Pr}[M(\boldsymbol{z}^{(2)})\in\mathcal{W}_{2}]{\rm
Pr}[X_{S_{n-1}}=\boldsymbol{z}^{(1)},X_{S_{n}-A_{n}}=\boldsymbol{z}^{(2)}|X_{t}=X^{\prime}]}\right)$
$\displaystyle=$ $\displaystyle\ln\left(\frac{{\sum_{\boldsymbol{z}^{(2)}}{\rm
Pr}[X_{S_{n}-A_{n}}=\boldsymbol{z}^{(2)}|X_{t}=\boldsymbol{x}]{\rm
Pr}[M(\boldsymbol{z}^{(2)})\in\mathcal{W}_{2}]{\rm
Pr}[\mathcal{M}^{\prime}(X_{S_{n}-A_{n}})\in\mathcal{W}_{1}|X_{S_{n}-A_{n}}=\boldsymbol{z}^{(2)}]}}{\sum_{\boldsymbol{z}^{(2)}}{\rm
Pr}[X_{S_{n}-A_{n}}=\boldsymbol{z}^{(2)}|X_{t}=\boldsymbol{x}^{\prime}]{\rm
Pr}[M(\boldsymbol{z}^{(2)})\in\mathcal{W}_{2}]{\rm
Pr}[\mathcal{M}^{\prime}(X_{S_{n}-A_{n}})\in\mathcal{W}_{1}|X_{S_{n}-A_{n}}=\boldsymbol{z}^{(2)}]}\right)$
$\displaystyle=$
$\displaystyle\ln\left(\frac{\mathbb{E}_{\boldsymbol{z}^{(2)}\sim\hat{P}_{t_{2}}(\boldsymbol{x},\cdot)}\left[{\rm
Pr}({M}(\boldsymbol{z}^{(2)})\in\mathcal{W}_{2})\cdot{\rm
Pr}[\mathcal{M}^{\prime}(X_{S_{n}-A_{n}})\in\mathcal{W}_{1}|X_{S_{n}-A_{n}}=\boldsymbol{z}^{(2)}]\right]}{\mathbb{E}_{\boldsymbol{z}^{(2)}\sim\hat{P}_{t_{2}}(\boldsymbol{x}^{\prime},\cdot)}\left[{\rm
Pr}({M}(\boldsymbol{z}^{(2)})\in\mathcal{W}_{2})\cdot{\rm
Pr}[\mathcal{M}^{\prime}(X_{S_{n}-A_{n}})\in\mathcal{W}_{1}|X_{S_{n}-A_{n}}=\boldsymbol{z}^{(2)}]\right]}\right)$
$\displaystyle=$
$\displaystyle\ln\left(\frac{\mathbb{E}_{{z}_{i}^{(2)}\sim\hat{P}_{i,t_{2}}({x}_{i},\cdot)}\left\\{\mathbb{E}_{\boldsymbol{z}_{-i}^{(2)}\sim\hat{P}_{-i,t_{2}}(\boldsymbol{x}_{-i},\cdot)}\left[{\rm
Pr}(M(\boldsymbol{z}^{(2)})\in\mathcal{W}_{2})\cdot{\rm
Pr}[\mathcal{M}^{\prime}(X_{S_{n}-A_{n}})\in\mathcal{W}_{1}|X_{S_{n}-A_{n}}=\boldsymbol{z}^{(2)}]\right]\right\\}}{\mathbb{E}_{{z}_{i}^{(2)}\sim\hat{P}_{i,t_{2}}({x}^{\prime}_{i},\cdot)}\left\\{\mathbb{E}_{\boldsymbol{z}_{-i}^{(2)}\sim\hat{P}_{-i,t_{2}}(\boldsymbol{x}_{-i},\cdot)}\left[{\rm
Pr}(M(\boldsymbol{z}^{(2)})\in\mathcal{W}_{2})\cdot{\rm
Pr}[\mathcal{M}^{\prime}(X_{S_{n}-A_{n}})\in\mathcal{W}_{1}|X_{S_{n}-A_{n}}=\boldsymbol{z}^{(2)}]\right]\right\\}}\right)$
$\displaystyle=$
$\displaystyle\ln\left(\frac{\mathbb{E}_{{z}_{i}^{(2)}\sim\hat{P}_{i,t_{2}}({x}_{i},\cdot)}\left\\{\mathbb{E}_{\boldsymbol{z}_{-i}^{(2)}\sim\hat{P}_{-i,t_{2}}(\boldsymbol{x}_{-i},\cdot)}\left[h_{1}(\boldsymbol{z}^{(2)})\cdot
h_{2}(\boldsymbol{z}^{(2)})\right]\right\\}}{\mathbb{E}_{{z}_{i}^{(2)}\sim\hat{P}_{i,t_{2}}({x}^{\prime}_{i},\cdot)}\left\\{\mathbb{E}_{\boldsymbol{z}_{-i}^{(2)}\sim\hat{P}_{-i,t_{2}}(\boldsymbol{x}_{-i},\cdot)}\left[h_{1}(\boldsymbol{z}^{(2)})\cdot
h_{2}(\boldsymbol{z}^{(2)})\right]\right\\}}\right)$ $\displaystyle\leq$
$\displaystyle\ln\left(1+\Delta\left(t-S_{n}+A_{n}\right)\cdot\left(\exp(\epsilon_{C,n}+\epsilon(S_{n}-A_{n}))-1\right)\right),~{}\forall
t\in[S_{n},S_{n+1}),n\in\mathbb{N},$ (53)

where $t_{2}=t-S_{n}+A_{n}$, $h_{1}(X)={\rm Pr}(M(X)\in\mathcal{W}_{2})$ and
$h_{2}={\rm
Pr}[\mathcal{M}^{\prime}(X_{S_{n}-A_{n}})\in\mathcal{W}_{1}|X_{S_{n}-A_{n}}=\boldsymbol{z}^{(2)}]$.
Note that

$\displaystyle h_{1}(X)$
$\displaystyle\leq\exp(\epsilon_{C,n})h_{1}(X^{\prime}),$ (54a) $\displaystyle
h_{2}(X)$ $\displaystyle\leq\exp(\epsilon(S_{n}-A_{n}))h_{2}(X^{\prime})$
(54b)

for all $X,X^{\prime}\in\mathcal{X}$ that differ only in one entry.
Substituting (54) into the (17) yields the last inequality of (53). This
completes the proof.

###  A-E Proof of Proposition 4

Since $\ln(1+x)$ is monotonically increasing in $x$, we can rewrite (32) as

$\displaystyle\min\quad$
$\displaystyle\frac{c\cdot\rho^{A}\cdot(\exp(\epsilon_{C})-1)}{1-c^{2}\cdot\rho^{\bar{S}}\exp(\epsilon_{C})}$
(55a) $\displaystyle{\rm s.t.}~{}\quad$ $\displaystyle
c^{2}\rho^{\bar{S}}\exp(\epsilon_{C})<1,$ (55b) $\displaystyle
f(A+\bar{S},\epsilon_{C})\leq\bar{f},$ (55c) $\displaystyle{\rm var.}\quad$
$\displaystyle\epsilon_{C}\geq 0,A\geq 0,\bar{S}\geq 0,$ (55d)

We first drop the constraint in (55b) and formulate the corresponding
Lagrangian:

$\displaystyle\mathcal{L}(A,\bar{S},\epsilon_{C})=\frac{c\cdot\rho^{A}\cdot(\exp(\epsilon_{C})-1)}{1-c^{2}\cdot\rho^{\bar{S}}\exp(\epsilon_{C})}-\lambda(f(A+\bar{S},\epsilon_{C})-\bar{f}),$
(56)

where $\lambda$ is the dual variable corresponding to the constraint in (55c).
The Karush–Kuhn–Tucker conditions (necessary for all local optima) are [51]

$\displaystyle\frac{-c\cdot\rho^{A}\ln(\rho)(\exp(\epsilon_{C})-1)}{c^{2}\rho^{\bar{S}}\exp(\epsilon_{C})-1}-\lambda\frac{\partial
f(A+\bar{S},\epsilon_{C})}{\partial A}$ $\displaystyle=0,$ (57a)
$\displaystyle\frac{c^{3}\cdot\rho^{A+\bar{S}}\ln(\rho)(\exp(\epsilon_{C})-1)}{(c^{2}\rho^{\bar{S}}\exp(\epsilon_{C})-1)^{2}}-\lambda\frac{\partial
f(A+\bar{S},\epsilon_{C})}{\partial\bar{S}}$ $\displaystyle=0.$ (57b)

Combining (57) and the fact that $\frac{\partial
f(A+\bar{S},\epsilon_{C})}{\partial\bar{S}}=\frac{\partial
f(A+\bar{S},\epsilon_{C})}{\partial A}$, we can obtain (33). We note that i)
(33) is necessary even if the problem in (55) is not convex; ii) (33)
automatically satisfies (55b), which implies that the relaxation of (55b) does
not lose any feasibility.

###  A-F Preliminaries: Mixing, Ergodicity, and Markov Chains

In order to characterize how privacy guarantees change over time under the new
framework of age-dependent DP, we introduce several related concepts and
preliminary results from the literature in this subsection.

####  A-F1 Geometric Ergodicity

To understand under what conditions a Markov chain satisfies the geometric
ergodicity, we first introduce the following important result in analyzing the
transition probability matrix $P(\cdot,\cdot)$:

######  Lemma 4 (Bounds on Eigenvalues [44]).

Let $P(\cdot,\cdot)$ be the transition matrix of an irreducible Markov chain
$\\{X_{t}\\}_{t\in\mathbb{N}}$. Then the eigenvalues of $P$,
$\\{\lambda_{k}\\}$, satisfy:

$\displaystyle 1=\lambda_{0}>\lambda_{1}\geq...\geq\lambda_{m-1}\geq-1,$ (58)

where $m=|\mathcal{X}|$ denotes the total number of states.

The largest eigenvalue $\lambda_{0}$ being $1$ results from irreducibility. It
is known that the convergence rate largely depends on the value
$\lambda_{*}=\max(\lambda_{1},|\lambda_{m-1}|)$.

There are a few studies in the literature of applied probability on analysis
of the value of $\lambda_{*}$ (e.g., [44, 45]). As an example, Landau and
Odlyzko in [45] provided a bound for a random walk on a connected graph and
showed the following result:

######  Proposition 7 ([45]).

Let $\\{X_{t}\\}_{t\in\mathbb{N}}$ be a random walk on a connected graph, it
follows that

$\displaystyle\lambda_{*}\leq
1-\frac{1}{|\mathcal{X}|d_{*}(1+\gamma_{*})}<1-\frac{1}{|\mathcal{X}|^{3}},$
(59)

where $|\mathcal{X}|$ is the number of vertices in the graph, $d_{*}$ is the
maximum degree of the graph, and $\gamma_{*}$ is the diameter of the graph.

###  A-G Proof of Theorem 4

To prove Theorem 4, we will first prove that the monotonicity of
$\epsilon(S_{n})$ in $n$ (Lemma 5). We will then present the intermediate
result of the existence of an optimal solution that have identical
$(A_{n}^{*},\bar{S}_{n}^{*},\epsilon_{C,n}^{*})$ after $n\geq m$ in Lemma 6,
based on which we complete the whole proof.

Define

$\displaystyle
F(A_{n},\bar{S}_{n},\epsilon_{C,n},\epsilon)\triangleq\ln\left(1+\Delta\left(\bar{S}_{n}+A_{n}\right)\cdot\left(\exp(\epsilon_{C,n})[\Delta(A)\cdot(\epsilon-1)+1]-1\right)\right),$
(60)

for all $t\in[S_{n},S_{n+1}),n\in\mathbb{N}$. We have
$\epsilon_{n+1}=F(A_{n},\bar{S}_{n},\epsilon_{C,n},\epsilon_{n})$, which is
strictly increasing in $\epsilon$ and $\epsilon_{C,n}$. For any
$m\in\mathbb{N}$, if we fix ${A}_{n},\bar{S}_{n},\epsilon_{C,n}$ for all
$n\geq m$, it follows that ${\epsilon_{m}+1}$ strictly increases in
$\epsilon_{m}$.

Let the maximal objective value of (26) be $\epsilon^{*}$. Let
$m\in\mathbb{N}\cup\\{+\infty\\}$ be the first epoch that the peak age-
dependent privacy risk, i.e., $\epsilon(S_{m})=\epsilon^{*}$.

We first introduce the following lemma:

######  Lemma 5.

For any optimal solution
$\mathcal{Z}^{*}=(\\{A_{n}^{*}\\},\\{\bar{S}_{n}^{*}\\},\\{\epsilon_{C,n}^{*}\\})$,
the sequence $\\{\epsilon_{n}\\}_{n}$ is non-decreasing in $n$.

To prove Lemma 5, suppose that there exists an optimal solution
$\mathcal{Z}^{*}=(\\{A_{n}^{*}\\},\\{\bar{S}_{n}^{*}\\},\\{\epsilon_{C,n}^{*}\\})$
such that $\epsilon_{k+1}<\epsilon_{k}$ for some $k$. In this case, we replace
$(A^{*}_{n},\bar{S}^{*}_{n},\epsilon^{*}_{C,n})$ for all $n\geq k$ by
$(A^{*}_{k},\bar{S}^{*}_{k},\epsilon^{*}_{C,k})$, i.e., we construct the
following new solution
$\mathcal{Z}^{\prime}=(\\{A_{n}^{\prime}\\},\\{\bar{S}_{n}^{\prime}\\},\\{\epsilon_{C,n}^{\prime}\\})$
satisfying:

$\displaystyle(A^{\prime}_{n},\bar{S}^{\prime}_{n},\epsilon^{\prime}_{C,n})=\begin{cases}(A^{*}_{k},\bar{S}^{*}_{k},\epsilon^{*}_{C,k}),\quad{\rm
if}\quad n\geq k,\\\ (A^{*}_{n},\bar{S}^{*}_{n},\epsilon^{*}_{C,n}),\quad{\rm
otherwise}.\end{cases}$ (61)

For the new sequence $\\{\epsilon_{n}^{\prime}\\}$ generated by
$\mathcal{Z}^{\prime}$, it follows that

$\displaystyle
F(A^{*}_{k},\bar{S}^{*}_{k},\epsilon^{*}_{C,k},\epsilon_{n}^{\prime})<F(A^{*}_{k},\bar{S}^{*}_{k},\epsilon^{*}_{C,k},\epsilon_{n}),$
(62)

i.e., $\epsilon_{n+1}^{\prime}<\epsilon_{n+1}$. Similarly, we have

$\displaystyle\epsilon_{n+1}^{\prime}<\epsilon_{n}^{\prime},\forall n\geq k.$
(63)

Therefore, we have
$\epsilon^{*}>\epsilon_{k}>\epsilon_{k}^{\prime}>\epsilon_{n}$ for all
$n\in\mathbb{N}$, which is a contradiction to the fact that $\mathcal{Z}^{*}$
is optimal.

We have the new solution $\mathcal{Z}^{\prime}$ is also feasible (as
$f(A_{m}+\bar{S}_{m},\epsilon_{C,m})\leq\bar{f}$).

$\displaystyle
F(A_{k}^{*},\bar{S}_{k}^{*},\epsilon_{C,n}^{*})=\ln\left(1+\Delta\left(\bar{S}_{k}^{*}+A_{k}^{*}\right)\cdot\left(\exp(\epsilon_{C,n}^{*})[\Delta(A_{k}^{*})\cdot(\epsilon_{n}-1)+1]-1\right)\right),n\in\mathbb{N}.$
(64)

In addition, we must have

######  Lemma 6.

For any optimal solution
$\mathcal{Z}^{*}=(\\{A_{n}^{*}\\},\\{\bar{S}_{n}^{*}\\},\\{\epsilon_{C,n}^{*}\\})$,
the sequence $\\{\epsilon_{n}\\}_{n}$, let $\epsilon_{m}=\epsilon_{n}^{*}$ for
$m$, then there exists another new optimal solution such that
$A_{n}^{*}=A^{*}$, $S_{n}^{*}=S^{*}$, and
$\epsilon_{C,n}^{*}=\epsilon_{C}^{*}$ for all $n\geq m$.

For any optimal solution
$\mathcal{Z}^{*}=(\\{A_{n}^{*}\\},\\{\bar{S}_{n}^{*}\\},\\{\epsilon_{C,n}^{*}\\})$,
we construct a new solution such that

$\displaystyle(A^{\prime}_{n},\bar{S}^{\prime}_{n},\epsilon^{\prime}_{C,n})=\begin{cases}(A^{*}_{m},\bar{S}^{*}_{m},\epsilon^{*}_{C,m}),\quad{\rm
if}\quad n\geq m,\\\ (A^{*}_{n},\bar{S}^{*}_{n},\epsilon^{*}_{C,n}),\quad{\rm
otherwise}.\end{cases}$ (65)

It follows that

$\displaystyle
F(A^{*}_{m},\bar{S}^{*}_{m},\epsilon^{*}_{C,m},\epsilon_{m})=\epsilon_{m+1}=\epsilon^{*}.$
(66)

Now, we focus on the optimal solution $\boldsymbol{Z}^{*}$ such that
$A_{n}^{*}=A_{n+1}^{*}=A^{*}$, and
$\bar{S}_{n}^{*}=\bar{S}_{n+1}^{*}\bar{S}^{*}$,
$\epsilon_{C,n}^{*}=\epsilon_{C,n+1}^{*}=\epsilon_{C}^{*}$ for all $n\geq m$.
Now, we consider a new solution such that
$\mathcal{Z}^{\prime}=(\\{A_{n}^{\prime}\\},\\{\bar{S}_{n}^{\prime}\\},\\{\epsilon_{C,n}^{\prime}\\})$
such that $A_{n}^{\prime}=A^{*}$, $\bar{S}_{n}^{\prime}=\bar{S}^{*}$, and
$\epsilon_{C,n}^{\prime}=\epsilon_{C}^{*}$ for all all $n\in\mathbb{N}$.

Note that, since

$\displaystyle
F(A^{*},\bar{S}^{*},\epsilon_{C}^{*},\epsilon^{*})=\epsilon^{*},$ (67)

and $F(A^{*},\bar{S}^{*},\epsilon_{C}^{*},\epsilon)$ in strictly increasing in
$\epsilon$. We have that, for the sequence $\\{\epsilon_{n}\\}$ generated
according to
$\epsilon_{n+1}=F(A^{*},\bar{S}^{*},\epsilon_{C}^{*},\epsilon_{n})$ for all
$n\in\mathbb{N}$ with $\epsilon_{0}=0$, $\epsilon_{n}\leq\epsilon^{*}$ for all
$n\in\mathbb{N}$. Therefore, the new solution $\mathcal{Z}^{\prime}$ must be
optimal as well.

###  A-H Proof of Corollary 2

Let $(A,\bar{S},\epsilon_{C})$ be any feasible solution, we construct another
solution $(A^{\prime},\bar{S}^{\prime},\epsilon_{C}^{\prime})$ such that

$\displaystyle A^{\prime}>A,~{}~{}\bar{S}^{\prime}>$
$\displaystyle~{}S,\epsilon_{C}^{\prime}>\epsilon_{C},$ (68)
$\displaystyle\rho^{A}(\exp(\epsilon_{C})-1)=$
$\displaystyle~{}\rho^{A^{\prime}}(\exp(\epsilon_{C}^{\prime})-1),$ (69)
$\displaystyle\rho^{\bar{S}}\exp(\epsilon_{C})=$
$\displaystyle~{}\rho^{\bar{S}^{\prime}}\exp(\epsilon_{C}^{\prime}).$ (70)

From (32a), we can show that
$(A^{\prime},\bar{S}^{\prime},\epsilon_{C}^{\prime})$ leads to the same
objective value as $(A,\bar{S},\epsilon_{C})$ does.

On the other hand, we have that

$\displaystyle A^{\prime}$
$\displaystyle=A+\frac{\ln(\exp(\epsilon_{C}^{\prime})-1)}{\ln(\rho^{-1})}-\frac{\ln(\exp(\epsilon_{C})-1)}{\ln(\rho^{-1})},$
(71) $\displaystyle\bar{S}^{\prime}$
$\displaystyle=\bar{S}+\frac{\epsilon_{C}^{\prime}}{\ln(\rho^{-1})}-\frac{\epsilon_{C}}{\ln(\rho^{-1})}.$
(72)

Therefore, the new value of the peak age penalty is given by

$\displaystyle
f\left(A^{\prime}+\bar{S}^{\prime},\epsilon_{C}^{\prime}\right)=f\left(\frac{\ln(\exp(\epsilon_{C}^{\prime})-1)}{\ln(\rho^{-1})}+\frac{\epsilon_{C}^{\prime}}{\ln(\rho^{-1})}+a,\epsilon_{C}^{\prime}\right),$
(73)

where
$a=A-\frac{\ln(\exp(\epsilon_{C})-1)}{\ln(\rho^{-1})}+\bar{S}-\frac{\epsilon_{C}}{\ln(\rho^{-1})}$.

The assumption that (73) is decreasing in $\epsilon^{\prime}_{C}$ means that
the new solution will satisfy
$f(A^{\prime}+\bar{S}^{\prime},\epsilon_{C}^{\prime})<f(A+\bar{S},\epsilon_{C})$
while achieving the same peak privacy guarantees.

###  A-I Autoregressive Model

We further consider a continuous-state autoregressive (AR) models, expressed
as

$\displaystyle
x_{i,t+1}=\rho_{1}x_{i,t}+\rho_{2}x_{i,t-1}+\rho_{3}x_{i,t-2}...+\epsilon_{i,t},~{}~{}\forall
i\in\mathcal{I},t\in\mathbb{N}_{+},$ (74)

where $\epsilon_{i,t}$ follows an i.i.d. normal distribution
$\mathcal{N}(0,\sigma^{2})$.

We start with the following time reversibility result:

######  Lemma 7 ([46]).

When $\epsilon_{i,t}$ follows i.i.d. normal distributions, the process in (74)
is time reversible.

In the following, we focus on an AR(1) model for trackability, i.e., among all
$\\{\rho_{t}\\}$ only the first coefficient $\rho_{1}$ takes a non-zero value.
Therefore, we drop the index $1$ in $\rho_{1}$ in the following.

When $\epsilon_{i,t}$ has mean zero and variance $\sigma^{2}$, it follows that

$\displaystyle\mathbb{E}[x_{i,t+n}|x_{i,n}]=\rho^{t}x_{i,n},\forall
t,n\in\mathbb{N}_{+},$ (75)

and

$\displaystyle\text{Var}[x_{i,t}|x_{i,0}]=\frac{(1-\rho^{2t})\sigma^{2}}{1-\rho^{2}},\forall
i\in\mathcal{I},\forall n\in\mathbb{N}_{+}.$ (76)

######  Lemma 8.

When $\epsilon$ follows $\mathcal{N}(0,\sigma^{2})$ for all $i\in\mathcal{I}$
and $t\in\mathbb{N}$, the probability distribution of $X_{i,t}$ conditional on
$X_{i,0}$ is expressed as

$\displaystyle
x_{i,t}|x_{i,0}\sim\mathcal{N}\left(\rho^{t}x_{i,0},\frac{(1-\rho^{2t})\sigma^{2}}{1-\rho^{2}}\right),~{}~{}\forall
i\in\mathcal{I},t\in\mathbb{N}_{+}.$ (77)

In addition, we note that the total variation distance is closely related to
another well-known metric called the Kullback–Leibler divergence:

$\displaystyle{\displaystyle
D_{\text{KL}}(\mu\parallel\pi)\triangleq\sum_{x\in{\mathcal{X}}}\pi(x)\log\left({\frac{\mu(x)}{\pi(x)}}\right)},$
(78)

and its relation to the total variation distance can be expressed in the
following:

######  Lemma 9.

The total variation distance is related to the Kullback–Leibler divergence by
the Pinsker’s inequality:

$\displaystyle\delta(\pi,\mu)\leq{\sqrt{{\frac{1}{2}}D_{\mathrm{KL}}(\pi\parallel\mu)}},\forall\pi,\mu.$
(79)

It follows that the Kullback-Leibler divergence is

$\displaystyle D_{\mathrm{KL}}(P_{t}(x_{i,0},\cdot)\parallel
P_{t}(x_{i,0}^{\prime},\cdot))={1\over
2}\left\\{{\frac{(\mu_{1}-\mu_{0})^{2}}{\sigma^{2}}}\right\\}$
$\displaystyle=\frac{(1-\rho^{2})\rho^{2t}(x_{i,t}-x^{\prime}_{i,t})^{2}}{2\sigma^{2}(1-\rho^{2n})}$
$\displaystyle\leq\frac{\rho^{2t}(x_{i,0}-x^{\prime}_{i,0})^{2}}{2\sigma^{2}}=\mathcal{O}(\rho^{2t}).$
(80)

Based on the relation between the Kullback-Leibler divergence and the total
variation distance in Lemma 9, it follows that

$\displaystyle\Delta(t)=\delta(P_{t}(x_{i,0},\cdot),P_{t}(x_{i,0}^{\prime},\cdot))\leq{\sqrt{{\frac{1}{2}}D_{\mathrm{KL}}(P_{t}(x_{i,0},\cdot)\parallel
P_{t}(x_{i,0}^{\prime},\cdot))}}\leq\frac{\rho^{t}|x_{i,0}-x^{\prime}_{i,0}|}{2\sigma}.$
(81)

The convergence rate of $\Delta(t)$ again is $\mathcal{O}(\rho^{t})$.

From Theorem 2, we conclude that any $\epsilon_{C}$-DP mechanism ${M}$ is also
$(\epsilon(t),t)$-age-dependent DP, satisfying

$\displaystyle\epsilon(t)=\ln\left(1+\frac{\rho^{t}|x_{i,0}-x^{\prime}_{i,0}|}{2\sigma}\cdot(\exp(\epsilon_{C})-1)\right).$
(82)

The single-query mechanism ${M}^{*}$ that estimates the average value of
$x_{i,t}$ over all users, i.e.,

$\displaystyle{M}(X_{0})=\left[\frac{\sum_{i}x_{i,0}}{I}\right]+n,$ (83)

where $n$ is a Laplace $(1/\epsilon_{C})$ random variable. Similarly, we use
the mean-squared estimation error as the accuracy loss metric, given by

$\displaystyle f_{\rm MMSE}(t,\epsilon_{C})$
$\displaystyle=\mathbb{E}\left[\left(M(X_{0})-\frac{1}{I}\sum_{i}x_{i,t}\right)^{2}\right],$
(84)
$\displaystyle=\frac{(1-\rho^{2t})\sigma^{2}}{I(1-\rho^{2})}+\frac{1}{\epsilon_{C}^{2}I^{2}}.$
(85)

Figure 8: Numerical results for the autoregressive model.

We present numerical results in Figure 8 which are similar to those in Figure
4. In Figure 8(a), we show that the accuracy loss increases in $t$, and for a
given $\epsilon_{C}$, it converges to an upper bound as $t\rightarrow\infty$.
In Figure 8(b), we compare our proposed mechanisms against a classical DP
benchmark that only injects Laplace noise. To achieve an arbitrary small
privacy risk, the accuracy loss incurred by the benchmark grows unbounded.
Compared to the benchmark, combining both aging and noise injection does not
incur meaningful accuracy loss, which is upper bounded as the privacy risk
approaches $0$.