text:
\section{Framework}
\label{sec:framework}
Here, we employ a similar framework to~\cite{tifs2016,nazanin_ISIT2017}. The system has $n$ users, and $X_u(k)$ is  user $u$'s data at time $k$. Our main goal is protecting $X_u(k)$ from a strong adversary $(\mathcal{A})$ who has full knowledge of the (unique) marginal probability distribution function of the data samples of each user based on previous observations or other sources. In order to achieve data privacy for users, both anonymization and obfuscation techniques can be used as shown in Figure \ref{fig:xyz}. In Figure \ref{fig:xyz}, $Z_u(k)$ shows the (reported) sample of the data of user $u$ at time $k$ after applying obfuscation, and $Y_u(k)$ shows the (reported) sample of the data of user $u$ at time $k$ after applying anonymization. Let $m=m(n)$ be the number of data points after which the pseudonyms of users are changed using anonymization. To break anonymization, the adversary tries to estimate $X_u(k)$, $k=1, 2, \cdots, m$, from $m$ observations per user by matching the sequence of observations to the known statistical characteristics of the users.

\begin{figure}[h]
	\centering
	\includegraphics[width = 0.7\linewidth]{fig/xyz}
	\caption{Applying obfuscation and anonymization techniques to users' data samples.}
	\label{fig:xyz}
\end{figure}

Let $\textbf{X}_u$ be the $m \times 1$ vector containing the samples of the data of user $u$, and $\textbf{X}$ be the $m \times n$ matrix with the $u^{th}$ column equal to $\textbf{X}_u$:
\[\textbf{X}_u = \begin{bmatrix}
X_u(1) \\ X_u(2) \\ \vdots \\X_u(m) \end{bmatrix} , \ \ \  \textbf{X} =\left[\textbf{X}_{1}\ \  \textbf{X}_{2}\ \  \cdots \ \ \textbf{X}_{n}\right].
\]

\textit{Data Samples Model:}
We assume users' data points can have one of $r$ possible values $(0, 1, \cdots, r-1)$. Thus, according to a user-specific probability distribution, $X_u(k)$ is equal to a value in $\left\{0,1, \cdots, r-1 \right\}$ at any time, and, per above, these user-specific probability distributions are known to the adversary $(\mathcal{A})$ and form the basis upon which she performs (statistical) matching.

\textit{Association Graph:}
An association graph or dependency graph is an undirected graph representing dependencies of the data of users with each other. Let $G(\mathcal{V},F)$ denote the association graph with set of nodes $\mathcal{V}$, $(|\mathcal{V}|=n)$, and set of edges $F$. Two vertices (users) are connected if their data sets are dependent. More specifically,
\begin{itemize}
	\item $(u,u') \in F$ iff $I(X_u(k); X_{u'}(k))>0,$ for $\forall k$,
	\item $(u,u') \notin F$ iff $I (X_u(k);X_{u'}(k))=0,$ for $\forall k$,
\end{itemize}
where $I\left(X_u(k); X_{u'}(k)\right)$ is the mutual information between the $k^{th}$ data sample of user $u$ and user $u'$. Note that, because we assume statistical stationarity in this paper, positive mutual information for one $k$ means positive information for all $k$'s.

\textit{Obfuscation Model:} Obfuscation perturbs the users' data samples \cite{shokri2012protecting, gruteser2003anonymous, bordenabe2014optimal}. Normally, in such settings, each user has only limited knowledge of the characteristics of the overall population. Thus, usually, a simple distributed method in which the samples of the data of each user are reported with error with a certain probability is employed \cite{randomizedresponse}. Note that this probability itself is generated randomly for each user.  Let $\textbf{Z}_u$ be the vector that contains

the obfuscated version of user $u$'s data samples, and ${\textbf{Z}}$ be the collection of ${\textbf{Z}}_u$ for all users,
\[{\textbf{Z}}_u = \begin{bmatrix}
{Z}_u(1) \\ {Z}_u(2) \\ \vdots \\ {Z}_u(m) \end{bmatrix} , \ \ \  {\textbf{Z}} =\left[ {\textbf{Z}}_{1} \ \ {\textbf{Z}}_{2}\ \ \cdots \ \  {\textbf{Z}}_{n}\right].
\]

Here we define the \emph{asymptotic noise level} for an obfuscation technique. Loosely speaking, the asymptotic noise level of obfuscation is the highest probable percentage of data points that are corrupted. More precisely,
for a subset of users $\bm{\mathfrak{U}}$, let $X_u(k)$ be the actual sample of the data of user $u$ at time $k$, $u \in \bm{\mathfrak{U}}$, $k \in \{1, 2, \cdots, m\}$ and let ${Z}_u(k)$ be the obfuscated (noisy) version of $X_u(k)$. Define
 \[A_m(u) = \frac{\abs*{\left\{k:{Z}_u(k) \neq X_u(k)\right\}}}{m}.\]
 Then, the asymptotic noise level for user $u$ is defined as follows:
 \[a (u)=\inf \bigg\{ a \geq 0: P(A_m(u)>a) \rightarrow 0 \text{ as }  m \rightarrow \infty\bigg\}.\]

 Also define
 \[A_m= \frac{\sum\limits_{u \in \bm{\mathfrak{U}}} \abs*{\left\{k:{Z}_u(k) \neq X_u(k)\right\}}}{m|\bm{\mathfrak{U}}|},\]
 then the asymptotic noise level for the entire dataset is
 \[a =\inf \bigg\{ a \geq 0: P(A_m>a) \rightarrow 0 \text{ as }  m \rightarrow \infty\bigg\}.\]
 Note that while the above definition is given for a general case required in Section \ref{perfect}, in practice we often use simple obfuscation techniques that employ i.i.d.\ noise sequences. Then, by the Strong Law of Large Number (SLLN),
 \[\frac{\abs*{\left\{k:{Z}_u(k) \neq X_u(k)\right\}}}{m} \xrightarrow{\text{a.s.}} P\left({Z}_u(k) \neq X_u(k)\right),\]
and for any $k$,
\[a(u)=P\left({Z}_u(k) \neq X_u(k)\right).\]

\textit{Anonymization Model:} In the anonymization technique, the identity of the users is perturbed \cite{1corser2016evaluating,hoh2005protecting,freudiger2007mix, ma2009location, shokri2011quantifying2, Naini2016,soltani2017towards, soltani2018invisible}. Anonymization is modeled by a random permutation $\Pi$ on the set of $n$ users. Let ${\textbf{Y}}_u$ be the vector which contains the anonymized version of ${\textbf{Z}}_u$, and ${\textbf{Y}}$ is the collection of ${\textbf{Y}}_u$ for all users, thus
\begin{align}
\no {\textbf{Y}} &=\textrm{Perm}\left({\textbf{Z}}_{1}, {\textbf{Z}}_{2}, \cdots,  {\textbf{Z}}_{n}; \Pi \right) \\
\nonumber &=\left[ {\textbf{Z}}_{\Pi^{-1}(1)} \ \ {\textbf{Z}}_{\Pi^{-1}(2)}\ \ \cdots \ \  {\textbf{Z}}_{\Pi^{-1}(n)}\right ] \\
\nonumber &=\left[ {\textbf{Y}}_{1}\ \ {\textbf{Y}}_{2}\ \ \cdots \ \ {\textbf{Y}}_{n}\right], \ \
\end{align}
where $\textrm{Perm}( \ . \ , \Pi)$ is permutation operation with permutation function $\Pi$. As a result, ${\textbf{Y}}_{u} = {\textbf{Z}}_{\Pi^{-1}(u)}$ and ${\textbf{Y}}_{\Pi(u)} = {\textbf{Z}}_{u}$.

\textit{Adversary Model:} We assume the adversary has full knowledge of the marginal probability distribution function of each of the users on $\{0,1,\ldots,r-1\}$. As discussed in the data samples models in succeeding sections, the parameters $p_u$, $u=1, 2, \cdots, n$ are drawn independently from a continuous density function, $f_{\textbf{P}}(\textbf{p}_u)$, which
has support on a subset of a given hypercube. The density $f_{\textbf{P}}(\textbf{p}_u)$ might be unknown to the
adversary, so all that is assumed here is that such a density exists. From the results of the paper, it will be evident that knowing or not knowing $f_{\textbf{P}}(\textbf{p}_u)$ does not change the results asymptotically.

 The adversary knows the anonymization mechanism but does not know the realization of the random permutation. The adversary also knows the obfuscation mechanism but does not know the realization of the noise parameters. And finally, the adversary knows the association graph $G(\mathcal{V},F)$, but does not necessarily know the exact nature of the dependency. That is, while the adversary knows the marginal distributions $X_u(k)$ as well as which pairs of users have strictly positive mutual information, he might not know the joint distributions or even the values of the mutual information $I(X_u(k); X_{u'}(k))$.

It is critical to note that the adversary does not have any auxiliary information or side information about users' data.

We adapt the definitions of perfect privacy and no privacy from \cite{tifs2016,nazanin_ISIT2017}:

\begin{define}
	User $u$ has \emph{perfect privacy} at time $k$ if and only if
	\begin{align}
		\no  \forall k\in \mathbb{N}, \ \ \ \lim\limits_{n\rightarrow \infty} I \left(X_u(k);{\mathbf{Y}}\right) =0,
	\end{align}
	where $I\left(X_u(k);{\textbf{Y}}\right)$ denotes the mutual information between a sample of the data of user $u$ at time $k$ and the collection of the adversary's observations for all the users.
\end{define}

\begin{define}
For an algorithm for the adversary that tries to estimate the actual sample of data of user $u$ at time $k$, define
\[P_e(u,k)\triangleq P\left(\widetilde{X_u(k)} \neq X_u(k)\right),\]
where $X_u(k)$ is the actual sample of the data of user $u$ at time $k$, $\widetilde{X_u(k)}$ is the adversary's estimated sample of the data of user $u$ at time $k$, and $P_e(u,k)$ is the error probability. Now, define ${\cal E}$ as the set of all possible adversary's estimators; then, user $u$ has \emph{no privacy} at time $k$, if and only if as $n \rightarrow \infty$,
\[
\forall k\in \mathbb{N}, \ \ \ P^{*}_e(u,k)\triangleq \inf_{\cal E} {P\left(\widetilde{X_u(k)} \neq X_u(k)\right)} \rightarrow 0.
\]
Hence, a user has \emph{no privacy} if there exists an algorithm for the adversary to estimate $X_u(k)$ with diminishing error probability as $n$ goes to infinity.
\end{define}

\textbf{\textit{Discussion:}} Both of the privacy definitions given above (perfect privacy and no privacy) are asymptotic in the number of users $(n \to \infty)$, which allows us to find clean analytical results for the fundamental limits. Moreover, in many IoT applications, such as ride sharing and dining recommendation applications, the number of users is large.

\textbf{\textit{Notation:}} Note that the sample of data of user $u$ at time $k$ after applying obfuscation $\left(Z_u(k)\right)$ and the sample of data of user $u$ at time $k$ after applying anonymization $\left(Y_u(k)\right)$ depend on the number of users in the setting $(n)$, while the actual sample of data of user $u$ at time $k$ is independent of the number of users $(n)$.  Despite the dependency in the former cases, we omit this subscript $(n)$ on $\left(Z_u^{(n)}(k), Y_u^{(n)}(k) \right)$ to avoid confusion and make the notations consistent.

\section{Impact of Correlation on Privacy Using Anonymization}
\label{anon}

In this section, we consider only anonymization and thus the obfuscation block in Figure \ref{fig:xyz} is not present. In this cases, the adversary's observation ${\textbf{Y}}$  is the anonymized version of $\textbf{X}$; thus
\begin{align}
\no {\textbf{Y}} &=\textrm{Perm}\left(\textbf{X}_{1}, \textbf{X}_{2}, \cdots,  \textbf{X}_{n}; \Pi \right) \\
\nonumber &=\left[ \textbf{X}_{\Pi^{-1}(1)}\ \ \textbf{X}_{\Pi^{-1}(2)}\ \ \cdots \ \  \textbf{X}_{\Pi^{-1}(n)}\right ] \\
\nonumber &=\left[ {\textbf{Y}}_{1}\ \ {\textbf{Y}}_{2}\ \ \cdots\ \ {\textbf{Y}}_{n}\right]. \ \
\end{align}

\subsection{i.i.d.\ Two-States  Model}
\label{iidtwo}

There is potentially dependency between the data of different users, but we assume here that the sequence of data for any individual user is i.i.d.\  We first consider the i.i.d.\ two-states $(r=2)$ case, where the sample of the data of user $u$ at any time is a Bernoulli random variable with parameter $p_u$, which we define as the probability of user $u$ being at state $1$. Thus, \[X_u(k) \sim Bernoulli \left(p_u\right).\]
The parameters $p_u$, $u=1, 2, \cdots, n$ are drawn independently from a continuous density function, $f_P(p_u)$, on the $(0,1)$ interval. Further, we assume there are $\delta_1, \delta_2>0$ such that\footnote{The condition $\delta_1<f_P(p_u) <\delta_2$ is not actually necessary for the results and can be relaxed; however, we keep it here to avoid unnecessary technicalities.}:
\begin{equation}
\no\begin{cases}
    \delta_1\leq f_P(p_u) \leq\delta_2, & p_u \in (0,1).\\
    f_P(p_u)=0, &  p _u\notin (0,1).
\end{cases}
\end{equation}

The adversary knows the values of $p_u$, $u=1, 2, \cdots, n$, and uses this knowledge to match the observed traces to the users. We will use capital letters (i.e., $P_u$) when we are referring to the random variable, and use lower case (i.e., $p_u$) to refer to the realization of $P_u$.

A vector containing the permutation of those probabilities after anonymization is
\begin{align}
\no \textbf{V} &=\textrm{Perm}\left({P}_{1}, {P}_{2}, \cdots,  {P}_{n}; \Pi \right) \\
\nonumber &=\left[ {P}_{\Pi^{-1}(1)}\ \ {P}_{\Pi^{-1}(2)}\ \ \cdots\ \ {P}_{\Pi^{-1}(n)}\right ] \\
\nonumber &=\left[V_{1}\ \ V_{2}\ \ \cdots\ \ V_{n}\right ], \ \
\end{align}
where $V_{u} = {{P}}_{\Pi^{-1}(u)}$ and  $V_{\Pi(u)} = {{P}}_{u}$. As a result, for $u=1,2,..., n$, the distribution of the data symbols for the user with pseudonym $u$ is given by:
\[ {Y}_u(k) \sim Bernoulli \left(V_u\right) \sim Bernoulli\left(P_{\Pi^{-1}(u)}\right)  .\]

In this case, dependency and correlation of the data samples are equivalent, that is, we can say:
\begin{itemize}
	\item $(u,u') \in F$ iff $\rho \left(X_u(k),X_{u'}(k)\right)=\rho_{uu'}>0,$ for $\forall k$,
	\item $(u,u') \notin F$ iff $\rho \left(X_u(k),X_{u'}(k)\right)=\rho_{uu'}=0,$ for $\forall k$,
\end{itemize}
where $\rho_{uu'}$ is the correlation coefficient between the data of user $u$ and that of user $u'$. The adversary knows the association graph $G(\mathcal{V},F)$, but does not necessarily know the correlation coefficient $(\rho_{uu'})$ for each specific $(u,u') \in F$.

Critical to compromising the privacy of the users will be the adversary's ability to match empirical correlation properties of the data traces to the known structure of the (ensemble) correlation between users.  First, we show that the adversary can reliably reconstruct the entire association graph for \textit{the anonymized version of the data} (i.e., the observed data traces) with relatively few observations.

\begin{lem}
	\label{lem1}
	Consider a general association graph $G(\mathcal{V},F)$. If the adversary obtains $m=(\log n)^3$ anonymized observations per user, he/she can construct $\widetilde{G}=\widetilde{G}(\widetilde{\mathcal{V}}, \widetilde{F})$, where $\widetilde{\mathcal{V}}=\{\Pi(u):u \in \mathcal{V}\}=\mathcal{V}$, such that with high probability, for all $u, u' \in \mathcal{V}$; $ (u,u')\in F$ iff  $\left(\Pi(u),\Pi(u')\right)\in \widetilde{F}$. We write this statement as $P(\widetilde{F}=F)\rightarrow 1$.
\end{lem}

\begin{proof}
We provide an algorithm for the adversary that with high probability obtains all edges of $F$ correctly. For each pair $u$ and $u'$, compute
\begin{align}
\nonumber\widetilde{Cov_{uu'}}&=\frac{M_{uu'}}{m}-\frac{M_{u}}{m}\frac{M_{u'}}{m}\\
&=\frac{mM_{uu'}-M_uM_{u'}}{m^2},
\label{cov}
\end{align}
where
\[M_{uu'}= \abs*{\left\{k: X_u(k)=1, X_{u'}(k)=1\right\}}.\]
\[M_{u}= \abs*{\left\{k: X_u(k)=1\right\}}.\]
\[M_{u'}= \abs*{\left\{k: X_{u'}(k)=1\right\}}.\]
Then:
\begin{itemize}
	\item If $|\widetilde{Cov_{uu'}}|<{m^{-\frac{1}{5}}}$, then $(u,u')\notin \widetilde{F}.$
	\item If $|\widetilde{Cov_{uu'}}|>{m^{-\frac{1}{5}}}$, then $(u,u')\in \widetilde{F}.$
\end{itemize}
We show the above method yields $P(\widetilde{F}=F)\rightarrow 1$ as $n \rightarrow \infty$, as follows.
Note
 \[M_{uu'} \sim \text{Binomial } (m, p_{uu'}),\] \[M_{u} \sim \text{Binomial } (m, p_{u}),\] \[M_{u'} \sim \text{Binomial } (m, p_{u'}),\]
then by using the Chernoff bound, for any $\zeta>0$, we have
\begin{align}
\no P\left(\bigg{|}\frac{M_{uu'}}{m}-p_{uu'}\bigg{|}\geq\zeta\right)\leq 2e^{-\frac{m\zeta^2}{3p_{uu'}}}.\ \
\end{align}
Now, let $\zeta=m^{-\frac{1}{4}}$. Define
\[ P(\mathcal{J}_{uu'})=P\left(\bigg{|}\frac{M_{uu'}}{m}-p_{uu'}\bigg{|}\geq m^{-\frac{1}{4}}\right),\]
so we have
\begin{align}
\no P(\mathcal{J}_{uu'})&\leq 2e^{-\frac{\sqrt{m}}{3p_{uu'}}}\\
\no &\leq 2e^{-\frac{\sqrt{m}}{3}}.
\end{align}

Similarly, define
\[ P(\mathcal{J}_{u})=P\left(\bigg{|}\frac{M_{u}}{m}-p_{u}\bigg{|}\geq m^{-\frac{1}{4}}\right),\]
\[P(\mathcal{J}_{u'})=P\left(\bigg{|}\frac{M_{u'}}{m}-p_{u'}\bigg{|}\geq m^{-\frac{1}{4}}\right),\]
so we have
\begin{align}
\no P(\mathcal{J}_{u}) \leq 2e^{-\frac{\sqrt{m}}{3}}.\ \
\end{align}
\begin{align}
\no P(\mathcal{J}_{u'})\leq 2e^{-\frac{\sqrt{m}}{3}}.\ \
\end{align}

Now, by using a union bound, we have
\begin{align}
\no P\left(\mathcal{J}_{uu'} \cup \mathcal{J}_{u} \cup \mathcal{J}_{u'} \right)\leq 2\left(e^{-\frac{\sqrt{m}}{3}}+e^{-\frac{\sqrt{m}}{3}}+e^{-\frac{\sqrt{m}}{3}}\right).\ \
\end{align}
Then by employing a union bound again,
\begin{align}
\no \bigcup\limits_{u=1}^n \bigcup\limits_{u'=1}^n P\left(\mathcal{J}_{uu'} \cup \mathcal{J}_{u} \cup \mathcal{J}_{u'}\right) &\leq \sum\limits_{u=1}^n  \sum\limits_{u'=1}^n2\left(e^{-\frac{\sqrt{m}}{3}}+e^{-\frac{\sqrt{m}}{3}}+e^{-\frac{\sqrt{m}}{3}}\right)\\
\no & \leq 2n^2\left(3e^{-\frac{\sqrt{m}}{3}}\right)
\\
\no &= 6\exp\left\{2 \log n-\frac{(\log n)^{\frac{3}{2}}}{3}\right\}\rightarrow 0.\ \
\end{align}
Thus, with high probability, for all $u,u' \in \{1,2,\cdots, n\}$, we have
\[0\leq mp_{uu'}-m^{\frac{3}{4}} \leq  M_{uu'} \leq mp_{uu'}+m^{\frac{3}{4}}.\]
\[0\leq mp_u-m^{\frac{3}{4}} \leq  M_u \leq mp_u+m^{\frac{3}{4}}.\]
\[0\leq mp_{u'}-m^{\frac{3}{4}} \leq  M_{u'} \leq mp_{u'}+m^{\frac{3}{4}}.\]
As a result, by using (\ref{cov}),
\begin{align}
\no \widetilde{Cov_{uu'}}=\frac{mM_{uu'}-M_uM_{u'}}{m^2}&\leq \frac{m(mp_{uu'}+m^{\frac{3}{4}})-(mp_{u}-m^{\frac{3}{4}})(mp_{u'}-m^{\frac{3}{4}})}{m^2}\\
\no&= p_{uu'}+m^{-\frac{1}{4}}-(p_u-m^{-\frac{1}{4}})(p_{u'}-m^{-\frac{1}{4}})\\
\no &=p_{uu'}-p_up_{u'}+m^{-\frac{1}{4}}+(p_u+p_{u'})m^{-\frac{1}{4}}-m^{-\frac{1}{2}}\\
\no &= p_{uu'}-p_up_{u'}+O(m^{-\frac{1}{4}}).\ \
\end{align}
Similarly,
\begin{align}
\no \widetilde{Cov_{uu'}}=\frac{mM_{uu'}-M_uM_{u'}}{m^2}&\geq \frac{m(mp_{uu'}-m^{\frac{3}{4}})-(mp_{u}+m^{\frac{3}{4}})(mp_{u'}+m^{\frac{3}{4}})}{m^2}\\
\no &=p_{uu'}-p_up_{u'}-m^{-\frac{1}{4}}-(p_u+p_{u'})m^{-\frac{1}{4}}-m^{-\frac{1}{2}}\\
\no &=p_{uu'}-p_up_{u'}-O(m^{-\frac{1}{4}}).\ \
\end{align}

For $(u,u') \notin F$, we have $\rho_{uu'}=0$, and as a result, $p_{uu'}-p_up_{u'}=0$. Thus, with high probability,
\begin{align}
\no |\widetilde{Cov_{uu'}}|\leq O(m^{-\frac{1}{4}}), \ \ \ \textrm{for all }u,u' \in \{1,2,\cdots, n\}.\ \
\end{align}
Then, as $n \rightarrow \infty$,
\begin{align}
\no P(|\widetilde{Cov_{uu'}}|\geq m^{-\frac{1}{5}})\rightarrow 0.
\end{align}

Similarly, for $(u,u') \in F$, we have $\rho_{uu'}>0$, thus
\begin{align}
\no |\widetilde{Cov_{uu'}}|\geq  \rho_{uu'}\sqrt{p_up_{u'}(1-p_u)(1-p_{u'})}-O(m^{-\frac{1}{4}}),  \  \rho_{uu'}\sqrt{p_up_{u'}(1-p_u)(1-p_{u'})}>0,\ \
\end{align}
and as a result, as $n \rightarrow \infty,$
\begin{align}
\no P(|\widetilde{Cov_{uu'}}|\geq m^{-\frac{1}{5}})\rightarrow 1.
\end{align}

Thus, for large enough $n$, we have $P\left(\widetilde{F}=F\right)\rightarrow 1$, so the adversary can reconstruct the association graph for the anonymized version of data with small error probability. Note that reconstruction of the association graph does not require the adversary's knowledge about user statistics (i.e., the values of $p_u$'s).
\end{proof}

The structure of the association graph $(G)$ can leak a lot of information.  For example, in Figure \ref{fig:identity}, the identity map is the only automorphism of the association graph $G$.  Thus, it is obvious that the adversary can uniquely identify all of the users if he/she can reconstruct the association graph $\widetilde{G}$ of the anonymized data.

To be able to derive further results, we need to make some assumptions on the structure of the association graph. For the rest of the paper, we consider a graph structure shown in Figure \ref{fig:graph}, where the association graph consists of $f$ disjoint subgraphs,
\[G=G_1 \cup G_2 \cup \cdots \cup  G_f,\]
where subgraph $G_j$ is a connected graph on $s_j$ vertices. In particular, each subgraph $G_j$ can be thought of as a group of ``friends'' or ``associates'' such that their data sets are dependent. So, we can write $G_j(\mathcal{V}_j, F_j)$, where $|\mathcal{V}_j|=s_j$. Note that, we assume $s_j$'s are finite.

\begin{figure}
	\centering
	\includegraphics[width=.4\linewidth]{fig/identity.jpg}
	\centering
	\caption{One example of an association graph for which the identity map is the only automorphism.}
	\label{fig:identity}
\end{figure}

\begin{figure}
	\centering
	\includegraphics[width=.5\linewidth]{fig/graph.jpg}
	\centering
	\caption{The association graph $G$ consists of a collection of disjoint subgraphs $(G_j)$, where $G_j$ is a connected graph on $s_j$ vertices.}
	\label{fig:graph}
\end{figure}

The following theorem states that if the number of observations per user $(m)$ is significantly larger than $n^{\frac{2}{s}} $ in this two-states model, where $s$ is the size of the group that the user belongs to, then the adversary can successfully de-anonymize the users in that group.

\begin{thm}\label{two_state_thm}
For the above two-states model, if ${\textbf{Y}}$ is the anonymized version of $\textbf{X}$  as defined above, the size of the group including user $1$ is $s$, and
\begin{itemize}
	\item $m=cn^{\frac{2}{s}+\alpha}$, for any $\alpha > 0$;
\end{itemize}
then user $1$ has no privacy for large enough $n$.
\end{thm}

\textit{Discussion}:
It is insightful to compare this result to Theorem 1 in \cite{tifs2016}, where it is stated that if the users are not correlated, then all users have perfect privacy as long as the number of adversary's observations per user $(m)$ is smaller than $O(n^2)$. Here, Theorem \ref{two_state_thm} states that with much smaller $m$ the adversary can de-anonymize the users. Therefore, we see that dependency can significantly reduce the privacy of users.

\noindent \textbf{Proof of Theorem \ref{two_state_thm}:}
\begin{proof}
The proof of Theorem \ref{two_state_thm} consists of three parts:
\begin{enumerate}
\item Showing the adversary can reconstruct the association graph of the anonymized version of data with small error probability.
\item Showing the adversary can uniquely identify group $1$ with small error probability.
\item Showing the adversary can individually identify all the members within group $1$.
\end{enumerate}

For the first part of the proof, we use Lemma \ref{lem1}, which states the adversary can reconstruct the entire association graph with arbitrary small error probability if the number of the adversary's observations per user $(m)$ is bigger than $(\log n)^3$. More specifically, since $n^{\frac{2}{s}}>(\log n)^3$, we can use Lemma \ref{lem1}, to conclude that the adversary can reconstruct the association graph with small error probability. Note that for the second and third part of the proof, we use $m=n^{\frac{2}{s}+\alpha}$ which is defined in the statement of Theorem \ref{two_state_thm}.

Now, assume the size of group $1$ is $s$. Without loss of generality, suppose the members of group $1$ are users $\{1,2, \cdots , s\}$. Note that there are at most $\frac{n}{s}$ groups of size $s$. We call these groups $1, 2, \cdots, \frac{n}{s}$. The adversary needs to first identify group $1$ among all of these groups.

First, for $u=1, 2, \cdots, s$, the adversary computes $\widetilde{p_u}$ as follow:
\begin{align}
\widetilde{p_{u}}=\frac{\sum\limits_{k=1}^mY_u(k)}{m},\ \
\label{p-tilde}
\end{align}
as a result,
\begin{align}
\widetilde{p_{\Pi(u)}}=\frac{\sum\limits_{k=1}^mX_u(k)}{m}=\frac{M_{u}}{m},\ \
\label{p-tilde2}
\end{align}
where $M_{u}= \abs*{\left\{k: X_u(k)=1\right\}}.$

Define $\Sigma_s$ as the set of all permutations on $s$ elements; for $\sigma \in \Sigma_s$, $\sigma :\{1, 2, \cdots, s\}\rightarrow \{1, 2, \cdots, s\}$ is a one-to-one mapping.

Now let $\mathbf{\Phi},\mathbf{\Psi} \in\mathbb{R}^s$,
\[\mathbf{\Phi}=[\Phi_1\ \ \Phi_2 \ \ \cdots\ \ \Phi_s].\]
\[\mathbf{\Psi}=[\Psi_1\ \ \Psi_2 \ \ \cdots \ \ \Psi_s].\]
Consider the  ${L-}$ infinity norm of the difference of these two sets:
{\begin{align}
\nonumber ||\mathbf{\Phi}-\mathbf{\Psi}_{\sigma}||_{\infty}=\max\left\{|\Phi_u-\Psi_{\sigma(u)}|:u = 1, 2, \cdots, s\right\}. \
\end{align}
}
Define
\begin{align}
D\left(\mathbf{\Phi},\mathbf{\Psi}\right)=\min\limits_{\sigma \in \Sigma_s}\left \{||\mathbf{\Phi}-\mathbf{\Psi}_{\sigma}||_{\infty}\right\},
\end{align}
and, for $\textbf{P}^{(1)},\widetilde{\textbf{P}^{(1)}} \in\mathbb{R}^s$:
\[\textbf{P}^{(1)}=[p_1\ \ p_2 \ \ \cdots \ \ p_s],\]
\[\widetilde{\textbf{P}^{(1)}} =[\widetilde{p_1}\ \ \widetilde{p_2}\ \ \cdots \ \ \widetilde{p_s}],\]
then
\begin{align}
D\left(\mathbf{P^{(1)}},\widetilde{\mathbf{P^{(1)}}}\right)=\min\limits_{\sigma \in \Sigma_s}\left\{||\mathbf{P^{(1)}}-\widetilde{\mathbf{P^{(1)}}}_\sigma||_{\infty}\right\}.
\end{align}
Now, we claim for large enough $n$,
\begin{itemize}
	\item $P\left(D\left(\textbf{P}^{(1)}, \widetilde{\textbf{P}^{(1)}}\right)\leq \mathcal{T}_n\right) \rightarrow 1$,
	\item $P\left(\bigcup\limits_{j=2}^{\frac{n}{s}}   \left\{ D\left(\textbf{P}^{(1)},\widetilde{\textbf{P}^{(j)}}\right)\leq \mathcal{T}_n \right\}\right) \rightarrow 0$ ,
\end{itemize}
where $\mathcal{T}_n= \frac{1}{n^{\frac{1}{s}+\frac{\alpha}{4}}}$.

Define the hypercubes of $\mathcal{F}^{(n)}$ and $\mathcal{H}^{(n)}$ as
\[\mathcal{F}^{(n)}\triangleq\bigg\{ (x_1, x_2, \cdots , x_s) \in \mathbb{R}^s : \max\limits_u\{|x_u-p_u|\}\leq \mathcal{T}_n, u=1,2, \cdots, s \bigg \}.\]
\[\mathcal{H}^{(n)}\triangleq\bigg\{ (x_1, x_2, \cdots , x_s) \in \mathbb{R}^s : \max\limits_u\{|x_u-p_u|\}\leq 2\mathcal{T}_n, , u=1, 2, \cdots, s \bigg \}.\]
Figure \ref{setBC} shows sets $\mathcal{F}^{(n)}$ and $\mathcal{H}^{(n)}$ in the case $s=2$.

\begin{figure}
	\centering
	\includegraphics[width=.3\linewidth]{fig/setBC.jpg}
	\centering
	\caption{$\textbf{P}^{(1)}$, sets $\mathcal{F}^{(n)}$ and $\mathcal{H}^{(n)}$ for case $s=2$.}
	\label{setBC}
\end{figure}

First, we prove $\widetilde{\textbf{P}^{(1)}}$ is in set $\mathcal{F}^{(n)}$, thus $D\left(\textbf{P}^{(1)}, \widetilde{\textbf{P}^{(1)}}\right)\leq \mathcal{T}_n$. For all $u \in \text{Group } 1$,
a Chernoff bound yields
\begin{align}
\no P\left(\bigg{|}\frac{M_{u}}{m}-p_{u}\bigg{|}\geq \mathcal{T}_n\right)&\leq 2e^{-\frac{m\mathcal{T}_n^2}{3p_u}}\\
\no &=2e^{\left(cn^{\frac{2}{s}+\alpha }\right)\left(\frac{1}{n^{\frac{1}{s}+\frac{\alpha}{4}}}\right)^2\left(\frac{1}{3p_u}\right)}\\
\no &\leq 2e^{-\frac{c}{3}n^{\frac{\alpha}{2}}}.\ \
\end{align}
Thus, by applying the union bound, we have
\begin{align}
\no P\left(D\left(\textbf{P}^{(1)},\widetilde{\textbf{P}^{(1)}}\right)\geq  \mathcal{T}_n\right) & \leq \sum\limits_{u=1}^{s} P\left(\bigg{|}\frac{M_{u}}{m}-p_{u}\bigg{|}\geq \mathcal{T}_n\right) \\
\no &\leq sP\left(\bigg{|}\frac{M_{u}}{m}-p_{u}\bigg{|}\geq \mathcal{T}_n\right) \\
\no &\leq 2se^{-\frac{c}{3}n^{\frac{\alpha}{2}}} \rightarrow 0,\ \
\end{align}
as $n \rightarrow \infty.$ As a result, $D\left(\textbf{P}^{(1)}, \widetilde{\textbf{P}^{(1)}}\right)\leq \mathcal{T}_n$ with high probability.

In the next step, we prove $P\left(\bigcup\limits_{j=2}^{\frac{n}{s}}   \left\{ D\left(\textbf{P}^{(1)},\widetilde{\textbf{P}^{(j)}}\right)\leq \mathcal{T}_n \right\}\right) \rightarrow 0$. For all groups other than group $1$, we have
\[(4 \mathcal{T}_n)^s\delta_1\leq  P\left( \textbf{P}^{(j)} \in \mathcal{H}^{(n)}\right) \leq  (4 \mathcal{T}_n)^s\delta_2,\]
and as a result,
\begin{align}
\no P(\textbf{P}^{(j)} \in \mathcal{H}^{(n)}) &\leq \delta_2 (4\mathcal{T}_n)^s\\
\no &=\delta_2 4^s\frac{1}{n^{1+\frac{\alpha}{4}s}}.\ \
\end{align}
Similarly, for any $\sigma \in \Sigma_s$,
\begin{align}
\no P(\textbf{P}^{(j)}_\sigma \in \mathcal{H}^{(n)}) &\leq \delta_2 (4\mathcal{T}_n)^s\\
\no &=\delta_2 4^s\frac{1}{n^{1+\frac{\alpha}{4}s}},\ \
\end{align}
and since $|\Sigma_s|=s!$, by a union bound,
\begin{align}
\no P\left(\bigcup\limits_{j=2}^{\frac{n}{s}}    \left\{ \bigcup\limits_{\sigma \in \Sigma_s}    \left\{ \textbf{P}^{(j)}_\sigma \in \mathcal{H}^{(n)}\right\} \right\}\right) &\leq \sum\limits_{j=2}^{\frac{n}{s}} \sum\limits_{\sigma \in \Sigma_s} \left(\textbf{P}^{(j)}_\sigma \in \mathcal{H}^{(n)} \right)\\
\no &\leq \frac{n}{s}s!\delta_24^s\frac{1}{n^{1+\frac{\alpha}{4}s}}\\
\no &=(s-1)!4^s\delta_2{n^{-\frac{\alpha}{4}s}}\rightarrow 0,\ \
\end{align}
as $n \rightarrow \infty.$
Thus, all $\textbf{P}^{(j)}$'s are outside of $\mathcal{H}^{(n)}$ with high probability.

Now, we prove that given all $\textbf{P}^{(j)}$'s are outside of $\mathcal{H}^{(n)}$, $P\left(\bigcup\limits_{j=2}^{\frac{n}{s}}   \left\{ D\left(\textbf{P}^{(1)},\widetilde{\textbf{P}^{(j)}}\right)\leq \mathcal{T}_n \right\}\right) \rightarrow 0$. We show that $\widetilde{\textbf{P}^{(j)}}$'s are close to $\textbf{P}^{(j)}$'s, and as a result, they will be outside of $\mathcal{F}^{(n)}$. Specifically, by using a Chernoff bound, for all $u \in \text{Group } j$, we have
\begin{align}
\no P\left(\bigg |\frac{M_u}{m}-p_{u}\bigg | \geq \mathcal{T}_n\right)&\leq 2 e^{-\frac{m \mathcal{T}_n^2}{3p_u}}\\
\no &=2e^{\left(cn^{\frac{2}{s}+\alpha }\right)\left(\frac{1}{n^{\frac{1}{s}+\frac{\alpha}{4}}}\right)^2\left(\frac{1}{3p_u}\right)}\\
\no & \leq 2e^{-\frac{c}{3}n^{\frac{\alpha}{2}}};
\end{align}
thus, by applying a union bound, we have
\begin{align}
\no P\left(D\left(\textbf{P}^{(j)},\widetilde{\textbf{P}^{(j)}}\right)\geq \mathcal{T}_n\right)& \leq \sum\limits_{u=1}^{s} P\left(\bigg{|}\frac{M_{u}}{m}-p_{u}\bigg{|}\geq \mathcal{T}_n\right) \\
\no &\leq 2se^{-\frac{c}{3}n^{\frac{\alpha}{2}}}. \ \
\end{align}

Now by using a union bound, again, we have
\begin{align}
	\no \no P\left(\bigcup\limits_{j=2}^{\frac{n}{s}}   \left\{ D\left(\textbf{P}^{(j)},\widetilde{\textbf{P}^{(j)}}\right)\geq \mathcal{T}_n \right\}\right)& \leq \sum\limits_{j=2}^{\frac{n}{s}}  P\left(D\left(\textbf{P}^{(1)},\widetilde{\textbf{P}^{(j)}}\right)\leq \mathcal{T}_n\right)\\
\no & \leq \frac{n}{s}2se^{-\frac{c}{3}n^{\frac{\alpha}{2}}}\\
\no  &= 2ne^{-\frac{c}{3}n^{\frac{\alpha}{2}}}\rightarrow 0,\ \
\end{align}
as $n \rightarrow \infty.$ Thus, for all $j=2, 3, \cdots, \frac{n}{s}$, $\widetilde{\textbf{P}^{(j)}}$'s are close to $\textbf{P}^{(j)}$'s, thus they will be outside of $\mathcal{F}^{(n)}$. Now, we can conclude as $n \rightarrow \infty$ that:
\begin{align}
\no  P\left(\bigcup\limits_{j=2}^{\frac{n}{s}}   \left\{ D\left(\textbf{P}^{(1)},\widetilde{\textbf{P}^{(j)}}\right)\geq \mathcal{T}_n \right\}\right)\rightarrow 0. \ \
\end{align}

This means that with high probability all $\widetilde{\textbf{P}^{(j)}}$ are outside of $\mathcal{F}^{(n)}$, so the adversary can successfully identify group $1$.

Finally, we prove that, after identifying group $1$, the adversary can correctly identify each member. This step can be done using a similar approach to that above. We define two sets $\mathcal{B}^{(n)}$ and $\mathcal{C}^{(n)}$ (Figure \ref{fig:converse}) around $p_1$. We will show that with high probability, the true estimated value of $p_1$ (shown as $\widetilde{p_1}$) is inside of  $\mathcal{B}^{(n)}$. Also, all $p_u$'s of other members of Group 1 are outside of $\mathcal{C}^{(n)}$, and since their estimated values are close to ${p}_u$'s, the estimated values will be outside of  $\mathcal{B}^{(n)}$. Therefore, the adversary can successfully invert the permutation $\Pi$ within Group $1$ and identify all of the members. Below are the details.

From (\ref{p-tilde}) and (\ref{p-tilde2}), for $u=1, 2, \cdots, s$, we have
\begin{align}
\no \widetilde{p_{u}}=\frac{\sum\limits_{k=1}^mY_u(k)}{m};\ \
\end{align}
as a result,
\begin{align}
\no \widetilde{p_{\Pi(u)}}=\frac{\sum\limits_{k=1}^mX_u(k)}{m}=\frac{M_{u}}{m},\ \
\end{align}
where $M_{u}= \abs*{\left\{k: X_u(k)=1\right\}}.$

Now, according to Figure \ref{fig:converse}, define
\[\mathcal{B}^{(n)}\triangleq \left\{x \in (0,1); |x-p_1| \leq \Delta_n\right\},\]
where $\Delta_n = \frac{1}{n^{\frac{1}{s}+\frac{\alpha}{4}}}.$
Now, we claim that if $m =cn^{\frac{2}{s} +  \alpha}$ for all members of group $1$, as $n \rightarrow \infty$,
\begin{enumerate}
\item $P\left( \widetilde{{p}_{\Pi(1)}}\in \mathcal{B}^{(n)}\right) \rightarrow 1.$
\item $P\left( \bigcup\limits_{u=2}^{s} \left\{\widetilde{{p}_{\Pi(u)}}\in \mathcal{B}^{(n)}\right\}\right) \rightarrow 0.$
\end{enumerate}
Thus, the adversary can identify $\Pi(1)$ by examining  $\widetilde{p_u}$'s and choosing the only one that belongs to $\mathcal{B}^{(n)}$.

First, we want to show that as $n$ goes to infinity,
\[P\left( {\widetilde{p_{\Pi(1)} }}\in \mathcal{B}^{(n)}\right) \rightarrow 1.\]
Note
\begin{align}

\no P\left({\widetilde{p_{\Pi(1)}}} \in \mathcal{B}^{(n)}\right) &= P\left(\frac{M_1}{m} \in  \mathcal{B}^{(n)} \right)\\
\nonumber &= P\left(p_1-\Delta_n\leq \frac{M_1}{m}\leq p_1+\Delta_n \right)\\

\nonumber &= P\left(\abs*{M_1-m p_1}\leq m\Delta_n \right).\ \
\end{align}
From the Chernoff bound, as $n \rightarrow \infty$,
\begin{align}

\no P\left(\abs*{M_1-m p_1}\leq m\Delta_n \right) &\geq 1-2e^{-\frac{m\Delta_n^2}{3p_u}} \\
\nonumber &\geq 1-2e^{-\left(cn^{\frac{2}{s}+\alpha}\right)\left(\frac{1}{n^{\frac{1}{s}+\frac{\alpha}{4}}}\right)^2\left(\frac{1}{3p_u}\right)}\\
\nonumber &\geq 1-2e^{-\frac{c}{3}n^{\frac{\alpha}{2}}}\rightarrow 1. \
\end{align}
As a result,
\[P\left({\widetilde{p_{\Pi(1) }}} \in \mathcal{B}^{(n)}\right) \rightarrow 1.\]

Now, we need to show that as $n$ goes to infinity,
\[P\left( \bigcup\limits_{u=2}^{s} \left\{{\widetilde{p_{\Pi(u)}}}\in \mathcal{B}^{(n)}\right\}\right) \rightarrow 0.\]
First, we define
\[
\mathcal{C}^{(n)}=\left\{x\in (0,1); |x-p_1| \leq 2\Delta_n\right\}
,\]
and claim as $n$ goes to infinity,
\[P\left(\bigcup\limits_{u=2}^s \left\{p_u \in \mathcal{C}^{(n)}\right\} \right)\rightarrow 0. \]

\begin{figure}
	\centering
	\includegraphics[width=.9\linewidth]{fig/converse.jpg}
	\centering
	\caption{$p_1$, sets $\mathcal{B}^{(n)}$ and $\mathcal{C}^{(n)}$ for case $r=2$.}
	\label{fig:converse}
\end{figure}

Note
\[4 \Delta_n \delta_2 < P\left( p_u\in \mathcal{C}^{(n)}\right) < 4 \Delta_n \delta_2,\]
and according to the union bound,
\begin{align}
\no P\left( \bigcup\limits_{u=2}^s \left\{p_u \in \mathcal{C}^{(n)}\right\} \right) &\leq \sum\limits_{u=2}^s P\left( p_u\in \mathcal{C}^{(n)}\right) \\
\nonumber &\leq 4s \Delta_n \delta_2\\
\nonumber &\leq 4s \frac{1}{n^{\frac{1}{s}+{\frac{\alpha}{4}}}} \delta_2 \rightarrow 0; \ \
\end{align}
thus, all $p_u$'s are outside of $\mathcal{C}^{(n)}$ for $u \in \{2,3,  \cdots , s\}$ with high probability.

Now, we claim that given all $p_u$'s are outside of $\mathcal{C}^{(n)}$, $P\left({\widetilde{p_{\Pi (u)}}} \in \mathcal{B}^{(n)}\right)$ is small.
Note,
\begin{align}
\no P\left({\widetilde{p_{\Pi(u)}}}\in \mathcal{B}^{(n)}\right) &\leq P\left(\abs*{{\widetilde{p_{\Pi(u)}}}-p_u } \geq\Delta_n\right) \\
\nonumber &=P\left(\abs*{\sum\limits_{k=1}^m X_u(k)-mp_u}\geq m\Delta_n\right)\ \
\end{align}
According to the Chernoff bound,
\begin{align}
\no P\left(\abs*{M_u-mp_u}\geq  m\Delta_n\right) &\leq 2e^{-\frac{m\Delta_n^2}{3p_u}} \\
\nonumber &= 2e^{-\left(cn^{\frac{2}{s}+\alpha}\right)\left(\frac{1}{n^{\frac{1}{s}+\frac{\alpha}{4}}}\right)^2\left(\frac{1}{3p_u}\right)}\\
\nonumber &\leq 2e^{-\frac{c}{3}n^{\frac{\alpha}{2}}}.\ \
\end{align}
As a result, by using a union bound, as $n$ becomes large,
\begin{align}
\no P\left( \bigcup\limits_{u=2}^s \left\{{\widetilde{p_{\Pi(u)}}}\in \mathcal{B}^{(n)}\right\}\right)\leq s\left(2e^{-\frac{c}{3}n^{\frac{\alpha}{2}}}\right) \rightarrow 0.
\end{align}

Thus, we have proved that if $m=n^{\frac{2}{s}+\alpha}$, there exists an algorithm for the adversary to successfully recover all the members of group $1$. Remember, the adversary identifies the members of group $1$ independent of the structure of the subgraph.

\end{proof}

\subsection{i.i.d.\ $r$-States Model}
\label{iidr}
Now, assume users' data samples can have $r$ possibilities $\left(0, 1, \cdots, r-1\right)$, and $p_u(i)$ is the probability of user $u$ having the data value $i$, i.e., $p_u(i)=P(X_u(k)=i)$, for $k=1, 2, \cdots, m$.  We define the vector $\textbf{p}_u$ as
\[\textbf{p}_u= \begin{bmatrix}
p_u(1) \\ p_u(2) \\ \vdots \\p_u(r-1) \end{bmatrix}, \textrm{ for each }u \in \{1,2,\cdots, n \}.
\]

We also assume $\textbf{p}_u$'s are drawn independently from some continuous density function, $f_\textbf{P}(\textbf{p}_u)$, which has support on a subset of the $(0,1)^{r-1}$ hypercube. In particular, define the range of the distribution as
\begin{align}
	\no  \mathcal{R}_{\textbf{P}} &= \left\{ (x_1, x_2, \cdots, x_{r-1}) \in (0,1)^{r-1}: x_i > 0 , x_1+x_2+\cdots+x_{r-1} < 1\right\}.
\end{align}
Then, we assume there are $\delta_1, \delta_2>0$ such that:
\begin{equation}
\begin{cases}
\no    \delta_1\leq f_{\textbf{P}}(\mathbf{p}_u) \leq \delta_2, & \textbf{p}_u \in \mathcal{R}_{\textbf{P}}.\\
f_{\textbf{P}}(\mathbf{p}_u)=0, &  \textbf{p}_u \notin \mathcal{R}_{\textbf{P}}.
\end{cases}
\end{equation}

\begin{thm}\label{r_state_thm}
	For the above $r$-states model, if $\textbf{Y}$ is the anonymized version of $\textbf{X}$  as defined above, the size of the group including user $1$ is $s$, and
	\begin{itemize}
		\item $m=cn^{\frac{2}{(r-1)s}+\alpha}$, for any $\alpha > 0$;
	\end{itemize}
then user 1 has no privacy for large enough $n$.
\end{thm}

The proof of Theorem \ref{r_state_thm} is similar to the proof of Theorem \ref{two_state_thm}. The algorithm for the adversary to identify all users is similar to Theorem \ref{two_state_thm}. In the first part, we prove the adversary can successfully recover the association graph of anonymized data. Then we show the adversary can uniquely identify group $1$ among all groups, and finally we show the adversary can correctly identify all of the members of group $1$.

Here, we provide the general idea and focus on the main points instead of stating the whole proof.

First, we extend the definition of $D\left(\mathbf{\Phi}, \mathbf{\Psi}\right)$ for vectors. Let
\[\mathbf{\Phi}=\left[\mathbf{\Phi}_1 \ \ \mathbf{\Phi}_2 \ \ \cdots \ \ \mathbf{\Phi}_s\right],\]
\[\mathbf{\Psi}=\left[\mathbf{\Psi}_1 \ \ \mathbf{\Psi}_2 \ \ \cdots \ \ \mathbf{\Psi}_s\right],\]
where $\mathbf{\Phi}_u \in \mathbb{R}^{r-1}$ and $\mathbf{\Psi}_u \in \mathbb{R}^{r-1}$. Define
Define
\begin{align}
\no D\left(\mathbf{\Phi},\mathbf{\Psi}\right)=\min\limits_{\sigma \in \Sigma_s}\left \{\max\big \{||\mathbf{\Phi}_1-\mathbf{\Psi}_{\sigma(1)}||_{\infty}, ||\mathbf{\Phi}_2-\mathbf{\Psi}_{\sigma(2)}||_{\infty}, \cdots, ||\mathbf{\Phi}_s-\mathbf{\Psi}_{\sigma(s)}||_{\infty}\big \}\right\},
\end{align}
where for $u \in \{1, 2, \cdots, s\}$,
{\begin{align}
	\nonumber ||\mathbf{\Phi}_u-\mathbf{\Psi}_{\sigma(u)}||_{\infty}=\max\left\{|\Phi_u(i)-\Psi_{\sigma(u)}(i)|:i = 1, 2, \cdots, r-1\right\}. \
	\end{align}
}

Now define
\[\textbf{P}^{(1)}=\left[\textbf{p}_1 \ \ \textbf{p}_2 \ \ \cdots \ \ \textbf{p}_s\right],\]
\[\widetilde{\textbf{P}^{(1)}}=\left[\widetilde{\textbf{p}}_1 \ \ \widetilde{\textbf{p}}_2 \ \ \cdots \ \ \widetilde{\textbf{p}}_s\right],\]
and we claim for large enough $n$,
\begin{itemize}
	\item $P\left(D\left(\textbf{P}^{(1)}, \widetilde{\textbf{P}^{(1)}}\right)\leq \mathcal{T}'_n\right) \rightarrow 1,$
	\item $P\left(\bigcup\limits_{j=2}^{\frac{n}{s}}   \left\{ D\left(\textbf{P}^{(1)},\widetilde{\textbf{P}^{(j)}}\right)\leq \mathcal{T}'_n \right\}\right) \rightarrow 0$ ,
\end{itemize}
where $\mathcal{T}'_n\triangleq\frac{1}{n^{\frac{1}{s(r-1)}+\frac{1}{\alpha}}}$.

This can be shown similar to the above proof that we provided for the two-states case. First define $\mathcal{F}'^{(n)}$ and $\mathcal{H}'^{(n)}$ as
\begin{align}
\no \mathcal{F}'^{(n)}\triangleq & \left\{(\textbf{x}_1, \textbf{x}_2, \cdots ,\textbf{x}_{s}) \in \left(\mathbb{R}^{(r-1)}\right)^s:
\max\limits_u\{|\textbf{x}_u-\textbf{p}_u|\}\leq \mathcal{T}'_n, u=1, 2, \cdots ,s\right\},
\end{align}
\begin{align}
\no \mathcal{H}'^{(n)}\triangleq &\left\{(\textbf{x}_1, \textbf{x}_2, \cdots ,\textbf{x}_{s}) \in \left(\mathbb{R}^{(r-1)}\right)^s:\max\limits_u\{|\textbf{x}_u-\textbf{p}_u|\} \leq 2\mathcal{T}'_n, u=1, 2, \cdots ,s\right\},
\end{align}
then, prove the adversary can identify group $1$ successfully. In the next step, the adversary has to identify each member of group $1$ correctly.
Let's define sets $\mathcal{B}'^{(n)}$ and $\mathcal{C}'^{(n)}$ as
\begin{align}
	\no \mathcal{B}'^{(n)}\triangleq & \bigg\{(x_1, x_2, \cdots, x_{r-1}) \in \mathcal{R}_{\textbf{P}}: | x_i-p_1(i)| \leq\Delta'_n, i=1, 2, \cdots, r-1\bigg\},
\end{align}
\begin{align}
	\no \mathcal{C}'^{(n)}\triangleq &\bigg \{(x_1, x_2, \cdots, x_{r-1}) \in \mathcal{R}_{\textbf{P}}:
	|x_i-p_1(i)| \leq 2 \Delta'_n, i=1, 2, \cdots,  r-1\bigg\},
\end{align}
where $\Delta'_n = \frac{1}{n^{\frac{1}{s(r-1)}+\frac{\alpha}{4}}}.$ Figure \ref{R_P} shows $\textbf{p}_1$, sets  $\mathcal{B}'{(n)}$ and $\mathcal{C}'{(n)}$ in range of $\mathcal{R}_{\textbf{P}}$ for case $r=3.$
\begin{figure}
	\centering
	\includegraphics[width=.5\linewidth, height=0.5 \linewidth]{fig/rp.jpg}
	\centering
	\caption{$\textbf{p}_1$, sets $\mathcal{B}'_P$ and $\mathcal{C}'_P$ in $R_P$ for case $r=3$.}
	\label{R_P}
\end{figure}

We claim for $m =cn^{\frac{2}{s(r-1)} +  \alpha}$,
\begin{enumerate}
	\item $P\left( {\widetilde{\textbf{p}_{\Pi(1) }}}\in \mathcal{B}'^{(n)}\right) \rightarrow 1.$
	\item $P\left( \bigcup\limits_{u=2}^{s} \left\{{\widetilde{\textbf{p}_{\Pi(u)}}}\in \mathcal{B}'^{(n)}\right\}\right) \rightarrow 0.$
\end{enumerate}
as $n \rightarrow \infty$; thus, user $1$ has no privacy.

\subsection{Markov Chain Model}
\label{markov}
In Sections \ref{iidtwo} and \ref{iidr}, we assumed each user's data patterns was i.i.d.. In this section, users' data patterns are modeled using Markov chains in which each user's data samples are dependent over time. In this model, we again assume there are $r$ possibilities for each data point, i.e., $X_u(k) \in \{0,1, \cdots, r-1\}$.

More specifically, each user's data is modeled by a Markov chain with $r$ states. It is assumed that the Markov chains of all users have the same structure but have different transition probabilities. Let $E$ be the set of edges in the assumed transition graph, so $(i, l) \in E$ if there exists an edge from state $i$ to state $l$, meaning that $p_u(i,l)=P\left(X_u(k+1)=l|X_u(k)=i\right)>0$. The transition matrix is a square matrix used to describe the transitions of a Markov chain; thus, different users can have different transition probability matrices. Note for each state $i$, we have
$\sum\limits_{l=1}^{r} p_u(i,l)=1,$
so the adversary can focus on a subset of size $d=|E|-r$ of the transition probabilities for recovering the entire transition matrix. Let $\textbf{p}_u$ be the vector that contains these transition probabilities for user $u$. We write
\[\textbf{p}_u= \begin{bmatrix}
p_u(1) \\ p_u(2) \\ \vdots \\p_u(d) \end{bmatrix} , \ \ \  \textbf{P} =\left[ \textbf{p}_{1} \ \ \textbf{p}_{2} \ \ \cdots\ \  \textbf{p}_{n}\right].
\]

We also consider $p_u(i)$'s are drawn independently from some continuous density function, $f_\textbf{P}(\textbf{p}_u)$, on the $(0,1)^{|E|-r}$ hypercube. Define the range of distribution as
\begin{align}
	\no  \mathcal{R}_{\textbf{P}} &= \left\{ (x_1, x_2, \cdots, x_{d}) \in (0,1)^{d}: x_i > 0 , x_1+x_2+\cdots+x_{d} < 1\right\}.
\end{align}

As before, we assume there are $ \delta_1, \delta_2 >0$, such that
\begin{equation}
\begin{cases}
\no   \delta_1\leq f_{\textbf{P}}(\textbf{p}_u) \leq \delta_2, & \textbf{p}_u \in \mathcal{R}_{\textbf{p}}.\\
f_{\textbf{P}}(\textbf{p}_u)=0, &  \textbf{p}_u \notin \mathcal{R}_{\textbf{p}}.
\end{cases}
\end{equation}

Now, we can repeat the same steps as the previous sections to prove the following theorem.

\begin{thm}\label{markov_thm}
	For an irreducible, aperiodic Markov chain model, if ${\textbf{Y}}$ is the anonymized version of $\textbf{X}$  as defined above, the size of the group including user $1$ is $s$, and
	\begin{itemize}
		\item $m=cn^{\frac{2}{s(|E|-r)}+\alpha}$, for any $\alpha > 0$;
	\end{itemize}
then user $1$ has no privacy for large enough $n$.
\end{thm}

The basic ideas behind the proof of Theorem \ref{markov_thm} are similar to the ones for Theorems \ref{two_state_thm} and \ref {r_state_thm}; thus, in this part we just focus on the differences and key ideas.

Define the random variable $M_u(i)$ as the total number of visits by user $u$ to state $i$, for $u= 1, 2, \cdots, n$ and $i=0, 1, \cdots, r-1$. Since the Markov chain is irreducible and aperiodic, and $m \rightarrow \infty$, all $\frac{M_i(u)}{m}$ converge to their stationary values. Given $M_u(i) = m_u(i)$, the transitions from state $i$ to state $l$ for user $u$ has a multinomial distribution with probabilities $p_u(i,l)$.

Now, considering the fact that the vector $\textbf{p}_u$ uniquely determines the user $u$, the adversary can invert the anonymization permutation function in a similar way to the i.i.d.\ case by focusing on $\textbf{p}_u$.

Let
\[\mathbf{\Phi}=\left[\mathbf{\Phi}_1\ \ \mathbf{\Phi}_2 \ \ \cdots \ \ \mathbf{\Phi}_s\right],\]
\[\mathbf{\Psi}=\left[\mathbf{\Psi}_1\ \ \mathbf{\Psi}_2\ \ \cdots \ \ \mathbf{\Psi}_s\right],\]
where $\mathbf{\Phi}_u \in \mathbb{R}^{|E|-r}$ and $\mathbf{\Psi}_u \in \mathbb{R}^{|E|-r}$. Define
\begin{align}
\no D\left(\mathbf{\Phi},\mathbf{\Psi}\right)=\min\limits_{\sigma \in \Sigma_s}\left \{\max\big \{||\mathbf{\Phi}_1-\mathbf{\Psi}_{\sigma(1)}||_{\infty}, ||\mathbf{\Phi}_2-\mathbf{\Psi}_{\sigma(2)}||_{\infty}, \cdots, ||\mathbf{\Phi}_s-\mathbf{\Psi}_{\sigma(s)}||_{\infty}\big \}\right\},
\end{align}
where for $u \in \{1, 2, \cdots, s\}$,
{\begin{align}
	\nonumber ||\mathbf{\Phi}_u-\mathbf{\Psi}_{\sigma(u)}||_{\infty}=\max\left\{|\Phi_u(i)-\Psi_{\sigma(u)}(i)|:i = 1, 2, \cdots, |E|-r\right\}. \
	\end{align}
}

Now define
\[\textbf{P}^{(1)}=\left[\textbf{p}_1\ \ \textbf{p}_2\ \ \cdots \ \ \textbf{p}_s\right],\]
\[\widetilde{\textbf{P}^{(1)}}=\left[\widetilde{\textbf{p}_1}\ \ \widetilde{\textbf{p}_2}\ \ \cdots \ \ \widetilde{\textbf{p}_s}\right],\]
 and we claim for large enough $n$,
\begin{itemize}
	\item $P\left(D\left(\textbf{P}^{(1)}, \widetilde{\textbf{P}^{(1)}}\right)\leq \mathcal{T}''_n\right) \rightarrow 1,$
	\item $P\left(\bigcup\limits_{j=2}^{\frac{n}{s}}   \left\{ D\left(\textbf{P}^{(1)},\widetilde{\textbf{P}^{(j)}}\right)\leq \mathcal{T}''_n \right\}\right) \rightarrow 0$ ,
\end{itemize}
where $\mathcal{T}''_n\triangleq\frac{1}{n^{\frac{1}{s(|E|-r)}+\frac{1}{\alpha}}}$.

This can be shown similar to the proof of Theorem \ref{two_state_thm}. First define $\mathcal{F}''^{(n)}$ and $\mathcal{H}''^{(n)}$ as
\begin{align}
\no \mathcal{F}''^{(n)}\triangleq & \left\{(\textbf{x}_1, \textbf{x}_2, \cdots ,\textbf{x}_{s}) \in \left(\mathbb{R}^{(|E|-r)}\right)^s:
\max\limits_u\{|\textbf{x}_u-\textbf{p}_u|\}\leq \mathcal{T}''_n, u=1, 2, \cdots ,s\right\},
\end{align}
\begin{align}
\no \mathcal{H}''^{(n)}\triangleq &\left\{(\textbf{x}_1, \textbf{x}_2, \cdots ,\textbf{x}_{s}) \in \left(\mathbb{R}^{(|E|-r)}\right)^s:\max\limits_u\{|\textbf{x}_u-\textbf{p}_u|\} \leq 2\mathcal{T}''_n, u=1, 2, \cdots ,s\right\},
\end{align}
then, prove that the adversary can identify group $1$ successfully. In the next step, the adversary has to identify each member of group $1$ correctly.
Define sets $\mathcal{B}''^{(n)}$ and $\mathcal{C}''^{(n)}$ as
\begin{align}
	\no \mathcal{B}''^{(n)}\triangleq & \bigg\{(x_1, x_2, \cdots ,x_{d}) \in \mathcal{R}_{\textbf{P}}: | x_i-p_1(i)| \leq \Delta''_n, i=1,2, \cdots , d\bigg\},
\end{align}
\begin{align}
	\no \mathcal{C}''^{(n)}\triangleq &\bigg\{(x_1, x_2, \cdots, x_{d}) \in \mathcal{R}_{\textbf{P}}:
	|x_i-p_1(i)| \leq 2 \Delta''_n, i=1, 2, \cdots, d\bigg\},
\end{align}
where $\Delta''_n = \frac{1}{n^{\frac{1}{s(|E|-r)}+\frac{\alpha}{4}}}.$

We claim for $m =cn^{\frac{2}{s(|E|-r)} +  \alpha}$,
\begin{enumerate}
	\item $P\left( {\widetilde{\textbf{p}_{\Pi(1) }}}\in \mathcal{B}''^{(n)}\right) \rightarrow 1,$
	\item $P\left( \bigcup\limits_{u=2}^{s} \left\{{\widetilde{\textbf{p}_{\Pi(u)}}}\in \mathcal{B}''^{(n)}\right\}\right) \rightarrow 0,$
\end{enumerate}
as $n \rightarrow \infty $. This can be shown similar to the proof of Theorem \ref{two_state_thm}, so the adversary can successfully recover the members of group $1$.

\section{Privacy using Anonymization and Obfuscation}
\label{obfs}
Here we consider the case when both anonymization and obfuscation techniques are employed, as shown in Figure \ref{fig:xyz}. We assume similar obfuscation to \cite{nazanin_ISIT2017}.

\subsection{i.i.d.\ Two-States Model}
\label{iidtwo_obfs}
Again, let us start with the i.i.d.\ two-states model. As before, we assume that $p_u$'s are drawn independently from some continuous density function, $f_P(p_u)$, on the $(0,1)$ interval.

To obfuscate the data samples, for each user $u$ we independently generate a random variable $R_u$ that is uniformly distributed between $0$ and $a_n$, where $a_n \in (0,1]$. The value of $R_u$ shows the probability that the user's data sample is changed to a different value by obfuscation, and $a_n$ is termed the ``noise level'' of the system.
So, for the case of $r=2$, where there are two states for users' data pattern (state $0$ and state $1$), the obfuscated data is obtained by passing users' data through a Binary Symmetric Channel (BSC) with small error probability \cite{randomizedresponse}, so we can write
\[
Z_{u}(k)=\begin{cases}
{X}_{u}(k), & \textrm{with probability } 1-R_u.\\
1-{X}_{u}(k),& \textrm{with probability of } R_u.
\end{cases}
\]

The effect of the obfuscation is to alter the probability distribution function of each user's data samples in a way that is unknown to the adversary, since it is independent of all past activity of the user, and hence the obfuscation inhibits user identification. For each user, $R_u$ is generated once and is kept constant for the collection of samples of length $m$, thus providing a very low-weight obfuscation algorithm.

The $Z_u(k)$'s are i.i.d.\ with a Bernoulli distribution with parameter
\begin{align}
	\no Q_u&=P_u(1-R_u)+(1-P_u)R_u  \\
	\nonumber &= P_u+\left(1-2P_u\right)R_u. \ \
\end{align}
Thus,
\[Z_u(k) \ | \ Q_u=q_u \sim Bernoulli\left(q_u\right)\]
Here, $q_u$ is the probability that an obfuscated data sample of user $u$ is equal to one.  Define the vector $\textbf{Q}$ that contains the obfuscated probabilities:
\[\textbf{Q}=\left[Q_1\ \ Q_2\ \ \cdots\ \ Q_n\right],\]
and the vector containing the permutation of those probabilities after anonymization as $\textbf{V}$. So
\begin{align}
	\no {\textbf{V}} &=\textrm{Perm}\left(Q_1, Q_2, \cdots,  Q_n; \Pi \right) \\
	\nonumber &=\left[Q_{\Pi^{-1}(1)}\ \ Q_{\Pi^{-1}(2)}\ \ \cdots\ \ Q_{\Pi^{-1}(n)}\right ] \\
	\nonumber &=\left[{V}_{1}\ \ {V}_{2}\ \ \cdots\ \ {V}_{n}\right ] \ \
\end{align}
As a result, for $u=1,2,..., n$,
\[Y_u(k) \sim Bernoulli \left(V_u\right).\]

\begin{thm}\label{two_state_thm_converse_obfs}
	For the above two-states model, if ${\textbf{Z}}$ is the obfuscated version of $\textbf{X}$, and ${\textbf{Y}}$ is the anonymized version of ${\textbf{Z}}$ as defined above, the size of the group including user $1$ is $s$, and
	\begin{itemize}
		\item $m =cn^{\frac{2}{s} +  \alpha}$ for any $c>0$ and $\alpha>0$;
		\item $R_u \sim Uniform [0, a_n]$, where $a_n \triangleq c'n^{-\left(\frac{1}{s}+\beta\right)}$ for any $c'>0$ and $\beta>\frac{\alpha}{4}$;
	\end{itemize}
	then user $1$ has no privacy as $n$ goes to infinity.
\end{thm}

\textit{Discussion}:
It is insightful to compare this result to Theorem $1$ in \cite{nazanin_ISIT2017}, which states that if the users are not correlated, then all users have perfect privacy as long the noise level $(a_n)$ used to obfuscate the users' data samples is larger than $O(n^{-1})$, even if $m(n)$ is arbitrary. Here, Theorem \ref{two_state_thm_converse_obfs} states that with a much larger $a_n$ the adversary can de-anonymize and de-obfuscate all users with vanishing error probability. Therefore, we see that correlation can significantly reduce the privacy of users. However, note that the asymptotic noise level is still zero in this case. Specifically, if $A_m(u) = \frac{\abs*{\left\{k:{Z}_u(k) \neq X_u(k)\right\}}}{m}$, then
\[E[A_m(u)]=E[A_m]= O\left(\frac{1}{n^{\frac{1}{s}+\beta}}\right) \rightarrow 0,\]
implying that the asymptotic noise level is zero.
$\\$

\noindent \textbf{Proof of Theorem \ref{two_state_thm_converse_obfs} :}
\begin{proof}
	The proof of Theorem \ref{two_state_thm_converse_obfs} similar to the proof of Theorem \ref{two_state_thm} and consists of three parts:
	\begin{enumerate}
		\item Showing the adversary can reconstruct the association graph of the obfuscated and anonymized data with small error probability.
		\item Showing the adversary can uniquely identify group $1$ with small error probability.
		\item Showing the adversary can successfully identify all of the members of group $1$.
	\end{enumerate}

	In Lemma \ref{lem1}, we show that for the case of anonymization, the adversary can reconstruct the entire association graph with arbitrarily small error probability if the number of the adversary's observations per user $(m)$ is bigger than $(\log n)^3$. Since obfuscation is done independently (from other users' obfuscation and from users' data), it does not change the association graph. Therefore, since $n^{\frac{2}{s}+\alpha}>(\log n)^3$,  we can use Lemma \ref{lem1} to show the adversary can reconstruct the obfuscated version of association graph with small error probability.

	Now, assume the size of group $1$ is $s$.  Without loss of generality, suppose the members of group $1$ are users $\{1,2, \cdots , s\}$, so there are at most $\frac{n}{s}$ groups of size $s$. We call these groups $1, 2, \cdots, \frac{n}{s}$. The adversary needs to first identify the group $1$ among all of these groups.

	According to Section \ref{iidtwo}, $\Sigma_s$ is defined as the set of all permutation on $s$ elements, and $\textbf{P}^{(1)}, \widetilde{\textbf{P}^{(1)}} \in\mathbb{R}^s$ are defined as
	\[\textbf{P}^{(1)}=[p_1 \ \ p_2\ \ \cdots\ \ p_s].\]

	\[\widetilde{\textbf{P}^{(1)}}=[\widetilde{p}_1\ \ \widetilde{p}_2\ \ \cdots\ \ \widetilde{p}_s].\]

We claim as $n \rightarrow \infty$ that:
\begin{itemize}
	\item $P\left(D\left(\textbf{P}^{(1)}, \widetilde{\textbf{P}^{(1)}}\right)\leq \mathcal{T}_n\right) \rightarrow 1, $
	\item $P\left(\bigcup\limits_{j=2}^{\frac{n}{s}}   \left\{ D\left(\textbf{P}^{(1)},\widetilde{\textbf{P}^{(j)}}\right)\leq \mathcal{T}_n \right\}\right) \rightarrow 0$ ,
\end{itemize}
where $\mathcal{T}_n= \frac{1}{n^{\frac{1}{s}+\frac{\alpha}{4}}}$.

As shown in Figure \ref{fig:converse}, define
\[\mathcal{F}^{(n)}\triangleq\bigg\{ (x_1, x_2, \cdots , x_s) \in \mathbb{R}^s : \max\limits_u\{|x_u-p_u|\}\leq \mathcal{T}_n, u=1, 2, \cdots, s \bigg \},\]
\[\mathcal{H}^{(n)}\triangleq\bigg\{ (x_1, x_2, \cdots , x_s) \in \mathbb{R}^s : \max\limits_u\{|x_u-p_u|\}\leq 2\mathcal{T}_n, u=1, 2, \cdots, s \bigg \}.\]

First we prove, for large enough $n$, that
\[P\left(D\left(\textbf{P}^{(1)},\widetilde{\textbf{P}^{(1)}}\right)\leq \mathcal{T}_n\right) \rightarrow 1.\]
Note
\begin{align}
\widetilde{p_{u}}=\frac{\sum\limits_{k=1}^mY_u(k)}{m};\ \
\label{p-tilde3}
\end{align}
as a result,
\begin{align}
\widetilde{p_{\Pi(u)}}=\frac{\sum\limits_{k=1}^mZ_u(k)}{m}=\frac{\widehat{M}_{u}}{m},\ \
\label{p-tilde4}
\end{align}
where $\widehat{M}_u=\abs*{\left\{k: Z_u(k)=1\right\}}.$

	Now can write for all $u$ in Group $1$,
	\begin{align}
		\no P\left(\bigg |\frac{\widehat{M}_u}{m}-p_u\bigg |\leq \mathcal{T}_n\right) &= P\left(p_u-\mathcal{T}_n\leq \frac{\widehat{M}_u}{m}\leq p_u+\mathcal{T}_n \right)\\
		\nonumber &= P\left(p_u-\mathcal{T}_n-q_u\leq\frac{\widehat{M}_u}{m}-q_u\leq p_u+\mathcal{T}_n-q_u \right).\ \
	\end{align}
	Note that for any $u \in \{1,2,\cdots, s\}$, we have
	\begin{align}
		\no |p_u-q_u| &=|1-2p_u|R_u\\
		\no & \leq R_u \leq a_n,
	\end{align}
	so, we can conclude
	\begin{align}
		\no P\left(\bigg |\frac{\widehat{M}_u}{m}-p_u\bigg |\leq \mathcal{T}_n\right) &= P\left(p_u-\mathcal{T}_n-q_u\leq \frac{\widehat{M}_u}{m}-q_u\leq  p_u+\mathcal{T}_n-q_u \right)\\
		\nonumber  &\geq P\left(-\mathcal{T}_n+ a_n\leq \frac{\widehat{M}_u}{m}-q_u\leq -a_n+\mathcal{T}_n \right)\\
		&= P\left(\abs*{{\widehat{M}_u}-mq_u}\leq  m (\mathcal{T}_n-a_n) \right).\ \
		\label{obfs1}
	\end{align}
Since $a_n \rightarrow 0$, for $p_u \in (0,1)$ and large enough $n$, we can say $p_u+a_n < 2 p_u$. Employing a Chernoff bound,
	\begin{align}

		\no P\left(\abs*{{\widehat{M}_u}-mq_u}\leq m (\mathcal{T}_n-a_n) \right) &\geq 1-2e^{-\frac{m(\mathcal{T}_n-a_n)^2}{3q_u}} \\
		\nonumber &\geq 1-2e^{-\left(cn^{\frac{2}{s}+\alpha}\right)\left(\frac{1}{n^{\frac{1}{s}+\frac{\alpha}{4}}}- \frac{c'}{n^{\frac{1}{s} +  \beta}}\right)^2 \left(\frac{1}{3(p_u+a_n)}\right)}\\

		&\geq 1-2e^{-\frac{c''}{6 p_u}n^{\frac{\alpha}{2}}}. \ \
		\label{obfs2}
	\end{align}

	Now from (\ref{obfs1}) and (\ref{obfs2}), we can conclude
	\begin{align}
		\no P\left(\bigg |\frac{\widehat{M}_u}{m}-p_u\bigg |\leq \mathcal{T}_n\right) \geq 	1-2e^{-\frac{c''}{6 p_u}n^{\frac{\alpha}{2}}},\ \
	\end{align}
	and
	\begin{align}
		\no P\left(\bigg |\frac{\widehat{M}_u}{m}-p_u\bigg |\geq \mathcal{T}_n\right) &\leq 	2e^{-\frac{c''}{6 p_u}n^{\frac{\alpha}{2}}}\\
		& \leq 2e^{-\frac{c''}{6}n^{\frac{\alpha}{2}}}
		\label{obfs3}
	\end{align}

Recall
\begin{align}
\no D\left(\mathbf{P^{(1)}},\widetilde{\mathbf{P^{(1)}}}\right)=\min\limits_{\sigma \in \Sigma_s}\left\{||\mathbf{P^{(1)}}-\widetilde{\mathbf{P^{(1)}}}||_{\infty}\right\},
\end{align}
	thus, by using the definition of $D\left(\textbf{P}^{(1)},\widetilde{\textbf{P}}^{(1)}\right)$ and Equation \ref{obfs3} and applying the union bound, we have
	\begin{align}
		\no P\left(D\left(\textbf{P}^{(1)},\widetilde{\textbf{P}}^{(1)}\right)\geq \mathcal{T}_n\right) &\leq \sum\limits_{u=1}^{s}  P\left(\bigg |\frac{\widehat{M}_u}{m}-p_u\bigg |\geq \mathcal{T}_n\right) \\
		 \no &\leq 2se^{-\frac{c''}{6}n^{\frac{\alpha}{2}}} \rightarrow 0,\ \
	\end{align}
as $n \rightarrow \infty.$
As a result,
	\begin{align}
		\no P\left(D\left(\textbf{P}^{(1)},\widetilde{\textbf{P}^{(1)}}\right)\leq \mathcal{T}_n\right) \rightarrow 1.\ \
	\end{align}
 In the next step, we should prove
	$P\left(\bigcup\limits_{j=2}^{\frac{n}{s}}   \left\{ D\left(\textbf{P}^{(1)},\widetilde{\textbf{P}^{(j)}}\right)\leq \mathcal{T}_n \right\}\right) \rightarrow 0$.

First, we prove and claim that, as $n$ goes to infinity,
	\[P\left(\bigcup\limits_{j=2}^{\frac{n}{s}} \left\{\textbf{P}^{(j)} \in \mathcal{H}^{(n)}\right\} \right)\rightarrow 0. \]
Note
\[(4 \mathcal{T}_n)^s\delta_1\leq  P\left( \textbf{P}^{(j)} \in \mathcal{H}^{(n)}\right) \leq  (4 \mathcal{T}_n)^s\delta_2,\]
and as a result,
\begin{align}
\no P(\textbf{P}^{(j)} \in \mathcal{H}^{(n)}) &\leq \delta_2 (4\mathcal{T}_n)^s\\
\no &=\delta_2 4^s\frac{1}{n^{1+\frac{\alpha}{4}s}}.\ \
\end{align}
Similarly, for any $\sigma \in \Sigma_s$,
\begin{align}
\no P(\textbf{P}^{(j)}_\sigma \in \mathcal{H}^{(n)}) &\leq \delta_2 (4\mathcal{T}_n)^s\\
\no &=\delta_2 4^s\frac{1}{n^{1+\frac{\alpha}{4}s}},\ \
\end{align}
and since $|\Sigma_s|=s!$, by a union bound,
\begin{align}
\no P\left(\bigcup\limits_{j=2}^{\frac{n}{s}}    \left\{ \bigcup\limits_{\sigma \in \Sigma_s}    \left\{ \textbf{P}^{(j)}_\sigma \in \mathcal{H}^{(n)}\right\} \right\}\right) &\leq \sum\limits_{j=2}^{\frac{n}{s}} \sum\limits_{\sigma \in \Sigma_s} \left(\textbf{P}^{(j)}_\sigma \in \mathcal{H}^{(n)} \right)\\
\no &\leq \frac{n}{s}s!\delta_24^s\frac{1}{n^{1+\frac{\alpha}{4}s}}\\
\no &={(s-1)!4^s\delta_2}{n^{-\frac{\alpha}{4}s}}\rightarrow 0,\ \
\end{align}
as $n \rightarrow \infty.$ As a result, we can conclude that all $\textbf{P}^{(j)} $'s are outside of $\mathcal{H}^{(n)}$ for $j \in \left\{2,3,  \cdots , \frac{n}{s}\right\}$ with high probability.

	Now, we claim that, given all $\textbf{P}^{(j)} $'s are outside of $\mathcal{H}^{(n)}$, $P\left(\bigcup\limits_{j=2}^{\frac{n}{s}}   \left\{ D\left(\textbf{P}^{(1)},\widetilde{\textbf{P}^{(j)}}\right)\leq \mathcal{T}_n \right\}\right)$ is small. In other words, by using a Chernoff bound, it is shown
	$\widetilde{\mathbf{P}^{(j)}}$'s are close to $\mathbf{P}^{(j)}$'s, and they will be outside of $\mathcal{F}^{(n)}$.

For all $u$ in Group $j$,
\begin{align}
	\no P\left(\bigg{|}\frac{\widehat{M}_u}{m}-p_u\bigg{|} \leq \mathcal{T}_n \right) &=  P\left(-m \mathcal{T}_n \leq {\widehat{M}_u}-mp_u\leq m\mathcal{T}_n \right) \\
	\nonumber & =P\left(-m \mathcal{T}_n+mp_u-mq_u \leq {\widehat{M}_u}-mq_u\leq m\mathcal{T}_n+mp_u-mq_u \right)\ \
\end{align}
Remember that for any $u$ in Group $j$, we have
\begin{align}
\no |p_u-q_u| \leq a_n,\ \
\end{align}
so, we have
\begin{align}
\no P\left(\bigg{|}\frac{\widehat{M}_u}{m}-p_u\bigg{|} \leq \mathcal{T}_n \right) &=  P\left(-m \mathcal{T}_n+mp_u-mq_u \leq {\widehat{M}_u}-mq_u\leq m\mathcal{T}_n+mp_u-mq_u \right)\\
\nonumber & \geq P\left(-m \mathcal{T}_n+ma_n \leq {\widehat{M}_u}-mq_u\leq m\mathcal{T}_n-ma_n \right)\\
\nonumber & = P\left( |{\widehat{M}_u}-mq_u| \leq m(\mathcal{T}_n-a_n) \right).\
\end{align}

Note $a_n \rightarrow 0,$ so for $p_u\in (0,1)$ and large enough $n$, we have $p_u+a_n < 2p_u$. Now, by using a Chernoff Bound,
\begin{align}
\no P\left(\bigg{|}\frac{\widehat{M}}{m}_u-p_u\bigg{|} \leq \mathcal{T}_n \right) &\geq  P\left( |{\widehat{M}_u}-mq_u| \leq m(\mathcal{T}_n-a_n) \right)\\
\no &\geq 1-2e^{-\frac{m(\mathcal{T}_n-a_n)^2}{3q_u}} \\
	\nonumber & \geq 1-2e^{-\left(cn^{\frac{2}{s}+\alpha}\right)\left(\frac{1}{n^{\frac{1}{s}+\frac{\alpha}{4}}}- \frac{c'}{n^{\frac{1}{s} +  \beta}}\right)^2 \left(\frac{1}{3(p_u+a_n)}\right)}\\
	\nonumber &\geq 1- 2e^{-\frac{c''n^{\frac{\alpha}{2}}}{6 p_u}} \\
	\nonumber &\geq 1- 2e^{-\frac{c''}{6}n^{\frac{\alpha}{2}}}. \ \
\end{align}
so we have
\begin{align}
\no P\left(\bigg{|}\frac{\widehat{M}}{m}_u-p_u\bigg{|} \geq \mathcal{T}_n \right) &\leq  2e^{-\frac{c''}{6}n^{\frac{\alpha}{2}}}. \ \
\end{align}
Thus, by applying a union bound we can conclude
	\begin{align}
		\no P\left(D\left(\textbf{P}^{(j)},\widetilde{\textbf{P}^{(j)}}\right)\geq \mathcal{T}_n\right) &\leq \sum\limits_{u=1}^{s} P\left(\bigg{|}\frac{\widehat{M}}{m}_u-p_u\bigg{|} \leq \mathcal{T}_n \right)  \\\no  &\leq 2se^{-\frac{c''}{6}n^{\frac{\alpha}{2}}}.\ \
	\end{align}
Now by using a union bound, we can conclude,
	\begin{align}
		\no \no P\left(\bigcup\limits_{j=2}^{\frac{n}{s}}   \left\{ D\left(\textbf{P}^{(j)},\widetilde{\textbf{P}^{(j)}}\right)\leq \mathcal{T}_n \right\}\right)& \leq \sum\limits_{j=2}^{\frac{n}{s}}  P\left(D\left(\textbf{P}^{(j)},\widetilde{\textbf{P}^{(j)}}\right)\leq \mathcal{T}_n\right)\\
		\no & \leq 2ne^{-\frac{c''}{6}n^{\frac{\alpha}{2}}}\rightarrow 0,\ \
	\end{align}
as $n \rightarrow \infty$. Thus, we have shown that for all $j=1, 2, \cdots, \frac{n}{s}$, $\widetilde{\mathbf{P}^{(j)}}$'s are close to ${\mathbf{P}^{(j)}}$, which are outside of set $\mathcal{F}^{(n)}$. As a result, as $n \rightarrow \infty$,
	\begin{align}
		\no \no P\left(\bigcup\limits_{j=2}^{\frac{n}{s}}   \left\{ D\left(\textbf{P}^{(1)},\widetilde{\textbf{P}^{(j)}}\right)\geq \mathcal{T}_n \right\}\right) \rightarrow 1.
	\end{align}

	In the next step, we need to prove that after identifying group $1$, the adversary can correctly identify each member. In other words, the adversary should identify the permutation of group $1$.

	According to Figure \ref{fig:converse}, we define
	\[\mathcal{B}^{(n)}\triangleq \left\{x \in (0,1); |x-p_1| \leq \Delta_n\right\},\]
	where $\Delta_n = \frac{1}{n^{\frac{1}{s}+\frac{\alpha}{4}}},$ and we claim that if $m =cn^{\frac{2}{s} +  \alpha}$  for all members of group $1$,
	\begin{enumerate}
		\item $P\left( {\widetilde{{p}_{\Pi(1)}}}\in \mathcal{B}^{(n)}\right) \rightarrow 1.$
		\item $P\left( \bigcup\limits_{u=2}^{s} \left\{{\widetilde{{p}_{\Pi(u)}}}\in \mathcal{B}^{(n)}\right\}\right) \rightarrow 0.$
	\end{enumerate}
	Thus, the adversary can identify $\Pi(1)$ by examining  ${\widetilde{{p}_u}}$'s and choosing the only one that belongs to $\mathcal{B}^{(n)}$.

	First, we show that as $n$ goes to infinity,
	\[P\left( {\widetilde{{p}_{\Pi(1) }}}\in \mathcal{B}^{(n)}\right) \rightarrow 1,\]
we can write
	\begin{align}
		\no P\left({\widetilde{{p}_{\Pi(1)}}} \in \mathcal{B}^{(n)}\right) &= P\left(\frac{\widehat{M}_1}{m} \in  \mathcal{B}^{(n)} \right)\\
		\nonumber &= P\left(p_1-\Delta_n\leq \frac{\widehat{M}_1}{m}\leq p_1+\Delta_n \right)\\
		\nonumber &= P\left(mp_1-m\Delta_n-m\widehat{p}_1\leq \widehat{M}_1-mq_1 \leq mp_1+m\Delta_n-mq_1 \right).\ \
	\end{align}

	Note that for any $u \in \{1,2,\cdots, s\}$, we have
	\begin{align}
		\no |p_u-q_u| &=|1-2p_u|R_u \\
		\no & \leq R_u\leq a_n,
	\end{align}
	So, we can conclude
	\begin{align}
		\no P\left({\widetilde{{p}_{\Pi(1)}}} \in \mathcal{B}^{(n)}\right) &= P\left(mp_1-m\Delta_n-mq_1\leq \widehat{M}_1-mq_1 \leq mp_1+m\Delta_n-m\widehat{p}_1 \right)\\
		\nonumber  &\geq P\left(-m\Delta_n+m a_n\leq \widehat{M}_1-mq_1 \leq -ma_n+m\Delta_n \right)\\
		&= P\left(\abs*{\widehat{M}_1-mq_1}\leq m (\Delta_n-a_n) \right).\ \
		\label{obfs4}
	\end{align}
	Since $a_n \rightarrow 0$, for $p_1 \in (0,1)$ and large enough $n$, we can say $p_1+a_n < 2 p_1$. According to a Chernoff bound,

	\begin{align}

		\no P\left(\abs*{\widehat{M}_1-mq_1}\leq m (\Delta_n-a_n) \right) &\geq 1-2e^{-\frac{m(\Delta_n-a_n)^2}{3q_1}} \\
		\nonumber &\geq 1-2e^{-\frac{1}{3(p_1+a_n)}cn^{\frac{2}{s}+\alpha}\left(\frac{1}{n^{\frac{1}{s}+\frac{\alpha}{4}}}- \frac{c'}{n^{\frac{1}{s} +  \beta}}\right)^2}\\

		\no &\geq 1-2e^{-\frac{c''}{6 p_1}n^{\frac{\alpha}{2}}} \\
		&\geq 1-2e^{-\frac{c''}{6n^{\frac{\alpha}{2}}}}. \ \
		\label{obfs5}
	\end{align}
	Now by using (\ref{obfs4}) and (\ref{obfs5}), we can conclude ,
	\[P\left({\widetilde{{p}_{\Pi(1)}}} \in \mathcal{B}^{(n)}\right) \rightarrow 1.\]

	Now, we need to show that as $n$ goes to infinity,
	\[P\left( \bigcup\limits_{u=2}^{s} \left\{{\widetilde{{p}_{\Pi(u)}}}\in \mathcal{B}^{(n)}\right\}\right) \rightarrow 0.\]
	First, we define
	\[
	\mathcal{C}^{(n)}=\left\{x\in (0,1); |x-p_1|\leq 2\Delta_n\right\}
	,\]
	and claim as $n$ goes to infinity,
	\[P\left(\bigcup\limits_{u=2}^s \left\{P_u\in \mathcal{C}^{(n)}\right\} \right)\rightarrow 0. \]

	Note
	\[4\Delta_n\delta_1\leq  P\left( P_u\in \mathcal{C}^{(n)}\right) \leq 4 \Delta_n\delta_2,\]
	and according to the union bound,
	\begin{align}
		\no P\left( \bigcup\limits_{u=2}^s \left\{P_u \in \mathcal{C}^{(n)}\right\} \right) &\leq \sum\limits_{u=2}^s P\left( P_u \in C^{(n)}\right) \\
		\nonumber &\leq 4s \Delta_n \delta_2\\
		\nonumber &= 4s \frac{1}{n^{\frac{1}{s}+{\frac{\alpha}{4}}}} \delta_2 \rightarrow 0,\ \
	\end{align}
	as $n \rightarrow \infty$. As a result, we can conclude that all $p_j$'s are outside of $\mathcal{C}^{(n)}$ for $u \in \left\{2,3,  \cdots , n\right\}$ with high probability. Now, we claim that given all $p_u$'s are outside of $\mathcal{C}^{(n)}$, $P\left({\widetilde{{p}_{\Pi (u)}}} \in \mathcal{B}^{(n)}\right)$ is small. Remember that for any $u \in \{1, 2,\cdots, n \}$, we have
	\begin{align}
		\no |p_u-q_u| \leq a_n.
	\end{align}
	Now, we can write
	\begin{align}
		\nonumber
		\no P\left({\widetilde{{p}_{\Pi(u)}}} \in \mathcal{B}^{(n)}\right) &\leq P\left(\abs*{{\widetilde{{p}_{\Pi(u)}}}-q_u}\geq (\Delta_n-a_n) \right)\\

		&= P\left(\abs*{\widehat{M}_u-mq_u}\geq  m(\Delta_n-a_n) \right).\ \
		\label{obfs6}
	\end{align}

	According to the Chernoff bound, for large enough $n$,
	\begin{align}

		\no P\left(\abs*{\widehat{M}_u-mq_u}\geq  m(\Delta_n-a_n) \right) &\leq 2e^{-\frac{m(\Delta_n-a_n)^2}{3q_1}} \\
		\nonumber &\leq 2e^{-\left(cn^{\frac{2}{s}+\alpha}\right)\left(\frac{1}{n^{\frac{1}{s}+\frac{\alpha}{4}}}- \frac{c'}{n^{\frac{1}{s} +  \beta}}\right)^2\left(\frac{1}{3(p_1+a_n)}\right)}\\

		\no &\leq 2e^{-\frac{c''}{6 p_1}n^{\frac{\alpha}{2}}} \\
		&\leq 2e^{-\frac{c''}{6}n^{\frac{\alpha}{2}}}. \ \
		\label{obfs7}
	\end{align}

	From (\ref{obfs6}) and (\ref{obfs7}), we have
	\begin{align}
		P\left({\widetilde{{p}_{\Pi(u)}}} \in \mathcal{B}^{(n)}\right) \leq 2e^{-\frac{c''}{6}n^{\frac{\alpha}{2}}},\ \
	\end{align}
	Thus, by using a union bound, we can conclude,
	\begin{align}
		\no P\left( \bigcup\limits_{u=2}^s \left\{\widetilde{{p}_{\Pi(u)}}\in \mathcal{B}^{(n)}\right\}\right)&\leq \sum\limits_{u=2}^{s}P\left({\widetilde{{p}_{\Pi(u)}}}\in \mathcal{B}^{(n)}\right)\\
		\nonumber &\leq s\left(2e^{-\frac{c''}{6}n^{\frac{\alpha}{2}}}\right) \rightarrow 0,\ \
	\end{align}
	as $n \rightarrow \infty$. So the adversary can successfully recover $Z_1(k)$. Since $Z_{1}(k)=X_1(k)$ with probability $1-R_u=1-o(1)$, the adversary can recover $X_{1}(k)$ with vanishing error probability.

\end{proof}

\subsection{i.i.d.\ $r$-States Model}
Now, assume users' data samples can have $r$ possibilities $\left(0, 1, \cdots, r-1\right)$. Similar to Section \ref{iidr}, we assume $\textbf{p}_u$'s are drawn independently from some continuous density function, $f_\textbf{P}(\textbf{p}_u)$, which has support on a subset of the $(0,1)^{r-1}$ hypercube, and $\textbf{p}_u$, $f_\textbf{P}(\textbf{p}_u)$, and $\mathcal{R}_\textbf{P}$ are defined as in Section \ref{iidr}.

Also, for the case $r>2$, the obfuscated data is obtained by passing the users' data through an $r$-ary symmetric channel with a random error probability, so for $l \in \{ 0, 1, \cdots, r-1\}$:

\[
P({Z}_{u}(k)=l| X_{u}(k)=i) =\begin{cases}
1-R_u, & \textrm{for } l=i.\\
\frac{R_u}{r-1}, & \textrm{for } l \neq i.
\end{cases}
\]

\begin{thm}\label{r_state_thm_converse_obfs}
	For the above $r$-states model, if ${\textbf{Z}}$ is the obfuscated version of $\textbf{X}$, and ${\textbf{Y}}$ is the anonymized version of ${\textbf{Z}}$ as defined above, the size of the group including user $1$ is $s$, and
	\begin{itemize}
		\item $m =cn^{\frac{2}{s(r-1)} +  \alpha}$ for any  $c>0$ and $\alpha>0$;
		\item $R_u \sim Uniform [0, a_n]$, where $a_n \triangleq c'n^{-\left(\frac{1}{s(r-1)}+\beta\right)}$ for any $c'>0$ and $\beta>\frac{\alpha}{4}$;
	\end{itemize}
	user $1$ has no privacy as $n$ goes to infinity.
\end{thm}

By using the general idea stated  in Section \ref{iidr}, the proof of Theorem \ref{r_state_thm_converse_obfs} is similar to the proof of Theorem \ref{two_state_thm_converse_obfs}.

\subsection{Markov Chain Model}
In this section, users' data patterns are modeled using Markov chains and there are $r$ possibilities for users' data patterns. Similar to Section \ref{markov}, we assume $p_u(i)$'s are drawn independently from some continuous density function, $f_\textbf{P}(\textbf{p}_u)$, on the $(0,1)^{|E|-r}$ hypercube, and $\textbf{p}_u$, $f_\textbf{P}(\textbf{p}_u)$, and $\mathcal{R}_\textbf{P}$ are defined in Section \ref{markov}.

Using the above observations, we can now repeat the same reasoning as the last sections to show the following theorem.

\begin{thm}\label{markov_thm_obfs}
	For an irreducible, aperiodic Markov chain model, iff ${\textbf{Z}}$ is the obfuscated version of $\textbf{X}$, and ${\textbf{Y}}$ is the anonymized version of ${\textbf{Z}}$ as defined above, the size of the group including user $1$ is $s$, and
	\begin{itemize}
		\item $m =cn^{\frac{2}{s(|E|-r)} +  \alpha}$ for any $c>0$ and $\alpha>0$;
		\item $R_u \sim Uniform [0, a_n]$, where $a_n \triangleq c'n^{-\left(\frac{1}{s(|E|-r)}+\beta\right)}$ for any $c'>0$ and $\beta>\frac{\alpha}{4}$;
	\end{itemize}
then user $1$ has no privacy for large enough $n$.
\end{thm}

\section{Achieving Perfect Privacy in the Presence of Correlation }
\label{perfect}
In the previous parts of the paper, we argued and demonstrated that dependencies between users can degrade the privacy provided by standard privacy-preserving mechanisms (PPMs). In this section, we discuss how to design PPMs considering user dependencies in order to better preserve privacy.
First, note that independent obfuscation alone cannot be sufficient even at a high noise level, because it cannot change the association graph. Therefore, the adversary can still reconstruct the association graph with a small number of observations if we add independent obfuscation noise. To mitigate this issue, we suggest that associated users should collaborate in applying the noise when deploying a PPM.

For clarity, we focus on the two-states i.i.d.\ case ($r=2$) where the association graph consists of subgraphs with the size of each of them less than or equal to $2$ $(s_j \leq 2)$. Thus, according to Figure \ref{fig:simpleexam}, there are some  connected users and there are also some isolated users. First, we state the following lemma.

\begin{figure}[h]
	\centering
	\includegraphics[width = 0.5\linewidth]{fig/simpleexam}
	\caption{Graph $G$ consists of some subgraphs ($G_j$) with $s_j \leq 2$.}
	\label{fig:simpleexam}
\end{figure}

\begin{lem}
	\label{lem2}
	Let $X_1(k) \sim Bernouli (p_1)$ and $X_2(k) \sim Bernouli (p_2)$; then, there exists an obfuscated technique with an asymptotic noise level
	\[a_{12}= \frac{\abs{\cov(X_1(k), X_2(k))}}{\max \{p_1, p_2, 1-p_1, 1-p_2\}},\]
	for the dataset of user $1$ and user $2$ such that $Z_1(k)$ and $Z_2(k)$ are independent from each other.
\end{lem}

\begin{proof}
	We explain the idea behind this lemma by an example.
	\begin{example}
		Let $X_1(k) \sim \text{Bernouli} \left(\frac{3}{5}\right)$ and $X_2(k) \sim \text{Bernouli} \left(\frac{1}{5}\right)$, and let Table \ref{tab:mathfunc} show the joint probability mass function of $X_1(k)$ and $X_2(k)$.

		\begin{table}[ht]
			\caption{Joint probability mass function of $X_1(k)$ and $X_2(k)$.}
			\begin{center}
				\begin{tabular}{l|c|c}
					\backslashbox{$X_1(k)$}{$X_2(k)$} & $0$   & $1$ \\
					\hline
					$0$  & $\frac{7}{20}$& $\frac{1}{20}$ \\	\hline
					$1$  & $\frac{9}{20}$ & $\frac{3}{20}$  \\
				\end{tabular}
			\end{center}
			\label{tab:mathfunc}
		\end{table}
		As a result, if we observe $2000$ bits of data, Table \ref{tab:databits} shows the expected results according to Table \ref{tab:mathfunc}.

		\begin{table}[ht]
			\caption{Expected results of $X_1(k)$ and $X_2(k)$ according to Table \ref{tab:mathfunc} after observing $2000$ bits of data.}
			\begin{center}
				\begin{tabular}{l|c|c}
					\backslashbox{$X_1(k)$}{$X_2(k)$} & $0$   & $1$ \\
					\hline
					$0$  & $700$& $100$ \\	\hline
					$1$  & $900$ & $300$  \\
				\end{tabular}
			\end{center}
			\label{tab:databits}
		\end{table}

		Then, to make $Z_1(k)$ and $Z_2(k)$ independent, it is sufficient for $Z_1(k)|Z_2(k) =0$ to have the same distribution as $Z_1(k)|Z_2(k)=1 $. This means we should have
		\begin{align}
			\no \frac{P\left(Z_1(k)=1,Z_2(k)=1\right)}{P\left(Z_2(k)=1\right)}=\frac{P\left(Z_1(k)=1,Z_2(k)=0\right)}{P\left(Z_2(k)=0\right)};\ \
		\end{align}
thus, according to Table \ref{tab:databits2}, we should have
		\begin{table}[ht]
			\caption{The desired results to make $Z_1(k)$ and $Z_2(k)$ independent from each other.}
			\begin{center}
				\begin{tabular}{l|c|c}
					\backslashbox{$Z_1(k)$}{$Z_2(k)$} & $0$   & $1$ \\
					\hline
					$0$  & $700$& $175$ \\	\hline
					$1$  & $900$ & $225$  \\
				\end{tabular}
			\end{center}
			\label{tab:databits2}
		\end{table}
		\[\frac{300 (1-\Upsilon)}{100+300}=\frac{900}{700+900} \Rightarrow \Upsilon=\frac{1}{4},\]
		so we need to change $\frac{1}{4}\cdot 300=75$ of data bits. As a result, if $X_1(k)=1$ and $X_2(k)=1$, then we pass $X_1(k)$ through a $BSC(\frac{1}{4})$, and obtain $Z_1(k)$. As a result,
		\[\text{Asymptotic Noise level}= \frac{3}{20}\cdot\frac{1}{4}=3.75\%\]
		It is easy to check that the asymptotic noise level will be given by the equation in the lemma. Specifically, for the above example,
		\[\cov(X_1(k), X_2(k))=P(X_1(k)=1, X_2(k)=1)-P(X_1(k)=1)P(X_2(k)=1)=\frac{3}{20}-\frac{3}{5}\cdot\frac{1}{5}=\frac{3}{100},\]
		and we have
		\[\text{Asymptotic Noise level}=\frac{\cov(X_1(k), X_2(k))}{\max \{p_1, p_2, 1-p_1, 1-p_2\}} = \frac{\frac{3}{100}}{\frac{4}{5}}=3.75\%\]
	\end{example}

	Now, to prove the lemma, apply the above procedure to a general table for a probability mass function. Let $X_1(k) \sim \text{Bernouli} \left(p_1\right)$ and $X_2(k) \sim \text{Bernouli} \left(p_2\right)$. Then, to make this two sequences independent, it suffices if $Z_1|Z_2=0$ has same distributions as $Z_1(k)|Z_2(k)=1 $. We only prove for the case $\max \{p_1,p_2,1-p_1,1-p_2\}=1-p_2$, and the proofs of the other cases are similar to this one. Now, to make $Z_1(k)$ and $Z_2(k)$ independent, we will change $\Upsilon\times N$ data points: If $X_1(k)=1$ and $X_2(k)=1$, we pass $X_1(k)$ through a $BSC(\Upsilon)$ in order to obtain $Z_1(k)$. Thus,
	\[\frac{P\left(X_1(k)=1,X_2(k)=0\right) }{1-p_2}=\frac{P\left(X_1(k)=1,X_2(k)=1\right)(1-\Upsilon)}{p_2},\]
	so $\Upsilon$ can be calculated as
	\[\Upsilon=1-\frac{p_2}{1-p_2}\frac{P\left(X_1(k)=1,X_2(k)=0\right)}{P\left(X_1(k)=1,X_2(k)=1\right)}.\]
Now we can conclude,
\begin{align}
\no \text{Asymptotic}&\text{Noise level}=\Upsilon \cdot P\left(X_1(k)=1,X_2(k)=1\right)\\
\no &=\left(1-\frac{p_2}{1-p_2}\frac{P\left(X_1(k)=1,X_2(k)=0\right)}{P\left(X_1(k)=1,X_2(k)=1\right)}\right) P\left(X_1(k)=1,X_2(k)=1\right)\\
\no &= P\left(X_1(k)=1,X_2(k)=1\right)-\frac{p_2}{1-p_2}{P\left(X_1(k)=1,X_2(k)=0\right)}\\
\no &= \frac{P\left(X_1(k)=1,X_2(k)=1\right) -p_2\left(P\left(X_1(k)=1,X_2(k)=1\right)+P\left(X_1(k)=1,X_2(k)=0\right)\right)}{1-p_2}\\
\no &=\frac{P\left(X_1(k)=1,X_2(k)=1\right)-p_1p_2}{1-p_2}\\
\no &=\frac{P\left(X_1(k)=1,X_2(k)=1\right)-p_1p_2}{\max\{p_1,p_2,1-p_1,1-p_2\}}\\
\no &=\frac{\cov(X_1(k), X_2(k))}{\max\{p_1,p_2,1-p_1,1-p_2\}}. \ \
\end{align}

\end{proof}

Lemma \ref{lem2} provides a method to convert correlated data to independent traces. The remaining task is to show that we achieve perfect privacy after applying such a method. Consider $G(\mathcal{V},F)$, where $s_j \leq 2$.  We have the same model for $p_u$ as in previous sections: $p_u$ is chosen from some density $f_P(p)$ such that, for $\delta_1, \delta_2>0$:
\begin{equation}
\no\begin{cases}
\delta_1<f_P(p_u) <\delta_2, & p_u \in (0,1).\\
f_P(p_u)=0, &  p _u\notin (0,1).
\end{cases}
\end{equation}

Also if $(u,u') \in F$, $\rho_{uu'}$ is chosen according to some density $f_{P (\rho_{uu'} | p_u,p_{u'})}$ with range  of $\left[0, \min \left\{\sqrt{\frac{p_u(1-p_{u'})}{p_{u'}(1-p_{u})}}, \sqrt{\frac{p_{u'}(1-p_u)}{p_u(1-p_{u'})}}\right\}\right].$ The following theorem states that we can indeed achieve perfect privacy if we allow collaboration between users.

\begin{thm}
	\label{thm:noise}
	For the  two-states model, if ${\textbf{Z}}$ is the obfuscated version of $\textbf{X}$, ${\textbf{Y}}$ is the anonymized version of ${\textbf{Z}}$, and the size of all subgraphs are less than $2$, there exist an anonymization/obfuscation scheme such that for all $(u,u') \in F$, the asymptotic noise level for users $u$ and $u'$ is at most
	\[a_e(u,u')= \frac{\abs{\cov (X_u(k), X_{u'}(k))}}{\max \{p_u, p_{u'}, 1-p_u, 1-p_{u'}\}},\]
	to achieve perfect privacy for all users. The anonymization parameter $m=m(n)$ can be made arbitrarily large.
\end{thm}

\begin{proof}
	There are two main steps.

	Step $1$: De-correlate based on Lemma \ref{lem2}. In particular, note that for  at least half of the users, no noise is added in this step. More specifically, define
	\[\mathcal{U}= \text{Set of unaffected users} =\{u: \text{no noise is added to user } u \text{ in this step}\}.\]
Then after step $1$, we have $Z_u(k) \sim Bernouli (q_u)$. As a result,
	\begin{itemize}
		\item For $u \in \mathcal{U}$; $Z_u(k)=X_u(k)$ and $q_u=p_u.$
		\item For $u \in \{1, 2, \cdots, n\}-\mathcal{U}$; $Z_u(k)\neq X_u(k)$ and $q_u\neq p_u.$
	\end{itemize}
	Note $|\mathcal{U}| \geq \frac{n}{2}$, because the main graph consists of some subgraphs with $s_j\leq 2$.

	Step $2$: Assume $q_u$'s are known to the adversary. The set up is now very similar to Theorem $1$ in \cite{nazanin_ISIT2017}, where perfect privacy is proved for the i.i.d.\ data. But there is a difference here. Specifically, although the users' data $Z_u(k)$ are now independent, the distribution of $q_u$'s are not, since they are the result of the data-dependent obfuscation technique of Lemma \ref{lem2}. Luckily, this issue can be easily resolved, so that we can show perfect privacy for user $1$. The main idea is to use the fact that as stated above, at least $\frac{n}{2}$ of the users are not impacted by the de-correlation step. As we see below, these users will be sufficient to ensure perfect privacy for user $1$ (which may or may not be in the set $\mathcal{U}$).

Let's explore the distributions of $Q_u=q_u$ for users in the set $\mathcal{U}$. For any correlated pair of users, the method of Lemma \ref{lem2} leaves the one whose $p_u$ is farthest from $\frac{1}{2}$ intact. Since $p_u$'s are chosen independently from each other and each user is correlated with only one user, it is easy to see that for users in the set $\mathcal{U}$, the $Q_u$'s are i.i.d.\ with the following probability density function
\[f_{Q'}(q')=2 f_P(q') \int_{\min(q',1-q')}^{\max(q',1-q')} f_P(x) dx. \]
Therefore, the setup is the same as Theorem $1$ in \cite{nazanin_ISIT2017} where we want to prove perfect privacy for user $1$, and we have $\frac{n}{2}$ users who are independent from user $1$ and their parameter $q'_u$ is chosen i.i.d.\ according to a density function. However, there is a small problem. We need to check that the density function $f_{Q'}(q')$ satisfies the condition $\delta_1' <f_{Q'}(q')<\delta_2'$ for some $\delta_1'$ and $\delta_2'$ on a neighborhood $q' \in [p_1-\epsilon',p_1+\epsilon']$.
First, note that
\begin{align*}
 f_{Q'}(q') &=2 f_P(q') \int_{\min(q',1-q')}^{\max(q',1-q')} f_P(x) dx. \\
  & < 2 \delta_2^2=\delta'_2.
\end{align*}
Next,
\begin{align*}
 f_{Q'}(q') &=2 f_P(q') \int_{\min(q',1-q')}^{\max(q',1-q')} f_P(x) dx. \\
  & > 2 \delta_1^2 |1-2q'|=\delta'_1.
\end{align*}
Thus, as long as $p_1 \neq \frac{1}{2}$, the condition is satisfied \footnote{The case $p_1 = \frac{1}{2}$ has zero probability, and thus need not be considered. Nevertheless, the result can be shown for $p_1=\frac{1}{2}$, as all we require is a number of users proportional to the length of the interval in the vicinity of $p_1$.}. Therefore, we can show perfect privacy for user $1$. Note that here, in the second step we need to apply a second stage of obfuscation and apply anonymization according to Theorem $1$ in \cite{nazanin_ISIT2017}. Nevertheless, since the noise level $a_n \rightarrow 0$ for this second stage, the asymptotic noise level will stay the same as that for step $1$, i.e.
\[\frac{\abs{\cov (X_u(k), X_{u'}(k))}}{\max \{p_u, p_{u'}, 1-p_u, 1-p_{u'}\}}.\]
\end{proof}

Now, the above method can be extended to the case where $s_j>2$. Let $s_j=3$. From Figure \ref{Sj=3}, there are three different situations in this case:
\begin{enumerate}
	\item Case $1$: As shown in Figure \ref{Sj_case1}, only user $1$ and user $2$ are correlated to each other, so we de-correlate them based on Lemma \ref{lem2}. Then, Theorem \ref{thm:noise} will be applied to achieve perfect privacy for them.
	\item Case $2$: As shown in Figure \ref{Sj_case2}, user $1$ and user $2$ are correlated, and user $2$ and user $3$ are correlated. In the first step, we de-correlate user $2$ and user $3$ based on Lemma \ref{lem2}. Now, we face a similar situation as that in case $1$. Hence, we can make all of the users independent from each other and then according to Theorem \ref{thm:noise}, we can achieve perfect privacy for all of them.
	\item Case $3$: As shown in Figure \ref{Sj_case3}, all three users are correlated to each other. In the first step, we use Lemma \ref{lem2} to make user $1$ and user $3$ uncorrelated. Now, we have a similar situation as case $2$, so we can make all the users independent from each other and then, according to Theorem \ref{thm:noise}, we can achieve perfect privacy for all of them.
\end{enumerate}
\begin{figure*}[t!]
	\centering
	\subfloat[Case $1$.]{
		\includegraphics[width=0.23\columnwidth]{fig/Sj_case1}
		\label{Sj_case1}
	}
	\subfloat[Case $2$.]{
		\includegraphics[width=0.23\columnwidth]{fig/Sj_case2}
		\label{Sj_case2}
	}
	\subfloat[Case $3$.]{
	\includegraphics[width=0.23\columnwidth]{fig/Sj_case3}
	\label{Sj_case3}
}
	\caption{Three different ways which $3$ users can be correlated to each other.}
	\label{Sj=3}
\end{figure*}


TITLE: $\frac{1}{\sin^2(t)}\frac{d}{dt}\sin^2(t)\frac{d}{dt}f=-k(k+2)f$
QUESTION [0 upvotes]: I'm trying to solve the differential equation $$\frac{1}{\sin^2(t)}\frac{d}{dt}\left(\sin^2(t)\frac{d}{dt}f\right)=-k(k+2)f.$$ I know that (multiples of) $\frac{\sin((k+1)t)}{\sin(t)}$ are a solution but there have to be more solutions than this since the differential equation is of order two or am I wrong here?
Thanks in advance.

REPLY [2 votes]: Another linearly independent solution is
$$
\frac{\cos((k+1)t)}{\sin(t)}.
$$
You can find it using the method of reduction of order. The change
$$
f(x)=\frac{\sin((k+1)t)}{\sin(t)}\,g(x)
$$
will lead to a first order equation.
Another possibility is the change
$$
g(t)=\frac{f(t)}{\sin t},
$$
which leads to a second order equation with constant coefficients.


TITLE: A regularity question on the Beltrami equation $ f_\bar{z} =\mu . f_z$ on $D$
QUESTION [4 upvotes]: Hello,
This question is related to Chapter V, lemma 3 on page 54 of Lars Ahlfors'    'Lectures on Quasiconformal mappings' which states :
If $\mu:\mathbb{C}\to \mathbb{D}  \in W^{1,p}(\mathbb{C}), p > 2 $ is fixed and sufficiently close to 2 ( because of Calderon-Zygmund theorem used in in the proof of the measurable Riemann Mapping Theorem ), $ L^{\infty} $ norm of $ \mu \le  \frac{k-1}{k+1}, k> 0 $ then the solution to the Beltrami equation $f_\bar{z}= \mu . f_z$ is a $\mathcal{C^1}$ diffeomorphism of the complex plane $ \mathbb{C} $.
The above lemma is part of the proof of the measurable Riemann mapping theorem, which generalizes the above lemma with $\mu \in L^\infty(\mathbb{C})$.
I have two questions regarding the above lemma :
1) I went through the proof of the lemma, and it seems like we don't need $\mu$ to be compactly supported.Do we ? [ The reason I am asking is the theorem 1 on page 54 is assumes $\mu$ to be compactly supported and they really use it. Also,you look some other book, e.g. : Imayosgi-Taniguchi's Techmuller Theory , chapter 4, Theorem 4.25, they use the phrase "under the same circumstances of theorem 4.24", which mean they want $\mu$ to be compactly supported, which I don't see why ]
2) Is the following true ? ( I am basically replacing the domain $\mathbb{C}$  by $\mathbb{D}$)
If $\mu:\mathbb{D}\to \mathbb{D}  \in W^{1,p}(\mathbb{D}), p > 2 $ and also real-analytic in $\mathbb{D}$, then any solution to the Beltrami equation $f_\bar{z}= \mu . f_z$ is a $\mathcal{C^1}$ diffeomorphism of the open unit disk $ \mathbb{D} $ and also
$ f \in C^1({\bar{\mathbb{D} }}) $
 [ the last condition is crucial ].
I was trying to answer question no 2 by assuming the following, which might not be correct :
If $\mu \in W^{1,p}(\mathbb{D})$ , then it is Holder continuous on ${\mathbb{D}}$ with Holder exponent $1- \frac{2}{p} $ ( well, I am not assuming this,it follows from the theory of Sobolev Spaces, see Evans' PDE book for example ) and hence is uniformly continuous on $\bar{\mathbb{D} }$.
( probably correct/incorrect ) assumption : Then there exists $ g\in C^\infty(D_2)$ such that $g|_{S^1}= \mu | _{S^1},g \in W^{1,3}(D_2)  $ . $D_2$ denotes the ball with radius $2$, centered at $0$.
The reason I was doing this is to transfer the problem to a Beltrami equation on $ \mathbb{C} $, by extending the Beltrami coefficient from $\mathbb{D}$ to $\mathbb{C}$ and the reason I want $L^3$ is that for a finite measure space ( balls of finite radius ) $ L^3 \subset L^p  \forall p \le  3 $
Any hints or suggestions or detailed answers for question # 2 ? Thank you !

REPLY [1 votes]: The most comprehensive source for the Beltrami equation in the plane is the book listed below and you should search it for the answers to your questions.
K.Astala, T.Iwaniec, G.Martin,
Elliptic partial differential equations and quasiconformal mappings in the plane.
Princeton Mathematical Series, 48. Princeton University Press, Princeton, NJ, 2009.