Entropy of Conditional Markov Trajectories

Mohamed Kafsi, Matthias Grossglauser, Patrick Thiran

Abstract

To quantify the randomness of Markov trajectories with fixed initial and final states, Ekroot and Cover proposed a closed-form expression for the entropy of trajectories of an irreducible finite state Markov chain. Numerous applications, including the study of random walks on graphs, require the computation of the entropy of Markov trajectories conditioned on a set of intermediate states. However, the expression of Ekroot and Cover does not allow for computing this quantity. In this paper, we propose a method to compute the entropy of conditional Markov trajectories through a transformation of the original Markov chain into a Markov chain that exhibits the desired conditional distribution of trajectories. Moreover, we express the entropy of Markov trajectories - a global quantity - as a linear combination of local entropies associated with the Markov chain states.

Introduction

In information theory, quantifying the randomness of a sequence is typically achieved using the entropy rate. However, many real-world applications—such as modeling a traveler's route on a map or a molecule's path in a physical system—focus on a specific trajectory with a fixed starting point ($s$) and destination ($d$).

While previous work by Ekroot and Cover (1993) provided a way to calculate the entropy of such trajectories for irreducible Markov chains, their method failed in two common scenarios: when side information is available (e.g., knowing the trajectory passed through specific intermediate points) and when the chain is non-irreducible (where constraints prevent certain states from reaching the destination). This paper addresses these gaps by providing a tool to measure the uncertainty remaining about a path once partial observations are made.

Methodology

The authors' approach relies on two main pillars: matrix transformation and the fundamental matrix of Markov chains.

To handle conditioning, the original transition matrix $P$ is transformed into a new matrix $P'$. This new matrix is constructed such that it only allows trajectories that satisfy the given conditions, effectively turning a conditional probability problem into a standard trajectory entropy problem on a modified graph.

Furthermore, the authors prove that the entropy of a trajectory $H_{sd}$ is equal to $\sum_{k \neq d} \mathbb{E}[V_k] H(P_{k.})$, where $\mathbb{E}[V_k]$ is the expected number of times the process visits state $k$ before hitting the destination, and $H(P_{k.})$ is the local entropy (uncertainty of the next step) at state $k$. The values for $\mathbb{E}[V_k]$ are derived from the "fundamental matrix" $(I - Q)^{-1}$, a standard tool in Markov chain theory.

Algorithm for computing the entropy of a Markov trajectory conditioned on a sequence of intermediate states.

The resulting algorithm, detailed above, has a computational complexity of $O(lN^3)$, where $l$ is the number of intermediate states and $N$ is the number of states in the system.

Key Insights and Results

A striking finding of this research is that the total entropy of a path is simply the sum of local uncertainties, weighted by how often those states are expected to be encountered. This provides an intuitive bridge between local transition rules and global path behavior.

The authors also identify a "Sequence vs. Set" paradox: conditioning on a specific sequence of states (e.g., "went to A then B") can actually result in higher entropy than conditioning on the set of those same states ("went to A and B in any order"). This happens because a specific sequence might force the trajectory into a high-entropy "detour" that it would otherwise avoid.

A 5-state Markov chain used to validate the proposed entropy calculations.

Validation was performed using synthetic Markov chains, such as the 5-state model shown above. Unlike previous methods, this approach only requires that the destination $d$ is reachable from the starting point $s$ within the allowed transitions, relaxing the strict requirement for irreducibility.

Applications and Future Work

This work has significant implications for mobility privacy. By calculating the conditional entropy, researchers can measure exactly how much "predictability" a user loses as they reveal more of their location history.

However, limitations remain for massive graphs (millions of nodes), where the $O(N^3)$ complexity may become a bottleneck. Additionally, calculating entropy conditional on an unordered set of visited states remains a harder problem, as it involves accounting for all possible permutations of those visits. Future research will also explore non-Markovian behaviors, as real-world human mobility often exhibits higher-order dependencies.

Summary updated

Abstract

To quantify the randomness of Markov trajectories with fixed initial and final states, Ekroot and Cover proposed a closed-form expression for the entropy of trajectories of an irreducible finite state Markov chain. Numerous applications, including the study of random walks on graphs, require the computation of the entropy of Markov trajectories conditioned on a set of intermediate states. However, the expression of Ekroot and Cover does not allow for computing this quantity. In this paper, we propose a method to compute the entropy of conditional Markov trajectories through a transformation of the original Markov chain into a Markov chain that exhibits the desired conditional distribution of trajectories. Moreover, we express the entropy of Markov trajectories - a global quantity - as a linear combination of local entropies associated with the Markov chain states.
BibTeX
@article{kafsi2013entropy,
  author = {Mohamed Kafsi and Matthias Grossglauser and Patrick Thiran},
  title = {{Entropy of Conditional Markov Trajectories}},
  journal = {IEEE Trans. Information Theory},
  year = {2013},
  url = {https://openreview.net/forum?id=hBP9sgyX7T},
}
Figure