Differential Privacy for Markov Chain State Trajectories

Differential Privacy for Markov Chain State Trajectories Alexander Benvenuti

abenvenuti3@gatech.edu

School of Electrical and Computer Engineering Georgia Institute of Technology

Matthew Hale

mhale30@gatech.edu

School of Electrical and Computer Engineering Georgia Institute of Technology

arXiv:2608.08341v1 [cs.CR] 8 Aug 2026

Abstract Data-driven systems may require state trajectories of Markov chains to function because these trajectories contain information that is useful to the system, e.g., a product’s credit risk, a user’s physical location, or a user’s internet browsing behavior. However, sharing such state trajectories can reveal sensitive information about users, which presents a privacy threat. Therefore, we develop a new framework for privatizing the state trajectories in a Markov chain using differential privacy. Our framework privatizes state trajectories online, in the sense that a private state trajectory is generated at the same time as the sensitive one it approximates. We treat Markov chains as weighted directed graphs whose edge weights are the negative logarithms of the transition probabilities. Then, each state in a private state trajectory is chosen by minimizing its distance to the corresponding state in the sensitive state trajectory, where the notion of distance is equal to the total edge weight along a shortest path. We prove that with high probability the private state trajectory remains close to the sensitive one, which maintains high utility for downstream uses of private data. Additionally, we prove that private state trajectories are consistently in the typical set of state trajectories generated by the underlying Markov chain, which means that private state trajectories have similar statistical properties to actual state trajectories produced by the underlying Markov chain. Numerical simulations show that under 3-differential privacy, the mechanism we introduce exhibits up to an 80% decrease in entropy compared to the state of the art, which illustrates that private state trajectories generated by our framework more closely resemble their corresponding sensitive state trajectory while maintaining the same level of privacy.

1

Introduction

Markov chains are used to model a variety of behaviors including credit migration of financial products (Kalkbrener & Packham, 2026; Hurd & Kuznetsov, 2007), city traffic patterns (Gong et al., 2011), and internet traffic patterns (Dong et al., 2022). State trajectories generated by such Markov chains may be used to infer the financial health over time of a product (Amed et al., 2026), individuals’ daily commutes (Gong et al., 2011), or their internet browsing behavior (Rendle et al., 2010), all of which are sensitive. Even when anonymizing data, users’ identities may be easily reconstructed, even from short state trajectories (De Montjoye et al., 2013). Without privacy protections, inferences from these trajectories can threaten users’ privacy. Therefore, in this paper we develop a framework to privatize state trajectories generated by Markov chains. This framework generates a private state trajectory online, i.e., a private state trajectory is generated simultaneously with the sensitive state trajectory it approximates. Our framework does so in a way that respects the Markov chain dynamics, in the sense that all state-to-state transitions in a private state trajectory are feasible under the transition probabilities of the given Markov chain. We develop this framework using differential privacy. Differential privacy is a statistical notion of privacy that was originally designed to preserve the privacy of sensitive databases when queried (Dwork et al., 2006). 1

Differential privacy has been widely used because of its strong guarantees, namely that it is (i) immune to post-processing, in the sense that post-hoc computations on differentially private data remain differentially private and (ii) robust to side information, in that learning additional information about the underlying sensitive data does not substantially weaken differential privacy. These properties have led to the adoption of differential privacy in optimization (Hsu et al., 2014; Wang et al., 2016; Munoz et al., 2021; Benvenuti et al., 2026a), planning (Gohari et al., 2020; Chen et al., 2023a), and machine learning (Ponomareva et al., 2023; Jayaraman & Evans, 2019; Blanco-Justicia et al., 2022), among other disciplines. Prior work on privatizing Markov chain state trajectories treats Markov chains as non-deterministic finitestate automata (Chen et al., 2023b). The approach used in that work is agnostic to the transition probabilities in the Markov chain, and it often selects private states by performing a uniform random walk over the Markov chain’s state space. This approach can be undesirable because such random walks often do not yield “typical” trajectories generated by the Markov chain, which harms utility. In contrast, we treat Markov chains as weighted, directed graphs, where the edge weights are the negative logarithms of the transition probabilities. Private trajectories are genereted by randomly selecting one state at a time using an approach similar to the permute-and-flip mechanism for differential privacy (McKenna & Sheldon, 2020). We calibrate the probability of selecting a candidate next private state by using the shortest-path distance between (i) each candidate next private state and (ii) the corresponding sensitive, non-private state in the trajectory being privatized. We show that with high probability, the resulting private state trajectories remain close (in a shortest-path distance sense) to the sensitive state trajectories they approximate. Additionally, we show that with high probability a privatized state trajectory is in the “typical set” of state trajectories generated by the Markov chain. The typical set is the set of state trajectories most likely to be generated by the Markov chain, and the generation of private state trajectories in this set ensures that private state trajectories preserve their utility for downstream analysis. To summarize, we make the following contributions: • We introduce a new notion of privacy for Markov chain state trajectories and develop a differential privacy mechanism with respect to this new definition (Definition 4, Mechanism 1, Theorem 1). • We give a concentration bound on the error induced by Mechanism 1 (Theorem 2). • We bound the expected empirical entropy of the private state trajectories generated by Mechanism 1 and give concentration bounds on the empirical entropy (Theorems 3 and 4). • We empirically validate Mechanism 1 on three real datasets: credit migration, city traffic, and internet traffic, and we show it produces private trajectories with 80% less entropy than the prior state-of-the-art mechanism. We also empirically show that Mechanism 1 reduces the probability of large errors at any time step by up to 4 orders of magnitude (Section 5). 1.1

Related work

Our mechanism uses the shortest-path distances on a graph as a measure of utility in private state trajectory approximations. This utility is a notion that has frequently appeared in the geo-indistinguishability literature (Zhu et al., 2024; Min et al., 2025; Wang et al., 2025). We differ from these works in three major ways. First, those works are concerned with preserving the privacy of individual states in a trajectory on a graph, while we consider privacy at the trajectory level. Second, the state trajectories we consider are generated via Markov chains, while those works consider deterministic walks on graphs. Third, these works select the next state in a private trajectory using the exponential mechanism, while we propose a new approach based on the permute-and-flip mechanism (McKenna & Sheldon, 2020). The authors in Chen et al. (2023b); Benvenuti et al. (2026c); Bertazzi et al. (2025); Chen et al. (2026) have previously considered privacy for the trajectories generated by Markov chains. We differ from Bertazzi et al. (2025) in two ways. First, they consider the execution of a Markov chain as a randomization algorithm itself, whereas we design a framework to privatize the state trajectories generated by a given Markov chain. Second, we consider the state trajectories themselves to be the sensitive data, not the underlying data used 2

to generate the Markov chain. We differ from the work in Benvenuti et al. (2026c) because we generate private state trajectories in an online fashion, which privatizes state trajectories as new transitions occur in the Markov chain, while that work privatizes state trajectories in an offline manner, i.e., the whole trajectory is privatized at once after runtime. Similarly, Guner & Gursoy (2023) privatize state trajectories used to empirically determine transition probabilities in a Markov chain, while we privatize state trajectories generated by an existing Markov chain. We differ from Chen et al. (2026) in two ways. First, their mechanism requires a context-specific distance function for a given problem, while we use the Markov chain transition probabilities to form our distance function, which may be used in any Markov chain setting. Second, they require approximating their mechanism by a deep neural network to implement their framework, while we may directly implement ours without a neural network. The authors in Fallin et al. (2023); Benvenuti et al. (2026b) also consider privacy for Markov chains. However, they privatize transition probabilities, or the data used to compute them, rather than state trajectories generated by the Markov chain. Our work is most similar to Chen et al. (2023b), which developed a mechanism for privatizing general symbolic system state trajectories online and applied it to Markov chains. We differ by designing a mechanism specifically for Markov chains. Our approach uses the transition probabilities to generate private trajectories that have more structural similarity to the underlying sensitive trajectories than the mechanism in Chen et al. (2023b). We illustrate this difference empirically in Section 5. 1.2

Notation

We use N to denote the non-negative integers, R to denote the real numbers, and R+ to denote the nonnegative real numbers. For n ∈ N we use [n] = {0, 1, . . . , n}, and we use 1[X] as the indicator function for the event X. We use Θ(A) to denote the set of probability distributions over a non-empty, finite set A. We use Ber(p) to denote a Bernoulli distribution with parameter p, and Sn to denote the set of all n×n stochastic matrices, i.e., the set of all n × n matrices with non-negative entries whose rows sum to 1. We use erf(x) to Rx 2 denote the error function, namely erf(x) = 0 e−u du. We use log to denote the natural logarithm, and we adopt the convention that − log(0) = ∞. For a function f the output of the operator arg minx f (x) is the set of all points x that minimize f . The arg max operator is set-valued in the analogous way.

2

Background and Problem Statements

This section reviews Markov chains and differential privacy, then presents problem statements. 2.1

Markov Chains

A stochastic process (Yt )t∈N on a state space S is a Markov chain if it satisfies the Markov property, namely P (Yt+1 = yt+1 | Y0 = y0 , Y1 = y1 , . . . , Yt = yt ) = P (Yt+1 = yt+1 | Yt = yt ) , where yt ∈ S for all t ∈ N. Throughout this work, we denote Markov chains by tuples of the form M = (S, P, p0 ), where S is the non-empty, finite set of states of the Markov chain, P ∈ S|S| is the transition matrix, and p0 ∈ Θ(S) is the initial state distribution. We assume that the tuple M = (S, P, p0 ) is publicly available. For example, in a city traffic scenario, this assumption implies that the roads, the probability of transitioning from one road to another, and the probability of a user beginning on some road are all publicly available information. Given that city maps are freely available and aggregate traffic data is frequently shared by cities, the assumption that M = (S, P, p0 ) is publicly available is easily satisfied in that setting. Remark 1. Throughout this work, we denote a state in a sequence indexed in time using subscripts, e.g., with st . To refer to individual states in the state space S we use i, j ∈ S. The probability of transitioning from state i ∈ S to state j ∈ S is Pij = P (j | i). For n ∈ N, we denote the set of all state trajectories of length n + 1 by S n+1 . Throughout this work, we use N (s) to denote the neighborhood set of a state s, i.e., N (s) = {y ∈ S : P (y | s) > 0}. We consider irreducible, time-homogeneous Markov chains. A Markov chain is irreducible if it is possible to reach state j from state i in finitely many steps for all i, j ∈ S, and a Markov chain is time-homogeneous if P is not a function of time. 3

Assumption 1. The Markov chain M = (S, P, p0 ) is ergodic. While the mechanism developed in this work only requires Markov chains to be irreducible, we require Markov chains that are ergodic for our analysis of that mechanism, and ergodic Markov chains are defined as follows. Let p(t) ∈ Θ(S) be the probability mass function (PMF) of the state distribution of the Markov chain at time t, i.e., for all i ∈ [|S|] \ {0} the value of pi (t) is the probability of the Markov chain being in state i at time t. In an ergodic Markov chain M = (S, P, p0 ), the PMF p(t) converges to a stationary distribution µ = limt→∞ p(t), where µ satisfies µT = µT P . 2.2

Differential Privacy

The goal of differential privacy is to make “similar” trajectories appear approximately indistinguishable. The notion of “similar” is defined by an adjacency relation. Definition 1 (Adjacency). Fix a Markov chain M = (S, P, p0 ) satisfying Assumption 1. Let d : S × S → R be a metric on the state space of M . Fix a number of state-to-state transitions n ∈ N and an adjacency parameter b > 0. Two trajectories w, v ∈ S n+1 are said to be (d, b)-adjacent if d(w, v) ≤ b. We use Adjn,b,d (w, v) = 1 to denote that w, v are (d, b)-adjacent, and we call (d, b) an “adjacency pair”. ▲ We leave the choice of d in Definition 1 open for now, and we sometimes call w and v “adjacent” if d and b are clear from context. In Appendix B we state the adjacency relation used in the prior state of the art in Chen et al. (2023b), and in Section 3 we introduce a new adjacency relation for state trajectories generated by Markov chains. To show why a new adjacency relation is needed, in Appendix C we develop a mechanism similar to the one developed in Section 3 but with the adjacency relation from Chen et al. (2023b), and Appendix C shows that it leads to poor accuracy, which motivates the use of a new adjacency relation. Differential privacy is enforced by a randomized mapping called a “mechanism”, which we denote by M. Definition 2 (Differential Privacy; Dwork et al. (2014)). Fix a probability space (Ω, F, P), an adjacency pair (d, b), a number of state-to-state transitions n ∈ N, and a privacy parameter ϵ > 0. A mechanism M : S n+1 × Ω → S n+1 is ϵ-differentially private if, for all w, v that are (d, b)-adjacent in the sense of Definition 1 and all L ⊆ S n+1 , M satisfies P (M(w) ∈ L) ≤ eϵ P (M(v) ∈ L) . ▲ Differential privacy for state trajectories is not explicitly defined in (Dwork et al., 2014). However, Definition 2 follows immediately from the definition of differential privacy stated in (Dwork et al., 2014). If a privacy mechanism M satisfies Definition 2, then all the guarantees of differential privacy hold for M, including immunity to post-processing and robustness to side information. See Dwork et al. (2014) for more details on the guarantees provided by differential privacy. The parameter ϵ quantifies the strength of privacy, and a smaller value of ϵ implies stronger privacy. Typical values of ϵ are ϵ ∈ [0.1, 10] (Hsu et al., 2014). 2.3

Problem Statements

In this work, we solve the following problems: Problem 1. Fix a Markov chain M = (S, P, p0 ). Develop a mechanism that generates ϵ-differentially private approximations for the state trajectories generated by M . For trajectories w = s0 s1 . . . sn , the solution to Problem 1 formulates a privacy mechanism that approximates each state st with a randomized version s′t such that the entire state trajectory w is kept private. The challenges in doing so are two-fold: (i) because the mechanism operates online it only has access to the history of the trajectory up to time t, and (ii) it must produce a trajectory that is feasible with respect to the transition probabilities of the underlying Markov chain. Problem 1 is solved in Section 3.1. Problem 2. Bound the probability that private state trajectories contain large deviations from the sensitive state trajectories they approximate. Problem 2 analytically quantifies the accuracy of the mechanism developed to solve Problem 1, and we solve Problem 2 in Section 3.2. 4

Problem 3. Bound the probability that the proposed mechanism produces a private trajectory that is in the η-typical set of the Markov chain that generated the underlying sensitive trajectory. Problem 3 quantifies how realistic a private state trajectory is for the underlying Markov chain. State trajectories that do not appear in the typical set may easily be identified as trajectories that were not produced by the Markov chain because they may contain many unlikely transitions. Thus, even if a private state trajectory is not an accurate approximation of the sensitive one, if the private trajectory is in the typical set for a Markov chain, then it will still likely appear as a “typical” trajectory, which preserves its usefulness for downstream analysis. Problem 3 is solved in Section 4. Problem 4. Empirically compare the performance of the proposed mechanism to the state of the art using real datasets. Section 5 presents the solution to Problem 4 using three examples: credit migration, city traffic, and internet traffic, while comparing to the most similar work to ours, namely Chen et al. (2023b).

3

Structure-Aware Mechanism Design

In this section, we solve Problems 1 and 2. We aim to use a Markov chain’s dynamics so that when an incorrect transition is taken, the private state trajectory on average eventually returns to a neighborhood near the sensitive state trajectory it approximates. This property yields private state trajectories with similar structure to sensitive state trajectories, which preserves utility for downstream usage of private data. 3.1

Proposed Mechanism

To design a mechanism that uses a Markov chain’s topology, we define the graph induced by a Markov chain. Definition 3 (Markov Chain Induced Graph). A Markov chain M = (S, P, p0 ) induces a weighted directed graph G = (S, E, W ), where E = {(i, j) | Pij > 0} is the edge set, and W = {Wij }i,j∈S is a set of edge weights, where Wij = − log(Pij ). ▲ Many choices of edge weights exist for Definition 3, such as the diffusion distance (Coifman & Lafon, 2006), hitting times (Boyd et al., 2021), and the negative log-probabilities of the transitions, i.e., Wij = − log(Pij ) (Rabiner, 2002). The negative log-probabilities is often chosen when computing paths in a graph, which we do here. Negative log-probabilities are chosen because the probabilities themselves do not induce a metric for measuring distances on a graph, while the use of the negative log-probabilities gives a quasi-metric for measuring distances on a directed graph. See Appendix A for details on the properties of quasi-metrics. Let V(i, j) be the set of all trajectories of any length between states i ∈ S and j ∈ S. Then we define the shortest-path distance G : S × S → R as G(i, j) = min

v∈V(i,j)

|v| X

Wvk−1 ,vk ,

(1)

k=1

where |v| denotes the length of the word v. Proposition 1. Fix a Markov chain M = (S, P, p0 ) satisfying Assumption 1, and let w = s0 s1 · · · sn be a length n+1 state trajectory generated by M with s0 = u and sn = q. Using the edge weights Wij = − log(Pij ) for i, j ∈ S, then the state trajectory w∗ = s0 s∗1 · · · s∗n−1 sn that minimizes the total graph distance from u to q, namely G(u, q), is the most likely state trajectory in the Markov chain from u to q. ♢ Proposition 1 says that on the graph G in Definition 3, the shortest path between nodes i and j in the graph sense corresponds to the most likely path between states i and j in the Markov chain sense. While Proposition 1 is well-known in the literature, e.g., (Rabiner, 2002), the authors are unaware of a proof of it in the literature, and thus we provide one in Appendix E, which also has proofs of all new results. To develop a mechanism that does not exhibit any random walking behavior when generating private outputs, we weigh all possible transitions from a private state s′t−1 to a candidate private state s′t by the shortest 5

path distance between s′t and the true state st . The shortest path distance from s′t to st is G(s′t , st ), where G is from (1). All of the shortest-path distances in G can be computed simultaneously via the Floyd-Warshall algorithm (Floyd, 1962). We then use the shortest-path distances to define adjacency for state trajectories. Definition 4 (Trajectory Adjacency). Fix a Markov chain M = (S, P, p0 ) satisfying Assumption 1 and an adjacency parameter ρ > 0. Let G = (S, E, W ) be defined as in Definition 3. Two state trajectories w = s0 · · · sn ∈ S n+1 and v = s̃0 · · · s̃n ∈ S n+1 are adjacent if n X

Gsym (st , s̃t ) ≤ ρ,

t=0

where Gsym (x, y) = max{G(x, y), G(y, x)}, and G is from (1).

▲

Using the notation of Definition 1, we write Adjn,ρ,Gsym (w, v) = 1 if two trajectories are adjacent in the sense of Definition 4, and we write Adjn,ρ,Gsym (w, v) = 0 otherwise. Definition 4 is in line with the notion of adjacency for numerical trajectories in ℓp -spaces (Le Ny & Pappas, 2013), where p is typically taken to be 2. However, Definition 4 is analogous to the ℓ1 -norm because the state space is on a graph, and thus there is no Euclidean distance between states. Definition 4 may also be viewed from an information-theoretic perspective: two state trajectories w, v ∈ S n+1 are adjacent if the maximum difference in their Shannon information content is bounded above by ρ nats. The adjacency parameter ρ may then be chosen based on how unlikely one state trajectory can be relative to another while still being considered “similar”. For example, using ρ = − log(0.1) implies that differences between trajectories that occur with probability 0.1 are protected by differential privacy. Unlike the adjacency relation in Chen et al. (2023b), where adjacent trajectories may only differ in a single entry, our notion of adjacency allows for trajectories to differ in multiple ways: (i) they may differ in many entries such that the disagreeing state-to-state transitions in both trajectories occur with high probability, or (ii) they may differ in only a few entries such that the disagreeing state-to-state transitions in both trajectories occur with low probability. To enforce differential privacy, we will create a mechanism that is similar in spirit to the permute-andflip mechanism (McKenna & Sheldon, 2020). The permute-and-flip mechanism assigns probabilities to all possible outputs based on a utility score, which encodes how well a private state trajectory w′ approximates a sensitive state trajectory w. Throughout this paper, for two state trajectories w = s0 s1 · · · sn ∈ S n+1 and w′ = s′0 s′1 · · · s′n ∈ S n+1 , we use G from (1) to define the utility function X u(w, w′ ) = − G(s′t , st ), (2) t∈[n]

which encodes the fact that w′ is a better approximation for a sensitive state trajectory w if the distance from w′ to w is small. Unlike the permute-and-flip mechanism, however, we cannot select entire private state trajectories based on this utility because we are privatizing sensitive trajectories online. Instead, the Markov property allows us to select each private state in a similar fashion to the permute-and-flip mechanism at each time step while guaranteeing privacy for the entire trajectory. Remark 2. We refer to mechanisms that measure similarity using the transition probabilities as structureaware and mechanisms that do not as structure agnostic. The utility function u in (2) admits a direct information-theoretic interpretation. Because the graph edge weights are defined as negative log-probabilities, the shortest-path distance G(s′t , st ) represents the minimum Shannon information content required to specify the true state st given the private state s′t . To calibrate our mechanism, we require the sensitivity of u in (2), which encodes the maximum amount that the utility function can change on adjacent inputs. Lemma 1 (Sensitivity). Fix a Markov chain M = (S, P, p0 ) satisfying Assumption 1 and an adjacency parameter ρ > 0. Let G = (S, E, W ) be as defined in Definition 3. Let w = s0 · · · sn ∈ S n+1 and v = s̃0 · · · s̃n ∈ S n+1 be two adjacent state trajectories in the sense of Definition 4. Let u be from (2). Then ∆u = max n+1 y∈S

max

w,v∈S n+1 Adjn,ρ,Gsym (w,v)=1

6

|u(w, y) − u(v, y)| ≤ ρ.

♦

Algorithm 1 Private Markov Chain State Trajectory Generation Inputs: (i) Neighborhood set of s′t , N (s′t ), (ii) the set of all shortest-path distances {G(i, j) | i, j ∈ S}, (iii) next sensitive state st+1 , (iv) adjacency parameter ρ, and (v) privacy parameter ϵ Outputs: Next private state s′t+1 1: if t = 0 then 2: return s′0 ∼ p0 3: end if 4: R ← R(N (s′t )) 5: i ← 1 6: for ri ∈ R do 7: s′t+1 ← ri   8:

ps′t+1 ← exp

ϵ ′ ′ 2ρ (miny∈N (st ) G(y, st+1 ) − G(st+1 , st+1 ))

if Ber(ps′t+1 ) then 10: return s′t+1 11: end if 12: i←i+1 13: end for 9:

We use Algorithm 1 to implement the proposed mechanism. In line 6 we use R(N (s′t )) to denote a uniformly randomly selected permutation of the elements of the set N (s′t ), and in line 8 we use ri for i ∈ {1, 2, . . . , |N (s′t )|} to denote the ith element in the resulting permutation. At time step t = 0, the first state of the private trajectory, namely s′0 , is randomly drawn from the initial distribution p0 of the Markov chain M . For times t > 0, Algorithm 1 proceeds as follows. We randomly permute the elements of N (s′t−1 ), which is the set of candidate next states that are feasible from the previous private state s′t−1 . A biased coin is flipped to determine if a candidate next state is selected to the be the private output state s′t at time t. The coin’s bias is computed using the utility of the candidate output state. In Algorithm 1, we define miny∈N (s′t ) G(y, st+1 ) as the shortest distance from any state in N (s′t ) to st+1 . We see that miny∈N (s′t ) G(y, st+1 ) − G(s′t+1 , st+1 ) = 0 when s′t+1 ∈ arg miny∈N (s′t ) G(y, st+1 ), and ps′t+1 = 1 for all such states. Therefore, Algorithm 1 is guaranteed to terminate for all t ∈ [n] because the for loop in lines 8-15 is guaranteed to terminate for all t ∈ [n]. We now formally state the proposed mechanism. Mechanism 1 (Solution to Problem 1). Fix a Markov chain M = (S, P, p0 ) satisfying Assumption 1, an adjacency parameter ρ > 0, and a privacy parameter ϵ ≥ 0. At each time t, given the current state of the △ sensitive state trajectory, the mechanism M1 selects the output state s′t according to Algorithm 1. Prior to runtime, the Floyd-Warshall algorithm (Floyd, 1962) can be used to compute the shortest-path distances between all pairs of states, which results in a time complexity of O(|S|3 ) for privatizing an entire
trajectory using Algorithm 1. However, the time complexity at time step t is O |N (s′t−1 )| , since the shortestpath distances may all be acquired at runtime via table-lookup after using the Floyd-Warshall algorithm once before runtime. The O(|S|3 ) complexity is the same as Chen et al. (2023b), and thus any improvement in performance over their mechanism is gained without any increase in computational complexity. Now we formally state the privacy guarantee of Mechanism 1. Theorem 1. Fix a Markov chain M = (S, P, p0 ) satisfying Assumption 1 and a sensitive state trajectory w = s0 , . . . , sn . Fix an adjacency parameter ρ > 0 and a privacy parameter ϵ ≥ 0. Mechanism 1 provides ϵdifferential privacy to w with respect to the adjacency relation in Definition 4. Theorem 1 says that our mechanism privatizes trajectories by generating a random state at each time step. 3.2

Drift Analysis

The goals of Mechanism 1 are to guarantee that (i) the private state trajectory remains close to the sensitive one in the graph G if they start together, i.e., if s0 = s′0 , and (ii) the private state trajectory will return to a neighborhood around the sensitive state trajectory if they drift apart at some point. Mathematically, this 7

latter property may be stated in terms of the Foster-Lypaunov condition (Meyn & Tweedie, 1992), namely   Est+1 ,s′t+1 G(s′t+1 , st+1 ) − G(s′t , st ) | (st , s′t ) < 0. (3) We say that the set of joint states (st , s′t ) ∈ S × S that satisfy (3) has “negative drift”. The stochastic process of joint state pairs (st , s′t ) is a hidden Markov model (HMM), where the hidden state is the true state st and the observation is the output state s′t . Then, the process of joint state pairs (st , s′t ) is the Markov chain MZ = (Z, PϵZ , z0 ),

(4)

2

where Z = S × S is the joint state space, PϵZ ∈ S|S| is the joint transition probability matrix, and z0 ∈ Θ(Z) is the initial distribution over all initial joint states. Thus, to analyze privacy for length n + 1 trajectories, we may analyze the drift properties of the joint state trajectory (Zt )t∈[n] , where Zt = (st , s′t ). Next, we derive conditions under which a joint state (st , s′t ) ∈ Z has negative drift when s′t is selected using Mechanism 1. To do so, we define the following quantities. Let V (Zt ) = G(s′t , st )

(5)

be the shortest-path distance from s′t to st , which we refer to as the “Foster-Lyapunov function”, and let Zattract (ϵ) = {Zt ∈ Z : E [V (Zt+1 ) − V (Zt ) | Zt ] < 0}

(6)

be the set of states with negative drift for t ≥ 1, which we refer to as the “attractive set”. The dependence of Zattract on ϵ follows from the fact that the transition probabilities namely PϵZ depend on ϵ. ′ Let s′,∗ t ∈ arg minj∈N (s′t ) G(j, st+1 ) be a next state along a (potentially non-unique) shortest path from st to st+1 . Define ( arg minj∈N (s′t )\{s′,∗ G(j, st+1 ) if N (s′t ) \ {s′,∗ ′,† t } ̸= ∅ t } St = . (7) ′,∗ ′,∗ ′ {st } if N (st ) \ {st } = ∅

This set equals the set of next states along a (potentially non-unique) second-shortest path from s′t to st+1 ′,† ′,† if one exists, and it equals the singleton {s′,∗ t } otherwise. Let st ∈ St . We also define Ws′t ,ygood = min ′ G(y, st+1 )

(8)

Ds′t ,max = max′ G(v, st+1 )

(9)

X

(10)

y∈N (st ) v∈N (st )

δst =

−Pst j log(Pst j )

j∈N (st ) ′,∗ γst+1 ,s′t = G(s′,† t , st+1 ) − G(st , st+1 ) 1 ′  . π(s′,∗ t | st+1 , st ) = ϵ ′ 1 + (|N (st )| − 1) exp − 2ρ γs′t

(11) (12)

In words, Ws′t ,ygood is the edge weight along the shortest-distance path between the states s′t and st+1 , the constant Dst ,max is the longest shortest-path distance to st+1 from any of the candidate output states in N (s′t ), and δst is an upper bound on the expected change in G when st transitions to st+1 . Formally, δst is equal to Est+1 [G(s′t , st+1 ) − G(s′t , st ) | (st , s′t )]. Additionally, γst+1 ,s′t is the difference in edge weight between the highest utility transition and the second-highest utility transition in the private trajectory being constructed. Finally, consider partitioning N (s′t ) into: (i) the set of “best” next states, in the sense that they all attain the shortest-path distance to the true state, equal to G(s′,∗ t , st+1 ), and (ii) the set of non-best candidate next states. When all non-best candidate next states have the same shortest-path distance to ′,∗ the true state G(s′,† | st+1 , s′t ) is the probability that the best next state is t , st+1 ), we have that π(st selected. See Appendix D for a derivation of the distribution that π follows from. Figure 1 shows a visual representation of (8), (9), and G(s′,∗ t , st+1 ), which is used to compute (11). 8

v1

d

′ ,y g

oo

Ws t

s′t

G(s†,∗ t , st+1 )

v2

st+1

v3

ma

D s t, x

v4

v5

v6

Figure 1: Visualization of the constants used to compute (8), (9) and (11), where v1 , v2 , and v4 are candidate output states at t + 1. Lemma 2. Fix a Markov chain M = (S, P, p0 ) satisfying Assumption 1. Fix an adjacency parameter ρ > 0 and a privacy parameter ϵ ≥ 0. Let G = (S, E, W ) be from Definition 3. Let (Zt )t∈[n] be the joint stochastic process of the sensitive state st and the output state s′t generated by the Markov chain MZ in (4). Consider Zattract (ϵ) from (6). A sufficient condition for (st , s′t ) ∈ Zattract (ϵ) is   ′ 1 − π(s′,∗ δst t | st+1 , st ) Ws′t ,ygood > Dst ,max + for all st+1 ∈ N (st ), ′,∗ ′,∗ ′ π(st | st+1 , st ) π(st | st+1 , s′t ) ′ where Ws′t ,ygood is from (8), Ds′t ,max is from (9), δst is from (10), and π(s′,∗ t | st+1 , st ) is from (12).

♦

Next, Theorem 2 provides a way for users to measure how much of the state space Z is in the set Zattract (ϵ). Theorem 2 (Solution to Problem 2). Fix a Markov chain M = (S, P, p0 ) satisfying Assumption 1, an adjacency parameter ρ > 0, and a privacy parameter ϵ ≥ 0. Let G = (S, E, W ) be as defined in Definition 3. Let (Zt )t∈[n] be the joint stochastic process of the sensitive state st and the output state s′t generated by MZ from (4). Consider V (Zt ) from (5) and Zattract (ϵ) from (6). Let Bϵ =

max

c (st ,s′t )∈Zattract (ϵ)

G(s′t , st ),

(13)

c (ϵ) = Z \ Zattract (ϵ). Then for all v > Bϵ , where Zattract

P (V (Zt ) > v) ≤ Ct exp (−α(v − Bϵ )) ,

(14)

where Ct = ζ t e−αBϵ

XX

p0 (x)p0 (y)eαG(x,y) +

x∈S y∈S

DZattract (ϵ) = γZattract (ϵ) =

2γ

(ϵ) α = DZZattract(ϵ) , attract

max

max

min

X

(15)

G(w, y) − G(s′t , st ),

(16)

π(y | s′t ) G(y, st+1 ) − G(s′t , st ) ,

(17)

(st ,s′t )∈Zattract (ϵ) w∈N (s′t ),y∈N (st )

(st ,s′t )∈Zattract (ϵ)

1 − ζ t αDZ attract (ϵ) , e 1−ζ

y∈N (s′t )

γ2

ζ = 1 − DZZattract (ϵ) (ϵ) , and we have used G from (1) and π from (12). attract

In Theorem 2, the quantity in (16) is the most that V (Zt ) can change inside of Zattract (ϵ) across one timestep, the quantity in (17) is the smallest average change in V (Zt ) across one timestep in Zattract (ϵ), and the quantity in (13) is the largest value of V (Zt ) outside of Zattract (ϵ). Theorem 2 shows that the probability of the private state trajectory having large deviations away from the underlying sensitive state trajectory is exponentially decreasing in the size of the deviation, which ensures that the private state trajectory maintains structure-aware similarity to the sensitive one (in the sense of Remark 2) with high probability. In the next section, we show how this structure-aware similarity leads to private state trajectories that would typically be produced by the Markov chain M . 9

4

Information Preservation and Typicality

In this section, we solve Problem 3. Specifically, we answer the question of “how likely is it that a private state trajectory was generated by the Markov chain M ?” To do this, we bound the expected entropy from private state trajectories. The empirical entropy of a state trajectory Y = (Yt )t∈[n] with n ≥ 2 is Hn (Y ) = −

n 1 1 X log(P (Y )) = G(Yt−1 , Yt ), n−1 n − 1 t=1

(18)

where G is from (1). The average empirical entropy of a Markov chain is referred to as its “entropy rate”, which we denote H(S) (Cover, 1999, Chapter 4). In a Markov chain M = (S, P, p0 ), XX 1 µi Pij log(Pij ), (19) H(S) = lim − log(P (s0 s1 · · · sn )) = − n→∞ n i∈S j∈S

where µ is the stationary distribution of the Markov chain M and the second equality is a consequence of the asymptotic equipartition property (AEP) (Breiman, 1957). If a private state trajectory’s empirical entropy is substantially greater than the entropy rate H(S), then the private state trajectory contains many state-to-state transitions that occur with low probability in the Markov chain dynamics, which implies that the trajectory may have been generated using different dynamics than those of the Markov chain M . To state the average empirical entropy bound, let Kasym = max

G(u, v)

(20)

u,v∈S G(v, u) u̸=v

be the largest asymmetry ratio between shortest-path distances, i.e., the maximum ratio of (i) the shortestpath distance from state u to state v and (ii) the shortest-path distance from state v to state u. Theorem 3. Fix a Markov chain M = (S, P, p0 ) satisfying Assumption 1 with stationary distribution µ, an adjacency parameter ρ > 0, and a privacy parameter ϵ ≥ 0. Let w = (st )t∈[n] for n ≥ 2 be a sensitive state trajectory and let w′ = (s′t )t∈[n] = (M1 (st ))t∈[n] be its corresponding private state trajectory generated from applying Mechanism 1 to w. Suppose p0 = µ so that s0 ∼ µ. Then E [Hn (w′ )] ≤     √ n  1 π H(S) + + Kasym  q 2 n−1 ψ2 2

Dmax

 r erf Bϵ

2 Dmax





+ C∞

DZattract (ϵ)  + (1 + ψ2 Kasym ) V̄0 , 2γZattract (ϵ) (n − 1)(1 − ψ2 )

where ψ2 ∈ (0, 1) is the second largest eigenvalue modulus of the transition matrix for the joint Markov P P chain MZ from (4), we use V̄0 = x∈S y∈S p0 (x)p0 (y)G(x, y), Dmax is the diameter of the graph G from Definition 3, Bϵ is from (13), DZattract (ϵ) is from (16), γZattract (ϵ) is from (17), Ct is from (15), Kasym is from (20), and 1 αDZ attract (ϵ) . C∞ = lim Ct = e (21) t→∞ 1−ζ Theorem 3 quantifies how much the expected empirical entropy rate of a private state trajectory differs from the true entropy rate H(S). While the expected change in entropy is bounded by Theorem 3, the probability that a single trajectory’s entropy differs from the entropy rate H(S) by a substantial amount is also of interest. Therefore, we next state a McDiarmid-like concentration bound on the empirical entropy of private state trajectories. This bound depends on the “mixing time” of the Markov chain M , i.e., the time for p(t) to converge to µ, defined as     1 , (22) tmix = min t ≥ 0 : max max |P (Yt ∈ A | Y0 = y) − µA | ≤ y∈S A⊆S 4 where µA is the stationary distribution of the subset A ⊆ S, which is equal to µ but with entries for states s ∈ S\A removed. 10

Theorem 4 (Solution to Problem 3). Let all conditions of Theorem  3 hold. n Hn (w ) − n−1 H(S) ≥ ϕϵ + ν

Let tmix be defined as 2ν 2 (n−1)2 − 9(4n−6)D2 tmix , where ϕϵ = max

in (22). Then for n ≥ 2 we have P ≤ exp    √  q  D (1+ψ2 Kasym )V̄0 n 1 p π2 erf Bϵ D 2 + C∞ 2γZZattract (ϵ) + (n−1)(1−ψ and C∞ is from (21). n−1 ψ2 + Kasym max 2) (ϵ) ′

2

attract

Dmax

Theorem 4 bounds the probability that the entropy of a private state trajectory deviates from the entropy (n) rate of the original Markov chain M by an amount ν + ϕϵ . For a Markov chain M , the η-typical set Aη is the set of length n + 1 state trajectories satisfying H(S) − η ≤ − n1 log(P (s0 s1 · · · sn )) ≤ H(S) + η. Then, by setting η = ν + ϕϵ , Theorem 4 allows users to bound the probability that a private state trajectory is (n) in Aη given choices of ϵ and ν. Doing so ensures that the private state trajectories remain η-typical with (n) high probability. Private trajectories that lie within Aη appear as though they were generated by M , which ensures that private trajectories generated by Mechanism 1 appear as though they were generated by M .

5

Empirical Results

In this section, we solve Problem 4. We consider three Markov chain examples of varying sizes whose state trajectories represent sensitive information. First, we consider a small Markov chain (|S| = 9) in the setting of credit migration, where the transition dynamics in P represent the probability of transitioning from one credit rating to another (Nickell et al., 2000). Second, we consider a vehicle traffic example (|S| = 43), specifically traffic in the city of Gainesville, Florida, as seen in Chen et al. (2023b), where the transition dynamics in P encode the probability of driving from one segment of road onto another. Finally, we consider internet traffic in the form of a condensed subset of Wikipedia articles in the Wikispeedia dataset (|S| = 3, 817), where the transition dynamics in P encode the probability of transitioning from one Wikipedia article to another (Leskovec & Krevl, 2014). In all examples, we consider the initial distribution p0 to be the Dirac distribution centered on the initial state s0 . See Appendix F for data processing details, details on calibrating the mechanism from Chen et al. (2023b), additional simulation results, and sample private state trajectories. 5.1

Error Probability

Figure 2 shows the probability of the shortest-path distance ever exceeding an error amount v for ϵ = 1, computed via Monte-Carlo simulation with 10, 000 privately generated state trajectories based on the same sensitive state trajectory. In the Gainesville traffic example, we see that large errors, i.e., v > 5 nats, appear frequently when using the mechanism from Chen et al. (2023b), and such errors appear with probability 0.39. However, using Mechanism 1, the probability of such errors is 0.06, which is 84% smaller. Thus, we find that in a city traffic example, Mechanism 1 yields private state trajectories that, with high probability, maintain structural similarity to the underlying sensitive state trajectories. Across all examples, we see the probability of large errors decrease by multiple orders of magnitude relative to Chen et al. (2023b), which highlights the ability of our mechanism to produce more accurate private state trajectories than the state of the art. 5.2

Empirical Entropy

Figure 3 shows the average empirical entropy over 10, 000 private state trajectories produced by Mechanism 1 (with ρ = 1) and Chen et al. (2023b). We vary the trajectory length for each ϵ ∈ {1, 3, 5} and show 2 standard deviation bounds on the empirical entropy from (18) of the state trajectories generated by the original Markov chain. For all values of ϵ and all trajectory lengths, the average empirical entropy of Mechanism 1 is lower than Chen et al. (2023b). In the Gainesville traffic example, we find up to an 80% decrease in average empirical entropy compared to Chen et al. (2023b) at ϵ = 3, which highlights the increased similarity of private state trajectories generated by Mechanism 1 to their underlying sensitive state trajectories. Additionally, the entropy in Chen et al. (2023b) increases with trajectory length, while the entropy of Mechanism 1 remains constant after a certain trajectory length. This difference occurs because a longer trajectory increases the probability that the mechanism in Chen et al. (2023b) takes an incorrect transition and begins random walking, in which case the entropy of their mechanism approaches that of a uniform random walk over the state space. 11

P (V (Zt ) > v)

Chen et al. (ϵ = 1.0)

Mechanism 1 (ϵ = 1.0)

100

10−1

10−1

10−2

10−3

10−3

10−4

10−5

10

10−7 0

10−5

−6

10−7 0

5 10 15 Error, v [nats] (a)

5 10 15 Error, v [nats] (b)

0

5 10 15 Error, v [nats] (c)

Figure 2: Probability of large errors in private trajectories in the (a) credit migration, (b) Gainesville traffic, and (c) Wikispeedia datasets. Across all examples, the probability of large errors is substantially lower than in Chen et al. (2023b), with the largest decrease occurring in the credit migration example at v = 15; the probability of errors this large is 0.003 under Chen et al. (2023b) and 2 × 10−7 under Mechanism 1, which is a 4-order-of-magnitude decrease.

E [Hn (s′ )]

Chen et al. (ϵ = 1.0) Mechanism 1 (ϵ = 1.0)

Chen et al. (ϵ = 3.0) Mechanism 1 (ϵ = 3.0)

Chen et al. (ϵ = 5.0) Mechanism 1 (ϵ = 5.0)

True Entropy Rate H(X ) True Process ±2σ

1.6 1.4 1.2 1 0.8

2 0 40 60 80 Trajectory Length, n (a) E [Hn (s′ )]

20

100

20

40 60 80 Trajectory Length, n (b)

100

4 3 2 20

40 60 80 Trajectory Length, n (c)

100

Figure 3: Empirical entropy with varying ϵ and trajectory length in the (a) credit migration, (b) Gainesville traffic, and (c) Wikispeedia examples. In Mechanism 1 the average empirical entropy remains constant beyond a certain trajectory length, while the average empirical entropy in Chen et al. (2023b) grows. This growth is a result of the random walking in their mechanism, because longer trajectories have a higher probability of an incorrect transition, which leads to their mechanism to begin random walking.

6

Conclusion

We have presented a framework for privatizing Markov chain state trajectories online in a way that improves on the state of the art. We proved that with high probability the errors induced by our mechanism remain small, and that with high probability private state trajectories remain in the η-typical set of the Markov chain that generated the underlying sensitive state trajectory. Empirically, we improved on the state of the art by lowering the expected entropy by up to 80% and lowering the probability of large errors by up to 4 orders of magnitude. Future work will develop an offline mechanism and will develop a framework to privatize state and action trajectories in other stochastic processes, including Markov decision processes. 12

Acknowledgements This work was partially supported by ONR under grant N00014-24-1-2432, AFOSR under grant FA955019-1-0169, and NSF Graduate Research Fellowship under grant DGE-2039655. Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of sponsoring agencies.

References Sultan Amed, Tanmay Sen, and Sayantan Banerjee. Fsl-bdp: Federated survival learning with bayesian differential privacy for credit risk modeling. arXiv preprint arXiv:2601.11134, 2026. Alexander Benvenuti, Brendan Bialy, Miriam Dennis, and Matthew Hale. Differentially private linear programming: Reduced sub-optimality and guaranteed constraint satisfaction. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 40, pp. 19702–19710, 2026a. Alexander Benvenuti, Brandon Fallin, Calvin Hawkins, Brendan Bialy, Miriam Dennis, Warren Dixon, and Matthew Hale. Differentially private data-driven markov chain modeling. arXiv preprint arXiv:2602.22443, 2026b. Alexander Benvenuti, Huaiyuan Rao, and Matthew Hale. Differential privacy for symbolic trajectories via the permute-and-flip mechanism. arXiv preprint arXiv:2603.28903, 2026c. Andrea Bertazzi, Tim Johnston, Gareth O Roberts, and Alain Oliviero Durmus. Differential privacy guarantees of markov chain monte carlo algorithms. In International Conference on Machine Learning, pp. 3931–3951. PMLR, 2025. Alberto Blanco-Justicia, David Sánchez, Josep Domingo-Ferrer, and Krishnamurty Muralidhar. A critical review on the use (and misuse) of differential privacy in machine learning. ACM Computing Surveys, 55 (8):1–16, 2022. Zachary M Boyd, Nicolas Fraiman, Jeremy Marzuola, Peter J Mucha, Braxton Osting, and Jonathan Weare. A metric on directed graphs and markov chains based on hitting probabilities. SIAM Journal on Mathematics of Data Science, 3(2):467–493, 2021. Leo Breiman. The individual ergodic theorem of information theory. The Annals of Mathematical Statistics, 28(3):809–811, 1957. Bo Chen, Calvin Hawkins, Mustafa O Karabag, Cyrus Neary, Matthew Hale, and Ufuk Topcu. Differential privacy in cooperative multiagent planning. In Uncertainty in Artificial Intelligence, pp. 347–357. PMLR, 2023a. Bo Chen, Kevin Leahy, Austin Jones, and Matthew Hale. Differential privacy for symbolic systems with application to markov chains. Automatica, 152:110908, 2023b. Gaoyi Chen, Yan Huang, and Chenxi Qiu. Context-aware metric differential privacy for vehicle trajectory data. arXiv preprint arXiv:2605.26351, 2026. Ronald R Coifman and Stéphane Lafon. Diffusion maps. Applied and Computational Harmonic Analysis, 21(1):5–30, 2006. Thomas M Cover. Elements of Information Theory. John Wiley & Sons, 1999. Yves-Alexandre De Montjoye, César A Hidalgo, Michel Verleysen, and Vincent D Blondel. Unique in the crowd: The privacy bounds of human mobility. Scientific Reports, 3(1):1376, 2013. Jie Dong, Gui Li, Wenkai Ma, and Jianshun Liu. Personalized recommendation system based on social tags in the era of internet of things. Journal of Intelligent Systems, 31(1):681–689, 2022. 13

Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography Conference, pp. 265–284. Springer, 2006. Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3–4):211–407, 2014. Brandon Fallin, Calvin Hawkins, Bo Chen, Parham Gohari, Alexander Benvenuti, Ufuk Topcu, and Matthew Hale. Differential privacy for stochastic matrices using the matrix dirichlet mechanism. In 2023 62nd IEEE Conference on Decision and Control (CDC), pp. 5067–5072. IEEE, 2023. Robert W Floyd. Algorithm 97: shortest path. Communications of the ACM, 5(6):345–345, 1962. Robert G Gallager. Stochastic Processes: Theory for Applications. Cambridge University Press, 2013. Parham Gohari, Matthew Hale, and Ufuk Topcu. Privacy-preserving policy synthesis in markov decision processes. In 2020 59th IEEE Conference on Decision and Control (CDC), pp. 6266–6271. IEEE, 2020. Qiuming Gong, Shawn Midlam-Mohler, Vincenzo Marano, and Giorgio Rizzoni. An iterative markov chain approach for generating vehicle driving cycles. SAE International Journal of Engines, 4(1):1035–1045, 2011. Efehan Guner and M Emre Gursoy. Learning markov chain models from sequential data under local differential privacy. In European Symposium on Research in Computer Security, pp. 359–379. Springer, 2023. Bruce Hajek. Hitting-time and occupation-time bounds implied by drift analysis with applications. Advances in Applied probability, 14(3):502–525, 1982. Justin Hsu, Marco Gaboardi, Andreas Haeberlen, Sanjeev Khanna, Arjun Narayan, Benjamin C Pierce, and Aaron Roth. Differential privacy: An economic method for choosing epsilon. In 2014 IEEE 27th Computer Security Foundations Symposium, pp. 398–410. IEEE, 2014. Tom Hurd and Alexey Kuznetsov. Affine markov chain models of multifirm credit migration. Journal of Credit Risk, 3(1):3–29, 2007. Yusuf Jafry and Til Schuermann. Measurement, estimation and comparison of credit migration matrices. Journal of Banking & Finance, 28(11):2603–2639, 2004. Bargav Jayaraman and David Evans. Evaluating differentially private machine learning in practice. In 28th USENIX Security Symposium (USENIX Security 19), pp. 1895–1912, 2019. Michael Kalkbrener and Natalie Packham. A markov approach to credit rating migration conditional on economic states. Canadian Journal of Statistics, pp. e70039, 2026. Jerome Le Ny and George J Pappas. Differentially private filtering. IEEE Transactions on Automatic Control, 59(2):341–354, 2013. Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http://snap. stanford.edu/data, June 2014. Ryan McKenna and Daniel R Sheldon. Permute-and-flip: A new mechanism for differentially private selection. Advances in Neural Information Processing Systems, 33:193–203, 2020. Sean P Meyn and Richard L Tweedie. Stability of markovian processes i: Criteria for discrete-time chains. Advances in Applied Probability, 24(3):542–574, 1992. Minghui Min, Jiahui Liu, Mingge Cao, Shiyin Li, Hongliang Zhang, Miao Pan, and Zhu Han. Road networkaware personalized trajectory protection with differential privacy under spatiotemporal correlations. arXiv preprint arXiv:2511.21020, 2025. 14

Andres Munoz, Umar Syed, Sergei Vassilvtiskii, and Ellen Vitercik. Private optimization without constraint violations. In International Conference on Artificial Intelligence and Statistics, pp. 2557–2565. PMLR, 2021. Pamela Nickell, William Perraudin, and Simone Varotto. Stability of rating transitions. Journal of Banking & Finance, 24(1-2):203–227, 2000. Daniel Paulin. Concentration inequalities for markov chains by marton couplings and spectral methods. Electronic Journal of Probability, 2015. Natalia Ponomareva et al. How to dp-fy ml: A practical guide to machine learning with differential privacy. Journal of Artificial Intelligence Research, 77:1113–1201, 2023. Lawrence R Rabiner. A tutorial on hidden markov models and selected applications in speech recognition. Proceedings of the IEEE, 77(2):257–286, 2002. Steffen Rendle, Christoph Freudenthaler, and Lars Schmidt-Thieme. Factorizing personalized markov chains for next-basket recommendation. In Proceedings of the 19th International Conference on World Wide Web, pp. 811–820, 2010. Sai Wang, Huijuan Lian, Lei Shi, Gaolei Li, and Yan Cao. Semantic-graph-indistinguishability: A novel approach to location privacy protection under road networks. In 2025 IEEE 24th International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom), pp. 3072–3080. IEEE, 2025. Yu Wang, Matthew Hale, Magnus Egerstedt, and Geir E Dullerud. Differentially private objective functions in distributed cloud-based optimization. In 2016 IEEE 55th Conference on Decision and Control (CDC), pp. 3688–3694. IEEE, 2016. Youwen Zhu, Yuanyuan Hong, Qiao Xue, Xiao Lan, Yushu Zhang, and Yong Xiang. Ldgi: Locationdiscriminative geo-indistinguishability for location privacy. IEEE Transactions on Knowledge and Data Engineering, 37(3):1282–1293, 2024.

A

Supporting Definitions and Lemmas

The following definitions and lemmas are used throughout these appendices. Definition 5 (Quasi-metric for Directed Graphs). Fix a directed weighted graph G = (V, E, W ) such that all the weights in W are non-negative. Given x, y, z ∈ V , the shortest-path distance G from (1) forms a quasi-metric over the node set V , i.e., G has the following properties: 1. G(x, y) ≥ 0 2. G(x, y) = 0 ⇐⇒ x = y 3. G(x, y) ≤ G(x, z) + G(z, y). Throughout these appendices, we refer to the third property of Definition 5 as the “triangle inequality for directed graphs”. The following lemma is used to derive the concentration bound in Theorem 4. Lemma 3 (McDiarmid’s Inequality for Markov Chains; Paulin (2015)). Let X1 . . . , Xn be a time homogeneous Markov chain taking values in a Polish state space Λ = Λ1 × . . . × Λn with mixing time tmix as defined in (22). Suppose that f : Λ → R satisfies f (x) − f (y) ≤

n X i=1

15

ci 1[xi ̸= yi ]

for some c ∈ RN + . Then for any k ≥ 0, P (f (X) − E [f (X)] ≥ k) ≤ exp

−2k 2

!

2

9 ∥c∥2 tmix

. ♦

B

Existing privacy mechanism from Chen et al. (2023b)

Consider a Markov1 chain M = (S, P, s0 ). Given a state trajectory w = s0 s1 · · · sn ∈ S n+1 , we want to privately generate a new trajectory w′ = s0 s′1 · · · s′n where each state s′t is selected online. That is, the private state trajectory w′ is generated at the same time as w. Consider generating s′t for a fixed t ∈ [n] \ {0}. First the actual state of the Markov chain transitions from st−1 to st . Then the mechanism selects a state s′t ∈ S to publicly share. Let v, w be two state trajectories of length n + 1. Then, the Hamming distance between v and w, denoted dH (v, w), is the number of entries where v and w differ, i.e., dH (w, v) = |{i | wi ̸= vi }|. In Chen et al. (2023b), they consider the following notion of adjacency for Markov chain state trajectories. Definition 6 (Word Adjacency; (Chen et al., 2023b)). Fix a number of state-to-state transitions n ∈ N and an adjacency parameter b ∈ N. Two trajectories w, v ∈ S n+1 are said to be adjacent if dH (w, v) ≤ b. ▲ Next we formally state the mechanism in Chen et al. (2023b). First, define (
1 if P st | s′t−1 > 0 ′ β(st , st−1 ) = 0 otherwise as an indicator function that returns 1 if there exists a feasible transition from s′t−1 to st , and 0 otherwise. A transition from s′t−1 to st is referred to as a “correct” transition because it ensures that the state at time t in the private state trajectory is the same as the non-private state at time t in the true state trajectory. To minimize the Hamming distance between the private state trajectory and the underlying sensitive state trajectory, a correct transition should be the most likely to occur, which is what motivates the following mechanism. Mechanism 2 (Chen et al. (2023b)). Fix a probability space (Ω, F, P) and a Markov chain M = (S, P, s0 ). Given a state trajectory w = s0 s1 · · · sn ∈ S n+1 , select an output state trajectory w′ = s0 s′1 · · · s′n ∈ S n+1 such that  ′  if st = s′t and β(s′t , s′t−1 ) = 1 τ (st , st−1 )  ′ ′ 1−τ (st ,st−1 )β(st ,st−1 ) if st ̸= s′t and β(s′t , s′t−1 ) = 1 P (M2 (st ) = s′t ) = |N (s′t−1 )|−β(st ,s′t−1 )   0 otherwise. △ In Mechanism 2, the probability of a correct transition is τ (st , s′t−1 ). If N (s′t−1 ) is the neighborhood set of state s′t−1 , and the correct transition is selected with probability τ (st , s′t−1 ), then the remaining states are each selected with probability 1 − τ (st , s′t−1 ) . |N (s′t−1 )| − 1 If the correct transition is not feasible, then the next state is sampled uniformly from the neighborhood set N (s′t−1 ). All non-feasible transitions have probability 0 to ensure that the private state trajectory is a feasible (though not necessarily likely) state trajectory from the Markov chain M . Theorem 5 (Chen et al. (2023b)). Mechanism 2 is ϵ-differentially private with respect to the adjacency relation in Definition 6 if 1 τ (st , s′t−1 ) = . ′ (|N (st−1 )| − 1) exp(− bϵ ) + 1 1 In order to match the definition of adjacency from Chen et al. (2023b), the definition of a Markov chain in this section considers a fixed initial state s0 rather than a distribution over initial states. Therefore, a sensitive word and its privatization both begin at s0 .

16

One benefit of Mechanism 2 is that it provably gives the highest probability of making the correct transition of any possible mechanism. However, the major drawback is that this mechanism exhibits random walking if the correct transition is infeasible. Specifically, if β(st , s′t−1 ) = 0, then all of the mechanism’s output probabilities become ( 1 if β(s′t , s′t−1 ) = 1 ′ ′ P (M2 (st ) = st ) = |N (st−1 )| 0 otherwise, which initiates a uniform random walk over the state space. This random walking behavior maximizes the probability of the correct transition when available. However, in a setting where the Markov chain states have structural similarities, e.g., in a city or internet traffic setting, there exists a notion of states being closer together and further away, which means that some incorrect transitions introduce larger errors than others. Thus, random walking may result in private state trajectories with little structural similarity to the underlying sensitive state trajectory.

C

Alternate Mechanism Design

In this section2 , we show how a mechanism similar to Mechanism 1 may be designed using Definition 6. Such a mechanism uses the notion of adjacency for state trajectories in Chen et al. (2023b). However, we demonstrate why this notion yields a privacy mechanism with poor accuracy at strong levels of privacy, and thus why a different adjacency relation is useful. First, we must compute the sensitivity of the utility function u with respect to the adjacency relation in Definition 6. Lemma 4 (Sensitivity). Fix a Markov chain M = (S, P, s0 ) satisfying Assumption 1 and an adjacency parameter b ∈ N \ {0}. Let w = s0 s1 · · · sn ∈ S n+1 and v = s0 s̃1 · · · s̃n ∈ S n+1 be two adjacent state trajectories in the sense of Definition 6. The sensitivity of u from (2) under this adjacency relation is ∆u = max n+1 y∈S

max

w,v∈S n+1 Adjn,b,d (w,v)=1

|u(w, y) − u(v, y)| ≤ bDmax ,

H

where Dmax is the diameter of the graph G from Definition 3.

♦

Proof. Let y = y0 · · · yn ∈ S n+1 . Substituting the utility function into the definition of sensitivity gives ∆u = max n+1 y∈S

maxn+1

X

w,v∈S Adjn,b,d (w,v)=1 t∈[n]

G(yt , s̃t ) −

X

G(yt , st ) .

t∈[n]

H

Let K be the set of indices t ∈ [n] such that s̃t ̸= st . From Definition 1, |K| ≤ b. We then have X ∆u = max max |G(yt , s̃t ) − G(yt , st )| . n+1 n+1 y∈S

w,v∈S t∈K Adjn,b,d (w,v)=1

(23)

H

From the triangle inequality for directed graphs in Definition 5, we have G(yt , st ) ≤ G(yt , s̃t ) + G(s̃t , st ), and rearranging yields

|G(yt , s̃t ) − G(yt , st )| ≤ G(s̃t , st ).

(24)

The farthest apart two states can be is the graph diameter, and therefore G(s̃t , st ) ≤ Dmax . Accordingly, using (23) and (24) gives X ∆u ≤ Dmax ≤ bDmax . t∈K

2 To continue matching the definition of adjacency in Chen et al. (2023b), we use the definition of a Markov chain considered

in Appendix B with a fixed initial state s0 .

17

Next we state the mechanism of interest. Given the neighborhood set of the previous private state, namely N (s′t−1 ), and the current true state, st , we select the next private state s′t via the following mechanism. Mechanism 3. Fix a Markov chain M = (S, P, p0 ) satisfying Assumption 1, an adjacency parameter b ∈ N \ {0}, and a privacy parameter ϵ ≥ 0. Consider G = (S, E, W ) from Definition 3 and G be from (1). Let Dmax be the diameter of G. At each time t, given the current state of the sensitive trajectory st , the mechanism M3 randomly selects the output state according to   ϵG(s′t ,st ) exp − 2bDmax  . P (M3 (st ) = s′t ) = P ϵG(y,st ) y∈N (s′ ) exp − 2bDmax t−1

△ The diameter of graphs in many practical applications is large, in  a mechanism that provides similar  resulting ϵG(s′t ,st ) performance to random walking because the numerator exp − 2bDmax approaches 1 when Dmax is large. Thus, Mechanism 3’s performance scales poorly with strong privacy and large graphs, which motivates the approach in Section 3.

D

Exponential Mechanism for Online Trajectory Privacy

The exponential mechanism is a privacy mechanism related to the permute-and-flip mechanism by virtue of also being used to privately select an approximation to some sensitive data (Dwork et al., 2014). While the permute-and-flip (PF) mechanism is often more accurate than (and is always at least as accurate as) the exponential mechanism, analysis of the PF mechanism is often difficult due to the lack of closed form for the PMF it induces over outputs. However, the PF mechanism stochastically dominates the exponential mechanism, i.e., the PF mechanism selects the highest-utility choice with at least the same probability as the exponential mechanism. Therefore, accuracy and privacy results for the exponential mechanism can be used to characterze the PF mechanism (McKenna & Sheldon, 2020, Theorem 2). Accordingly, we state the following exponential mechanism that we use to prove results about Mechanism 1. Mechanism 4 (Alternate Solution to Problem 1). Fix a Markov chain M = (S, P, p0 ) satisfying Assumption 1, an adjacency parameter ρ > 0, and a privacy parameter ϵ ≥ 0. Let G = (S, E, W ) be from Definition 3. At each time t ∈ [n], given the state st , the mechanism M4 selects the output state s′t according to   ϵG(s′ ,s ) exp − 2ρt t ,  P (M4 (st ) = s′t ) = P (25) ϵG(y,st ) y∈N (s′ ) exp − 2ρ t−1

where G is from (1).

△

In Appendix E.3, we show that Mechanism 4 is ϵ-differentially private as a means of showing that Mechanism 1 is ϵ-differentially private. Next, we show how (12) follows from (25). Consider the case with one best next candidate state (i.e., the candidate next state with the shortest shortest-path distance to the true state st+1 ), and let it’s shortestpath distance be G(s′,∗ t , st+1 ). Additionally, let every other non-best candidate next state have the utility G(s′,† , s ). Then, the probability that the best state is selected is t+1 t   ϵG(s′,∗ t ,st+1 ) exp −
2ρ   P M4 (st+1 ) = s′,∗ =P t ϵG(y,st ) exp − ′ y∈N (st−1 ) 2ρ   ϵG(s′,∗ t ,st+1 ) exp − 2ρ = (26)    . ϵG(s′,∗ ϵG(s′,† ′ t ,st+1 ) t ,st+1 ) exp − + (|N (s )| − 1) exp − t−1 2ρ 2ρ 18

  ϵG(s′,∗ t ,st+1 ) Dividing the numerator and denominator of (26) by exp − gives 2ρ   ϵG(s′,∗ t ,st+1 ) exp − 2ρ 1  ,   =  ′,† ′,∗ ϵG(st ,st+1 ) ϵG(st ,st+1 ) ′ )| − 1) exp − ϵ γ ′ ′ 1 + (|N (s + (|N (s )| − 1) exp − exp − s t t−1 2ρ t 2ρ 2ρ

(27)

′ where γ is from (11). The expression in (27) matches that of π(s′,∗ t | st+1 , st ) from (12).

E

Omitted Proofs

E.1

Proof of Proposition 1

From the Markov property, the probability of a path w = s0 · · · sn where s0 = u is P (w) =

n Y

Psi−1 si .

i=1

The most likely path between u and v is then any w ∈ arg max ∗

n Y

(28)

Psi−1 si ,

w∈V(u,v) i=1

where V(u, v) is the set of all trajectories of any length between states u and v. The log function is strictly monotonically increasing, and we transform (28) by maximizing over the log probability via ! n n X Y ∗ log(Psi−1 si ). w ∈ arg max log Psi−1 si = arg max w∈V(u,v)

w∈V(u,v) i=1

i=1

Since finding the maximum of a function is equivalent to finding the minimum of its negative, we have w∗ ∈ arg min

n X

− log(Psi−1 si ) = arg min

w∈V(u,v) i=1

n X

Wsi−1 si .

w∈V(u,v) i=1

Pn We see that minw∈V(u,v) i=1 Wsi−1 si = G(u, v), and thus the most likely path from u to v, namely w∗ , yields the shortest path distance from u to v. E.2

Proof of Lemma 1

Let y = y0 · · · yn ∈ S n+1 . Substituting the utility function into the definition of the sensitivity, for adjacent w, v we have that max

y∈S n+1

max

w,v∈S n+1 Adjn,ρ,Gsym (w,v)=1

|u(w, y) − u(v, y)| = max n+1 y∈S

n X

max

G(yt , s̃t ) − G(yt , st ) .

w,v∈S n+1 t=0 Adjn,ρ,Gsym (w,v)=1

From the triangle inequality we find max n+1

y∈S

n X

maxn+1

w,v∈S

Adjn,ρ,Gsym (w,v)=1

G(yt , s̃t ) − G(yt , st ) ≤ max n+1

maxn+1

y∈S

t=0

w,v∈S

Adjn,ρ,Gsym (w,v)=1

n X

|G(yt , s̃t ) − G(yt , st )|.

t=0

An application of the triangle inequality for directed graphs in Definition 5 then yields max n+1

y∈S

maxn+1

w,v∈S

Adjn,ρ,Gsym (w,v)=1

n X

|G(yt , s̃t ) − G(yt , st )| ≤

t=0

maxn+1

w,v∈S

Adjn,ρ,Gsym (w,v)=1

≤

maxn+1

w,v∈S

Adjn,ρ,Gsym (w,v)=1

19

n X

G(st , s̃t )

t=0 n X t=0

Gsym (st , s̃t ),

where Gsym is from Definition 4. Substituting in the adjacency relation from Definition 4 gives maxn+1

max n+1

y∈S

maxn+1

|u(w, y) − u(v, y)| ≤

w,v∈S

w,v∈S

Adjn,ρ,Gsym (w,v)=1

Adjn,ρ,Gsym (w,v)=1

n X

Gsym (st , s̃t ) ≤ ρ,

t=0

which completes the proof. E.3

Proof of Theorem 1

To show that Mechanism 1 is ϵ-differentially private, we first prove that Mechanism 4 from Appendix D is ϵ-differentially private, and the fact that Mechanism 1 is ϵ-differentially private follows from its stochastic dominance of Mechanism 4. For adjacent sensitive input words x = x0 · · · xn and y = y0 · · · yn and a private output word z ′ = z0 · · · zn we have n P (z0 | x0 ) Y P (zt | xt , zt−1 ) P (z ′ | x) = . P (z ′ | y) P (z0 | y0 ) t=1 P (zt | yt , zt−1 )

(29)

In Mechanism 1 we have z0 ∼ p0 independent of x and y. Thus, (29) becomes n P (z ′ | x) Y P (zt | xt , zt−1 ) = . P (z ′ | y) t=1 P (zt | yt , zt−1 )

(30)

Substituting the PMF from Mechanism 4 gives P (zt | xt , zt−1 ) = exp P (zt | yt , zt−1 )



  ϵ G(s, y ) exp − t
s∈N (zt−1 ) 2ρ ϵ   . G(zt , yt ) − G(zt , xt )  P ϵ 2ρ exp − G(s, x ) t s∈N (zt−1 ) 2ρ 

P

From the triangle inequality for directed graphs in Definition 5, we have    
ϵ ϵ exp G(zt , yt ) − G(zt , xt ) ≤ exp Gsym (xt , yt ) , 2ρ 2ρ

(31)

(32)

where Gsym is from Definition 4. Next we bound the rightmost term in (31). Again using the triangle inequality for directed graphs gives −G(s, yt ) ≤ −G(s, xt ) + Gsym (xt , yt ). ϵ Multiplying by 2ρ , taking the exponential, and taking the sum over s ∈ N (zt−1 ) gives       X X ϵ ϵ ϵ exp − G(s, yt ) ≤ Gsym (xt , yt ) . exp − G(s, xt ) exp 2ρ 2ρ 2ρ s∈N (zt−1 )

(33)

s∈N (zt−1 )

Substituting (32) and (33) into (31) gives   ϵ exp − G(s, y ) t s∈N (zt−1 ) 2ρ P (zt | xt , zt−1 ) ϵ   ≤ exp G(zt , yt ) − G(zt , xt )  P ϵ P (zt | yt , zt−1 ) 2ρ exp − G(s, x ) t s∈N (zt−1 ) 2ρ     P ϵ ϵ  
s∈N (zt−1 ) exp − 2ρ G(s, xt ) exp 2ρ Gsym (xt , yt ) ϵ    ≤ exp G(zt , yt ) − G(zt , xt )  P ϵ 2ρ s∈N (zt−1 ) exp − 2ρ G(s, xt ) 



P

   ϵ ϵ Gsym (xt , yt ) exp Gsym (xt , yt ) 2ρ 2ρ   ϵ = exp Gsym (xt , yt ) , ρ

≤ exp



20

(34)

where the third inequality uses the triangle inequality for directed graphs from Definition 5. Substituting (34) into (30) gives !   n n n Y ϵ ϵX P (zt | xt , zt−1 ) Y Gsym (xt , yt ) . ≤ exp Gsym (xt , yt ) = exp P (zt′ | yt , zt−1 ) t=1 ρ ρ t=1 t=1 Substituting in the definition of adjacency gives exp

! n ϵX Gsym (xt , yt ) ≤ exp(ϵ), ρ t=1

which completes the proof. E.4

Proof of Lemma 2

To satisfy the Foster-Lyapunov condition in (3), we see that G(s′t+1 , st+1 ) must satisfy   Est+1 ,s′t+1 G(s′t+1 , st+1 ) − G(s′t , st ) | (st , s′t ) < 0.

(35)

We then add and subtract G(s′t , st+1 ) to find   Est+1 ,s′t+1 G(s′t+1 , st+1 ) − G(s′t , st ) | (st , s′t )   = Est+1 ,s′t+1 (G(s′t+1 , st+1 ) − G(s′t , st+1 )) + (G(s′t , st+1 ) − G(s′t , st )) | (st , s′t ) . We next separate the expectations to yield   Est+1 ,s′t+1 (G(s′t+1 , st+1 ) − G(s′t , st+1 )) + (G(s′t , st+1 ) − G(s′t , st )) | (st , s′t ) h i   = Est+1 Es′t+1 G(s′t+1 , st+1 ) − G(s′t , st+1 ) | s′t , st+1 | st + Est+1 [G(s′t , st+1 ) − G(s′t , st ) | (st , s′t )] .

(36)

We now bound the first and second terms on the right-hand side of (36) individually. Beginning with the second term on the right-hand side of (36), from the triangle inequality for directed graphs in Definition 5 we have G(s′t , st+1 ) − G(s′t , st ) ≤ G(st , st+1 ). Taking the expectation gives Est+1 [G(s′t , st+1 ) − G(s′t , st ) | (st , s′t )] ≤ Est+1 [G(st , st+1 ) | st ] .

(37)

We can then compute the expectation in (37) as Est+1 [G(s′t , st+1 ) − G(s′t , st ) | (st , s′t )] ≤ Est+1 [G(st , st+1 ) | st ] =

X

−Pst j log(Pst j ) = δst .

(38)

j∈N (st )

Next, we bound the first term on the right-hand side of (36). Suppose that at time t, there is at least one possible next state along a shortest path from the private state at time t to the sensitive state at time t + 1. There are at most |N (s′t )|−1 possible next states not on a shortest path. Let ygood be a state along a shortest path from s′t to the sensitive state st+1 , and let ybad be a state not on a shortest path from s′t to st+1 if such a non-shortest path exists3 . If the private state trajectory transitions from s′t to ygood , then the distance from ygood to st+1 is less than the distance from s′t to st+1 by an amount equal to the edge weight Ws′t ,ygood . Thus, in this case, G(ygood , st+1 ) − G(s′t , st+1 ) = (G(s′t , st+1 ) − Ws′t ,ygood ) − G(s′t , st+1 ) = −Ws′t ,ygood ,

(39)

3 We state this proof in the case where y bad exists, though it is not guaranteed to exist. However, the resulting bound holds

whether ybad exists or not.

21

where Ws′t ,ygood is the edge weight from s′t to ygood , i.e., Ws′t ,ygood =

min G(w, st+1 ).

w∈N (s′t )

If the private state trajectory transitions from s′t to ybad , then the distance from ybad to st+1 can be greater than the distance from s′t to st+1 by up to Ds′t ,max = maxv∈N (s′t ) G(v, st+1 ). From the triangle inequality for directed graphs in Definition 5, we have G(ybad , st+1 ) ≤ G(ybad , s′t ) + G(s′t , st+1 ), and thus rearranging gives G(ybad , st+1 ) − G(s′t , st+1 ) ≤ G(s′t , st+1 ) + Ds′t ,max − G(s′t , st+1 ) = Ds′t ,max ,

(40)

where Ds′t ,max is from (9). From applying the law of total expectation to the first term on the right-hand side of (36) and using (39) and (40), we then have   Es′t+1 G(s′t+1 , st+1 ) − G(s′t , st+1 ) | s′t , st+1 ≤ −Pgood Ws′t ,ygood + (1 − Pgood )Ds′t ,max , (41) where Pgood is the probability that s′t+1 = ygood for any ygood , i.e., any candidate next state along a shortest ′,† ′,† ′,† path from s′t to st+1 . Let s′,∗ t ∈ arg minj∈N (s′t ) G(j, st+1 ), and let st ∈ St , where St is from (7). For ′ any ygood , the lowest probability of having st+1 = ygood under Mechanism 4 (from Appendix D) occurs when there exists only one ygood and all other candidate next states have equal utility. In this scenario, we find ′ Pgood = π(s′,∗ t | st+1 , st ) =

where

1 1 + (|N (s′t )| − 1) exp



ϵ − 2ρ γs′t

,

(42)

′,∗ γst+1 ,s′t = G(s′,† t , st+1 ) − G(st , st+1 ).

Substituting (41) and (42) into the first term on the right-hand side of (36) and substituting (38) into the second term on the right hand side of (36) gives   Est+1 ,s′t+1 G(s′t+1 , st+1 ) − G(s′t , st ) | (st , s′t )   ′,∗ ′ ′ ≤ Est+1 −π(s′,∗ t | st+1 , st )Ws′t ,ygood + (1 − π(st | st+1 , st ))Ds′t ,max | st + δst .

(43)

A sufficient condition for the right-hand side of (43) to be strictly negative is for ′,∗ ′ ′ −π(s′,∗ t | st+1 , st )Ws′t ,ygood + (1 − π(st | st+1 , st ))Ds′t ,max + δst < 0

to hold for all st+1 ∈ N (st ). Rearranging to solve for Ws′t ,ygood yields the equivalent sufficient condition   ′ δst 1 − π(s′,∗ t | st+1 , st ) Ds′t ,max + . (44) Ws′t ,ygood > ′,∗ ′,∗ ′ π(st | st+1 , st ) π(st | st+1 , s′t ) Thus, given the joint state (st , s′t ), from (35) we find that E [V (Zt+1 ) − V (Zt ) | Zt ] < 0 holds if (44) holds for all st+1 ∈ N (st ), which completes the proof. E.5

Proof of Theorem 2

For the concentration bound, we will invoke (Hajek, 1982, Theorem 2.3). To do so, we require several constants. First, we bound how much V (Zt ) may change in one timestep within Zattract (ϵ) via   ′ |V (Zt+1 ) − V (Zt )| ≤ max max G(w, y) − G(s , s ) = DZattract (ϵ) . t t ′ ′ (st ,st )∈Zattract (ϵ)

w∈N (st ),y∈N (st )

22

Next, we require the smallest expected drift in one timestep within Zattract (ϵ), which is γZattract (ϵ) =

X

min

(st ,s′t )∈Zattract (ϵ)

π(y | s′t )(G(y, st ) − G(s′t , st )) .

y∈N (s′t )

Finally, we require the largest value of V (Zt ) outside of Zattract (ϵ), which is Bϵ =

max

c (st ,s′t )∈Zattract (ϵ)

G(s′t , st ),

c where Zattract (ϵ) = Z \ Zattract (ϵ) and Z is from the joint Markov chain in (4). Then, from Equation (2.8) in (Hajek, 1982, Theorem 2.3) we have

P (V (Zt ) > v | Z0 ) ≤ ζ t eα(V (Z0 )−v) +

1 − ζt DH eα(Bϵ −v) , 1−ζ

(45)

where α=

2γZattract (ϵ) , DZattract (ϵ)

ζ =1−

2 γZ attract (ϵ)

, DZattract (ϵ) DH = exp(αDZattract (ϵ) ) are from Lemma 2.1 and Conditions D1 and D2 in Hajek (1982). Taking the expectation over the randomness in Z0 in (45) to remove the conditioning on Z0 gives h i 1 − ζt P (V (Zt ) > v) ≤ ζ t E eα(V (Z0 )−v) + DH exp(−α(v − Bϵ )). 1−ζ Adding and subtracting αBϵ in the exponent in the first term of (46) gives h i 1 − ζt P (V (Zt ) > v) ≤ ζ t E eα(V (Z0 )−Bϵ +Bϵ −v) + DH exp(−α(v − Bϵ )) 1−ζ h i 1 − ζt = ζ t E eα(V (Z0 )−Bϵ ) e−α(v−Bϵ ) + DH exp(−α(v − Bϵ )) 1−ζ   h i 1 − ζt = ζ t E eα(V (Z0 )−Bϵ ) + DH exp(−α(v − Bϵ )). 1−ζ   Then, we compute the expectation E eα(V (Z0 )−Bϵ ) as h i h i X E eα(V (Z0 )−Bϵ ) = e−αBϵ E eαV (Z0 ) = e−αBϵ p0 (x)p0 (y)eαG(x,y) , x,y∈S

where p0 is the initial distribution of M , which gives the bound   t XX 1 − ζ P (V (Zt ) > v) ≤ ζ t e−αBϵ p0 (x)p0 (y)eαG(x,y) + eαDZattract (ϵ)  exp(−α(v − Bϵ )). 1−ζ x∈S y∈S

Letting Ct = ζ t e−αBϵ

XX

p0 (x)p0 (y)eαG(x,y) +

x∈S y∈S

we have

1 − ζ t αDZ attract (ϵ) , e 1−ζ

P (V (Zt ) > v) ≤ Ct exp (−α(v − Bϵ )) ,

which completes the proof. 23

(46)

E.6

Proof of Theorem 3

Taking the expectation of (18) with Y = s′ gives E [Hn (s′ )] =

n  1 X  E G(s′t−1 , s′t ) . n − 1 t=1

From the triangle inequality for directed graphs in Definition 5, we have     E G(s′t−1 , s′t ) ≤ E G(s′t−1 , st−1 ) + E [G(st−1 , st )] + E [G(st , s′t )] .

(47)

(48)

Because p0 = µ, from the definition of the expectation we have E [G(st−1 , st )] = H(S),  where H(S)  is from (19). From the definition of the Foster-Lyapunov function V in (5), we have E G(s′t−1 , st−1 ) = E [V (Zt−1 )]. Then the bound in (48) implies that   E G(s′t−1 , s′t ) ≤ E [V (Zt−1 )] + H(S) + E [G(st , s′t )] . (49) The term E [G(st , s′t )] is just the reverse distance of E [G(s′t , st )] = E [V (Zt )]. To bound E [G(st , s′t )] in terms of the Foster-Lyapunov function, we use the constant Kasym from (20) to write E [G(st , s′t )] ≤ Kasym E [V (Zt )] . Then (49) implies that   E G(s′t−1 , s′t ) ≤ E [V (Zt−1 )] + H(S) + Kasym E [V (Zt )] .

(50)

By virtue of the Markov chain M being ergodic, the Markov chain MZ is also ergodic, and thus the state distribution of MZ at time t, denoted pZ (t), converges to a stationary distribution µZ . Let Z∞ ∼ µZ denote a joint state drawn from this distribution, and define the expected steady-state shortest-path distance from s′t to st as V∞ = E [V (Z∞ )], where the expectation is taken over the randomness induced by the stationary distribution of MZ . An additional property of ergodicity is that the PMF over the states pZ (t) converges to the stationary distribution of the Markov chain MZ geometrically fast (Gallager, 2013, Theorem 4.3.5). As a result, the expectation of bounded, continuous functions of Zt converge to a steady-state value geometrically fast, including the shortest-path distance. For each time t, from the definition of geometric convergence we have E [V (Zt )] ≤ V∞ + ψ2t E [V (Z0 )] , (51) where the term ψ2t E [V (Z0 )] is the expected transient error at time t and ψ2 is the second largest eigenvalue modulus (SLEM) of the joint transition matrix PϵZ from (4). We can then compute E [V (Z0 )] directly as XX E [V (Z0 )] = p0 (x)p0 (y)G(x, y) = V̄0 . (52) x∈S y∈S

Substituting (52) and (51) into (50) gives E [V (Zt−1 )] + H(S) + Kasym E [V (Zt )] ≤ H(S) +



 1 + Kasym (V∞ + ψ2t V̄0 ). ψ2

(53)

Then using (47), (50), and (53), we find E [Hn (s′ )] ≤

    n 1 X 1 1 H(S) + + Kasym V∞ + + Kasym (ψ2t V̄0 ) n − 1 t=1 ψ2 ψ2     n 1 (1 + ψ2 Kasym ) V̄0 ≤ H(S) + + Kasym V∞ + , n−1 ψ2 (n − 1)(1 − ψ2 )

(54)

where the right-most term in (54) follows from the formula for a convergent infinite geometric series in ψ2 . 24

Now we bound V∞ . From the definition of the expectation V∞ = E[V (Z∞ )] we have Z ∞ P (V (Z∞ ) > v) dv. V∞ =

(55)

0

We split the integral in (55) into two regions: one where v ≤ Bϵ and the other where v > Bϵ . For v ≤ Bϵ , we note that V (Z∞ ) ∈ [0, Dmax ], where Dmax is the diameter of G. Thus, from Hoeffdings inequality, we have   2v 2 P (V (Z∞ ) > v) ≤ exp − 2 . (56) Dmax For v > Bϵ , we use (14) in Theorem 2, i.e.,  2γZattract (ϵ) P (V (Z∞ ) > v) ≤ C∞ exp − (v − Bϵ ) . DZattract (ϵ) 

(57)

Substituting (56) and (57) into (55) yields     Z ∞ 2γZattract (ϵ) 2v 2 V∞ ≤ (v − Bϵ ) dv exp − 2 dv + C∞ exp − Dmax DZattract (ϵ) 0 Bϵ r   √ DZattract (ϵ) π 2 erf Bϵ , = q + C∞ 2 Dmax 2γZattract (ϵ) 2 Dmax Z Bϵ

which we substitute into (54) to obtain E [Hn (s′ )] ≤     √ π n  1  q H(S) + + Kasym 2 n−1 ψ2 2

 r erf Bϵ

Dmax

2 Dmax



 DZattract (ϵ)  + (1 + ψ2 Kasym ) V̄0 , + C∞ 2γZattract (ϵ) (n − 1)(1 − ψ2 )

which completes the proof. E.7

Proof of Theorem 4

We begin by bounding how much the value of Hn (s′ ) =

n 1 X G(s′t−1 , s′t ) n − 1 t=1

may change when changing a single state in the trajectory s′ = s′0 s′1 · · · s′n . Let the state with the change be s′t for a fixed t ∈ [n]. Changing s′t may at most change G(s′t−1 , s′t ) by Dmax , where Dmax is the diameter of G from Definition 3. Similarly, changing s′t may also at most change G(s′t , s′t+1 ) by Dmax . Then, changing s′t ′ max changes Hn (s′ ) by at most 2D n−1 for each t ∈ {1, . . . , n − 1}. If t ∈ {0, n}, then st appears only in one value Dmax ′ ′ of G, and therefore Hn (s ) changes by at most n−1 for t ∈ {0, n}. Let s̃ be a state trajectory equal to s′ but with a change in a single state. Then Hn (s′ ) − H(s̃′ ) ≤

n−1 X Dmax X 2Dmax 1[s′i ̸= s̃′i ] + 1[s′i ̸= s̃′i ]. n−1 n − 1 i=1

(58)

i∈{0,n}

Let c=



 Dmax 2Dmax 2Dmax Dmax , ,··· , , . n−1 n−1 n−1 n−1 25

(59)

Then, for n ≥ 2 2

∥c∥2 =

n X

c2i = 2



i=0

Dmax n−1

2

+ (n − 2)

From (58) and (59), we have Hn (s′ ) − H(s̃′ ) ≤



n X

2Dmax n−1

2

=

2 (4n − 6)Dmax . 2 (n − 1)

(60)

ci 1[s′i ̸= s̃′i ].

(61)

i=0

As a result of (61), Lemma 3 implies that for any ν ∈ R we have P (Hn (s ) − E [Hn (s )] ≥ ν) ≤ exp ′

′

!

−2ν 2 2

9 ∥c∥2 tmix

,

where tmix is from (22). Substituting the upper bound on E [Hn (s′ )] from Theorem 3 yields !   n −2ν 2 ′ P Hn (s ) − H(S) ≥ ϕϵ + ν ≤ exp . 2 n−1 9 ∥c∥2 tmix

(62)

Substituting (60) into (62) yields     2ν 2 (n − 1)2 n ′ H(S) ≥ ϕϵ + ν ≤ exp − , P Hn (s ) − 2 n−1 9(4n − 6)Dmax tmix which completes the proof.

F

Additional Simulation Details

F.1

Data Pre-Processesing Table 1: Empirical 1-Year Transition Matrix for US Obligors. Terminal Rating Initial Rating

Aaa

Aa

A

Baa

Ba

B

Caa

Ca/C

Def

Aaa Aa A Baa Ba B Caa Ca/C Def

0.919 0.012 0.001 0 0 0 0 0 0

0.069 0.893 0.023 0.002 0.001 0.001 0 0 0

0.011 0.088 0.920 0.055 0.005 0.002 0 0 0

0 0.005 0.049 0.889 0.054 0.007 0.010 0 0

0.001 0.002 0.006 0.045 0.855 0.065 0.025 0.010 0

0 0 0.002 0.006 0.069 0.829 0.076 0.057 0

0 0 0 0.001 0.003 0.019 0.673 0.143 0

0 0 0 0 0 0.005 0.035 0.581 10−4

0 0 0 0.001 0.014 0.072 0.181 0.210 1−10−4

To compute the Markov chain model for the credit rating migration example, we take the transition probabilities from (Nickell et al., 2000, Table 3) from the Moody’s 1-year credit rating transition matrix, yielding a Markov chain with |S| = 9 states. Because the Markov chain in (Nickell et al., 2000, Table 3) is not irreducible, we include a small probability (10−4 ) of a firm recovering from default, which guarantees the Markov chain is irreducible for our analysis. Previous work on credit migration matrices shows that the default state being “absorbing” is unrealistic and harms analysis, which motivates our choice to include this probability (Jafry & Schuermann, 2004). The transition probabilities of the resulting Markov chain are shown in Table 1. Table 2 shows sample trajectories for ϵ ∈ {0.1, 1, 2, 5} for both Mechanism 1 and 26

Table 2: Sample private state trajectories for the credit migration example. Bold entries indicate a deviation from the sensitive state trajectory. ϵ

Mechanism

t=0

t=1

t=2

t=3

t=4

t=5

t=6

t=7

t=8

t=9

—

Sensitive

Caa

Ca/C

Caa

Caa

Caa

Caa

B

Caa

Ca/C

Ca/C

0.1

Chen et al. Mechanism 1

Caa Caa

Baa Def

Aa Ca/C

Aaa Caa

Aaa Ba

Aa Baa

Ba Caa

Aa Ca/C

A Caa

Aaa Def

1.0

Chen et al. Mechanism 1

Caa Caa

Caa Ca/C

Def Caa

Ca/C Caa

Caa Caa

Caa Def

B Ca/C

Ca/C Def

B Ca/C

Baa Ca/C

2.0

Chen et al. Mechanism 1

Caa Caa

Caa Ca/C

Caa Caa

Caa Ca/C

Caa Caa

Def Caa

Def B

Def Caa

Ca/C Ca/C

Ca/C Ca/C

5.0

Chen et al. Mechanism 1

Caa Caa

Ca/C Ca/C

Caa Caa

Caa Caa

Caa Caa

Caa Caa

B B

Caa Caa

Ca/C Ca/C

Ca/C Ca/C

Mechanism 2. The sensitive state trajectory is the credit rating of a European country over the past 10 years. To compute the Markov chain model for the Gainesville traffic example, we divide the roads around the University of Florida into segments, where a road segment is a section of road between two intersections. If a road does not extend past any intersections, it has only a single segment. Each of these segments is a state in the Markov chain, and the resulting Markov chain has |S| = 43 states. To compute the transition probabilities, we count the number of times drivers transitioned from one road segment to another, and we divide it by the total number of times drivers transitioned away from the first segment. Figure 5a shows the state space for the Markov chain, and the remainder of Figure 5 shows sample trajectories for varying levels of privacy. To develop the Markov chain model for the Wikispeedia example, we count the number of times users transitioned from one Wikipedia article to another, and we take the largest strongly connected subgraph of the resulting Markov chain, resulting in |S| = 3, 817. Figure 6 shows a visualization of the Wikispeedia dataset, and Figure 7 shows samples of private trajectories on this visualization. F.2

Additional Simulation Details

In this subsection, we state the simulation parameters used for Chen et al. (2023b), show single-sample results for all three simulation examples in Section 5 at ϵ = 1, and show figures showcasing the error probability results from Section 5.1 with varying values of ϵ. Additionally we include results on the size of the attractive set Zattract (ϵ). All simulation examples use b = 1 in Mechanism 2. This choice of b implies that only changing one state-tostate transition is protected by differential privacy. This is a strong privacy guarantee, and it is standard in the differential privacy literature. However, choosing ρ = 1 while using Mechanism 1 implies that changes in multiple state-to-state transitions are protected by differential privacy, which provides a stronger notion of privacy. For example, under Definition 4 the maximum number of state-to-state transitions that can change j k ρ between adjacent trajectories is mini,j∈S G(i,j) . In the credit migration example, we find that the maximum number of state-to-state transitions in which two trajectories can differ in this way is 11, implying that the privacy guarantee from Mechanism 1 at ρ = 1 is stronger than that of Mechanism 2 at b = 1. Figure 9 shows the fraction of the state space with negative drift for Mechanism 1 both empirically and according to Theorem 2 for ϵ ∈ {0.5, 1, . . . , 10} for all three examples. In all three examples, we find empirically that nearly the entire joint state space has negative drift. Theorem 2 gives a sufficient condition, and thus it provides a lower bound on the fraction of joint states with negative drift. However, in smaller Markov chains, such as the credit migration example, Theorem 2 predicts nearly 100% of the state space exhibits negative drift under Mechanism 1, which matches the empirical results. Figures 10 and 11 show the 27

Shortest-Path distance, V (Zt )

Chen et al. (ϵ = 1.0) Mechanism 1 (ϵ = 1.0)

8

10

6 4

5

2 0

0 20

40

60 Time, t

80

20

100

40

Shortest-Path distance, V (Zt )

(a)

60 Time, t

80

100

(b)

10

5

0 20

40

60 Time, t

80

100

(c) Figure 4: Single sample shortest-path distances from the private state s′t to the underlying sensitive state st for each t ∈ {0, 1, . . . , 100} for the (a) credit migration, (b) Gainesville traffic, and (c) Wikispeedia datasets. same scenario as Figures 2 and 3 in the case where the initial state distribution is the uniform distribution over the state space S. Those figures show similar results to the setting in Section 4 in which the initial distribution is the Dirac distribution, which shows that Mechanism 1 is robust to the use of arbitrary initial states.

28

SW 2nd Ave W University Ave (6 States)

SW 2nd Ave (4 States)

SW 4th Ave (1 State) SW Archer Rd (5 States)

SW Depot Ave (1 State)

SW 34th St (6 States)

SW 6th St (2 States)

SW 16th Ave (4 States) Old Archer Rd (2 States)

SW 23rd Ter (1 State) SW 13th St (4 States)

SW 35th Pl (1 State)

S Main St (3 States)

SW Williston Rd (3 States)

Sensitive Route Mechanism 1 Route Chen et al. 2023 Route

(b) ϵ = 1

(a)

Sensitive Route

Sensitive Route

Mechanism 1 Route

Mechanism 1 Route

Chen et al. 2023 Route

Chen et al. 2023 Route

(c) ϵ = 2

(d) ϵ = 5

Figure 5: A map of Gainesville streets and state names in (a), along with sample private state trajectories for varying levels of privacy in (b), (c), and (d). Even when Mechanism 1’s outputs deviate from the underlying sensitive state trajectory, the private state trajectories it generates bear more similarity to the sensitive state trajectory than those generated by Chen et al. (2023b).

29

IT

Religion Art

Mathematics

Language and literature Design and Technology

Citizenship

Everyday life Uncategorized

Science

Music

People

History

Business Studies

Geography

Countries

Figure 6: Map of Wikispeedia dataset with category names. The “Uncategorized” label only applies to a single article.

30

Mechanism 1 (Blue)

Chen et al. 2023 (Red)

(a) ϵ = 2

Mechanism 1 (Blue)

Chen et al. 2023 (Red)

(b) ϵ = 5

Figure 7: Sample state trajectories for varying levels of privacy, with the sensitive trajectory in gray. Even when Mechanism 1 is incorrect, the private state trajectories often return to their corresponding true trajectories, while the state trajectories generated by Mechanism 2 often do not.

31

Chen et al. (ϵ = 3.0)

100

100

10−1

10−1

10−2

10−2

10−3

10−4

10−3

10−4

10−4

10−5

10−5

10−5

10−6

10−6

10−6

10−1 P (V (Zt ) > v)

Mechanism 1 (ϵ = 3.0)

10−2 10−3

0

5 10 15 Error, v [nats]

0

0

5 10 15 Error, v [nats]

(a)

(b)

5 10 15 Error, v [nats] (c)

Figure 8: Probability of large errors in private trajectories in the (a) credit migration, (b) Gainesville traffic, and (c) Wikispeedia datasets. With a larger value of ϵ compared to Figure 2, in (b) Bϵ is small enough such that bound in Theorem 2 holds, and thus we see a linear relationship on the log-scale axes.

|Zcont (ϵ)|/|Z| × 100%

Mechanism 1

100% 80% 60% 40% 0

5 10 Privacy Strength, ϵ

Theorem 2

100%

100%

50%

50%

0%

0% 0

5 10 Privacy Strength, ϵ

(a)

(b)

0

5 10 Privacy Strength, ϵ (c)

Figure 9: Fraction of the joint state space with negative drift in the (a) credit migration, (b) Gainesville traffic, and (c) Wikispeedia examples. Because Theorem 2 gives a sufficient condition, in practice we find that more states have negative drift than is suggested by Theorem 2.

32

Chen et al. (ϵ = 1.0)

P (V (Zt ) > v)

100

10−1

10−2

10−3 0

Mechanism 1 (ϵ = 1.0)

100

100

10−1

10−1

10−2

10−2

10−3

10−3

10−4

10−4

10−5

10−5

10−6

10−6

5 10 15 20 Error, v [nats]

0

5 10 15 Error, v [nats]

(a)

0

(b)

5 10 15 Error, v [nats] (c)

Figure 10: Probability of large errors in private trajectories in the (a) credit migration, (b) Gainesville traffic, and (c) Wikispeedia datasets with p0 as the uniform distribution over all s ∈ S.

Chen et al. (ϵ = 1.0) Mechanism 1 (ϵ = 1.0)

Chen et al. (ϵ = 3.0) Mechanism 1 (ϵ = 3.0)

Chen et al. (ϵ = 5.0) Mechanism 1 (ϵ = 5.0)

True Entropy Rate H(X ) True Process ±2σ

E [Hn (s′ )]

1.6 1.4

2

1.2 1

0

0.8 40 60 80 Trajectory Length, n (a)

E [Hn (s′ )]

20

100

20

40 60 80 Trajectory Length, n (b)

100

4 3 2 20

40 60 80 Trajectory Length, n (c)

100

Figure 11: Empirical entropy with varying ϵ and trajectory length in the (a) credit migration, (b) Gainesville traffic, and (c) Wikispeedia examples with p0 as the uniform distribution over all s ∈ S.

33

Related documents

• Context-Aware Metric Differential Privacy for Vehicle Trajectory Data#229446
• Differentially Private Sampling from Distributions via Wasserstein Projection#175142
• Online Differentially Private Consistent Clustering#618519
• Privacy Amplification Without Independence: How Far Negative Dependence Carries the Guarantees of Poisson Subsampling#822359
• The Fast Mixing Mechanism for Differential Privacy#652332