  Various modern and highly popular applications make use of user data traces
in order to offer specific services, often for the purpose of improving the
user's experience while using such applications. However, even when user data
is privatized by employing privacy-preserving mechanisms (PPM), users' privacy
may still be compromised by an external party who leverages statistical
matching methods to match users' traces with their previous activities. In this
paper, we obtain the theoretical bounds on user privacy for situations in which
user traces are matchable to sequences of prior behavior, despite anonymization
of data time series. We provide both achievability and converse results for the
case where the data trace of each user consists of independent and identically
distributed (i.i.d.) random samples drawn from a multinomial distribution, as
well as the case that the users' data points are dependent over time and the
data trace of each user is governed by a Markov chain model.
