Proof. Let \(W=(W_i)_{i\in[n]}\) be the purported mechanism, with \(W_i\colon {\cal X}\to{\cal Y}\) being the mapping of the \(i\)-th user. We create a symmetric (randomized) mechanism \(\tilde{W}\colon{\cal X}\to[n]\times{\cal Y}\) as follows: On input \(x\in{\cal X}\), use private (respectively public) randomness to generate \(I\in[n]\) uniformly at random (and independently of everything else); and output \((I, W_I(x))\).⁷

Clearly, the resulting mechanism is symmetric. Further, by a standard coupon-collector argument, for \(n'=O(n\log n)\) we have that with probability at least \(5/6\), each \(i\in[n]\) will be drawn at least once. Whenever this is the case, upon gathering all the outputs, the referee can then select a subset of \(n\) outputs and simulate the original mechanism, having received the output of \(W_1,\dots, W_n\). Overall, the probability of failure is at most \(1/6+1/6=1/3\) by a union bound. ◻

Proof. Recall from 1 that an \(\varepsilon\)-LDP RR is described by the channel \(W_{\mathrm{\small RR}}(0\mid 0)=W(1\mid 1) = \frac{e^\varepsilon}{e^\varepsilon+1}\). When a \(\operatorname{Bern}\mleft( \rho \mright)\) random variable passes through this channel, the output is a Bernoulli random variable with mean \[\rho' :=\rho\frac{e^\varepsilon}{e^\varepsilon+1}+(1-\rho)\frac{1}{e^\varepsilon+1} = \frac{1}{e^\varepsilon+1} + \rho \frac{e^\varepsilon-1}{e^\varepsilon+1}.\] Therefore, estimating \(\rho\) to \(\pm\gamma\) using this mechanism is equivalent to estimating \(\rho'\) to an additive \(\gamma':= \frac{e^\varepsilon+1}{e^\varepsilon-1}\gamma\), which can be done with \(O(1/{\gamma'}^2) = O(1/(\gamma^2\varepsilon^2))\) samples (the second as \(\varepsilon \lesssim 1\)).

It remains to prove optimality. For \(k=2\), it can shown that any \(\varepsilon\)-LDP scheme can be obtained by passing output of an \(\varepsilon\)-LDP RR through another channel. Therefore, RR will require the least number of samples for estimating the bias, and it suffices to show the claimed bound of \(\Omega\!\left(1/(\gamma^2\varepsilon^2)\right)\) for RR. To that end, suppose we provide as input a Bernoulli random variable with bias \(1/2+\gamma\) to RR. Then, the output has bias \(\frac{1}{2} +\gamma\frac{e^\varepsilon-1}{e^\varepsilon+1} = \frac{1}{2}+O(\gamma\varepsilon)\). On the other hand, when the input is \(\operatorname{Bern}\mleft( 1/2 \mright)\), then the output is \(\operatorname{Bern}\mleft( 1/2 \mright)\) as well. Therefore, distinguishing between a \(\operatorname{Bern}\mleft( 1/2 \mright)\) and a \(\operatorname{Bern}\mleft( 1/2+\gamma \mright)\) using samples from an \(\varepsilon\)-LDP RR is at least as hard as distinguishing \(\operatorname{Bern}\mleft( 1/2 \mright)\) and \(\operatorname{Bern}\mleft( 1/2 +O(\gamma\varepsilon) \mright)\) without privacy constraints. This latter task is known to require the stated number of samples. ◻

Proof. Consider a distribution \(p\) over \(\{0,1\} \times \{0,1\}\) with marginals \(p_1\) and \(p_2\). Note that \[\left\lvert p(0,0)-p_1(0)p_2(0)|=|p(x,y)-p_1(x)p_2(y) \right\rvert, \quad x,y\in \{0,1\}.\] Thus, if \(p\) is \(\gamma\)-far in total variation distance from any product distribution, it must hold that \({\operatorname{d}_{\rm TV}^{}\!\left({p, p_1\otimes p_2}\right)}\geq \gamma\), which in view of the equation above yields \(|p(0,0)-p_1(0)p_2(0)|\geq \gamma/2\). Using this observation, we can test for independence using \(O(1/(\varepsilon^2\gamma^2))\) samples as follows. First, note that for any symbol \(x\), \(p(x)\) can be estimated up to an accuracy \(\gamma\) using \(O(1/(\varepsilon^2\gamma^2))\) samples by converting the observation \(X\) to the binary observation \(\mathbb{1}_{\left\{X=x\right\}}\) and applying the estimator of 2. Thus, we can estimate \(p(0,0)\), \(p_1(0)\), and \(p_2(0)\) up to an accuracy \(\gamma/16\) by assigning \(O(1/(\varepsilon^2\gamma^2))\) samples each for them. Denote the respective estimates by \(\tilde{p}(0,0)\), \(\tilde{p}_1(0)\), and \(\tilde{p}_2(0)\). When \(p(0,0)=p_1(0)p_2(0)\), \[|\tilde{p}(0,0)-\tilde{p}_1(0)\tilde{p}_2(0)|\leq |\tilde{p}(0,0)-p(0,0)|+ \tilde{p}_1(0)-p_1(0)|+ |\tilde{p}_2(0)-p_2(0)| \leq \frac{3}{16} \gamma.\] On the other hand, when \(|p(0,0)-p_1(0)p_2(0)|\geq \gamma/2\), we have \[|\tilde{p}(0,0)-\tilde{p}_1(0)\tilde{p}_2(0)| \geq |p(0,0)-p_1(0)p_2(0)|- |\tilde{p}(0,0)-p(0,0)|- |\tilde{p}_1(0)-p_1(0)|- |\tilde{p}_2(0)-p_2(0)| \geq \frac{5}{16}\gamma.\] Thus, for \(k=2\), locally private independence testing can be performed with \(O(1/(\varepsilon^2\gamma^2))\) samples by estimating the probabilities \(p(0,0)\), \(p_1(0)\), \(p_2(0)\) and comparing \(\left\lvert \tilde{p}(0,0)-\tilde{p}_1(0)\tilde{p}_2(0) \right\rvert\) to the threshold \(\gamma/4\). ◻

Proof of 2. Clearly, since Rappor is an \(\varepsilon\)-LDP mechanism, the overall 4 does not violate the \(\varepsilon\)-LDP constraint. We now analyze the error performance of the proposed test, which we will do simply by using Chebyshev’s inequality. Towards that, we evaluate the expected value and the variance of \(T\).

The following evaluation of expected value of statistic \(T\) uses a simple calculation entailing moments of a Binomial random variable:

Turning to the variance, we get the following:

The proof of this lemma is quite technical and relies on a tedious analysis of the covariance of the random variables \((N_x)_{x\in[k]}\), in view of bounding quantities of the form \(\operatorname{Cov}(f(N_x), f(N_y))\). We defer the details to 8.

With these two lemmata, we are in a position to conclude the argument. Suppose \(n\geq C\cdot \frac{k^{3/2}}{\alpha_{R}^2\gamma^2}\), for some constant \(C>0\) to be specified later. Recall that \(\alpha_{R} = \varepsilon/4+o(\varepsilon)\) when \(\varepsilon\to 0\), leading to the claimed sample complexity.

First, consider the case when \(p=u\). In this case \(\mathbb{E}\mleft[T\mright]=0\) and \(\operatorname{Var}\mleft(T\mright)\leq 4kn^2\) by 3 4, and so by Chebyshev’s inequality \[\Pr\mleft[\, T \geq n^2\frac{\alpha_{R}^2\gamma^2}{k} \, \mright] \leq \frac{ k^2\operatorname{Var}\mleft(T\mright) }{ n^4\alpha_{R}^4\gamma^4 } \leq \frac{17k^3}{8n^2\alpha_{R}^4\gamma^4} < \frac{3}{C^2}\] which is at most \(1/3\) for \(C\geq 3\).

Next, when \({\operatorname{d}_{\rm TV}^{}\!\left({p, u}\right)}>\gamma\), \(\mathbb{E}\mleft[T\mright]>2n^2\frac{\alpha_{R}^2\gamma^2}{k}\) and \(\operatorname{Var}\mleft(T\mright)\leq 4kn^2 + 8n\mathbb{E}\mleft[T\mright]\), and again by Chebyshev’s inequality \[\Pr\mleft[\, T < n^2\frac{\alpha_{R}^2\gamma^2}{k} \, \mright] \leq \Pr\mleft[\, T < \frac{1}{2}\mathbb{E}\mleft[T\mright] \, \mright] \leq \frac{ 4\operatorname{Var}\mleft(T\mright) }{ \mathbb{E}\mleft[T\mright]^2 } \leq \frac{17k^3}{2n^2\alpha_{R}^4\gamma^4} + \frac{10k}{n\alpha_{R}^2\gamma^2} \leq \frac{17}{2C^2} + \frac{10}{C\sqrt{k}}\] which is at most \(1/3\) for \(C\geq 23\). Taking \(C = 23\) concludes the proof of 2. ◻

Proof of 4. For any \(z\in[K]\), let \(D_z\subseteq[k]\) be the set of symbols \(x\) such that \(z\in C_x\). Then, from 3 (recalling that \(s=K/2\)) we get \[\begin{align} q(z) &= \sum_{x\in D_z} W(z\mid x)p(x) + \sum_{x\in D_z} W(z\mid x)p(x) \nonumber \\ &= \frac{1}{s}\left( p(D_z) \frac{e^\varepsilon}{e^\varepsilon+1} + p(D_z^c) \frac{1}{e^\varepsilon+1} \right) +\frac{1}{K}\cdot\frac{e^\varepsilon-1}{e^\varepsilon+1}\cdot\left(p(D_z)-p(D_z^c)\right) \nonumber \\ &=\frac{1}{K} + \frac{\alpha_{H}}{K}\left(2p(D_z)-1\right)\,. \label{eq:expression:output} \end{align}\tag{9}\] Define \(q^\ast\in\Delta\mleft([K]\mright)\) as \[\label{eq:def:qast} q^\ast(z) :=\frac{1}{K} + \frac{\alpha_{H}}{K}\left(\frac{2\left\lvert D_z \right\rvert}{k}-1\right), \quad \forall z\in[K],\tag{10}\] so that \(q^\ast(z) \in [(1-\alpha_{H})/K, (1+\alpha_{H})/K]\) for every \(z\) and \({\lVert q^\ast{\rVert}}_2 \leq (1+\alpha_{H})/\sqrt{K}\). From 9 10 , we get \[\label{eq:normtwo:q:expression} {\lVert q-q^\ast{\rVert}}_2^2 = \sum_{z\in[K]}\left(q(z) -q^\ast(z)\right)^2 = \frac{4\alpha_{H}^2}{K^2}\sum_{z\in[K]} \left( p(D_z)-\frac{\left\lvert D_z \right\rvert}{k} \right)^2.\tag{11}\]

Note that we may view a probability distribution \(p\in\Delta\mleft([k]\mright)\) as a function \(\boldsymbol{p}\colon \{0,1\}^k\to \mathbb{R}\) with \[\boldsymbol{p}(s) = p(S) = \sum_{x\in S} p(x), \quad \forall s\in\{0,1\}^k,\] where we identify \(s\in\{0,1\}^k\) with the subset \(S= \left\{\; x\in[k] \;\colon\; s_x = 1\; \right\} \subseteq [k]\) and use the two notations interchangeably. Also, from [fact:hadamard:fourier] and the definition of the \(C_x\) as sets encoded by the rows of the matrix \(H_K\), we have that \[\chi_{\phi(x)}(z) = (H_K)_{\phi(x),z} = 2\mathbb{1}_{\left\{z\in C_x\right\}} - 1, \quad \forall\, z\in[K], x\in[k],\] whereby \[\sum_{x\in[k]} \left( p(x) - \frac{1}{k} \right)\chi_{\phi(x)}(z) = 2\left( p(D_z)-\frac{\left\lvert D_z \right\rvert}{k} \right), \quad \forall\, z\in[K].\] Now, consider the function \(g\colon [K]\to \mathbb{R}\) defined by \(g(z) = 2\left( p(D_z)-\left\lvert D_z \right\rvert/k\right)\),¹¹. Using the previous equation, we can view \(g\) alternatively as \[g(z) = \sum_{T\in\phi([k])}\left( p( \phi^{-1}(T) ) - \frac{1}{k} \right)\chi_T(z), \quad \forall\, z\in[K].\] Therefore, \[\hat{g}(T) = \sum_{x\in[k]}\left( p(x) - 1/k\right)\mathbb{1}_{\left\{T=\phi(x)\right\}}, \quad \forall\, T\in[K],\] which by Parseval’s theorem (1) gives \[\begin{align} \nonumber \frac{4}{K}\sum_{z\in[K]} \left( p(D_z)-\frac{\left\lvert D_z \right\rvert}{k} \right)^2 = \lVert g{\rVert}^2 = \sum_{T\in [K]} \hat{g}(T)^2 = \sum_{x\in[k]} \left( p(x) - \frac{1}{k} \right)^2 = {\lVert p-u{\rVert}}_2^2\,. \end{align}\] The identity above, together with 11 , yields \[{\lVert q-q^\ast{\rVert}}_2^2 = \frac{\alpha_{H}^2}{K}{\lVert p-u{\rVert}}_2^2\,.\] The claimed result then follows from the fact that \(\alpha_{H}=\frac{\varepsilon}{2}+o(\varepsilon)\). ◻

Proof. Let \(Y_1, \dots, Y_k\) be independent random bits, and let \(X_1, \dots, X_k\) be obtained by conditioning \((Y_1, \dots, Y_k)\) on the event \(\sum_{i\in [k]}X_i = k/2\). Consider the random set \(S\) defined as \[S = \left\{\; i\in[k] \;\colon\; X_i =1\; \right\} .\] Letting \(\delta :=p- u\), we have \[p(S) - u(S) = p(S) - \frac{1}{2} = \sum_{i\in[k]}\delta_iX_i.\] Note that \(\mathbb{E}\mleft[X_1^2\mright] = \mathbb{E}\mleft[X_1^4\mright] =1/2\). Also, \[\begin{align} \mathbb{E}\mleft[X_1X_2\mright] &= \frac{1}{2} \Pr\mleft[\, X_2=1 \;\middle\vert\; X_1=1\, \mright] \\ &= \frac{1}{2} \Pr\mleft[\, Y_2=1 \;\middle\vert\; Y_1=1, \sum_{i=1}^kY_i =\frac{k}{2} \, \mright] \\ &= \frac{1}{2} \Pr\mleft[\, Y_2=1 \;\middle\vert\; \sum_{i=2}^kY_i =\left(\frac{k}{2} -1\right)\, \mright] \\ &= \frac{1}{2} \mathbb{E}\mleft[\, Y_2 \;\middle\vert\; \sum_{i=2}^kY_i =\left(\frac{k}{2} -1\right)\, \mright] \end{align}\] which by symmetry yields \[\mathbb{E}\mleft[X_1X_2\mright] = \frac{1}{2} \mathbb{E}\mleft[\, Y_j \;\middle\vert\; \sum_{i=2}^kY_i =\left(\frac{k}{2} -1\right)\, \mright], \quad \forall\, 2\leq j\leq k.\] Taking the average of the right-side, we get \[\mathbb{E}\mleft[X_1X_2\mright] = \frac{1}{2(k-1)} \mathbb{E}\mleft[\, \sum_{j=2}^kY_j \;\middle\vert\; \sum_{i=2}^k Y_i =\left(\frac{k}{2} -1\right)\, \mright] =\frac{(k -2)}{4(k-1)} \leq \frac{1}{4}.\] Finally, note that \[{\lVert\delta{\rVert}}_2^2 \geq \frac{1}{k} {\lVert\delta{\rVert}}_1^2 \geq \frac{4\gamma^2}{k},\] so that, applying 6 to \(Z = \sum_{i=1}^k\delta_i X_i\) with \(\alpha :=1/477\) we get \[\Pr\mleft[\, Z^2 >\frac{\gamma^2}{5k}\, \mright] \geq \frac{1}{477},\] which completes the proof. ◻

Proof of 7. The proof of correctness follows the foregoing outline, which we describe in more detail. Let \(c:=1/477\) be the constant from 2, and let \(\delta :=\frac{c}{2(1+c)}\), and set \(\gamma' :=\frac{\gamma}{\sqrt{5k}}\). By a standard amplification argument,¹⁶ one can amplify the success probability of the private estimation procedure of 2 to \(1-\delta\), using a total of \(O(\log(1/\delta)/({\gamma'}^2\varepsilon^2))=O(1/({\gamma'}^2\varepsilon^2))\) samples (to achieve privacy \(\varepsilon\) and accuracy \(\gamma'\)).

Consider the \(t\)-th test from 6 (where \(1\leq t\leq T\)), and let \(b_t\) be the indicator that the bias estimation outputs unbiased. If \(p\) is uniform, then by the above we have \(\Pr\mleft[\, b_t = 1 \, \mright] \geq 1- \delta\) (where the probability is over the choice of the random subset \(S_t\), and the randomness of the bias estimation). However, if \(p\) is \(\gamma\)-far from uniform, by 2 it it the case that \(\Pr\mleft[\, b_t = 1 \, \mright] \leq (1-c) + c\delta = 1- (\delta+\frac{c}{2})\). Therefore, for a sufficiently large constant in the choice of \(T = \Theta(1/c^2) = \Theta(1)\), a Chernoff bound argument ensures that we can distinguish between these two cases with probability at least \(2/3\). ◻

Proof. Our lower bound relies on analyzing the standard “Paninski construction” [20], which we briefly recall. Assuming without loss of generality that \(k\) is even, we partition the domain in \(k/2\) consecutive pairs \((2i-1,2i)\). For a given parameter \(\gamma\in(0,1/2]\), the family of “no-instances” is the collection of \(2^{k/2}\) distributions \((p_{\theta})_{\theta\in\{-1,+1\}^{k/2}}\) where \[p_{\theta}(2i-1) = \frac{1+2\theta_i\gamma}{k}, \qquad p_{\theta}(2i) = \frac{1-2\theta_i\gamma}{k}, \qquad i\in[k/2]\,.\] Note that every such \(p_\theta\) is a total variation exactly \(\gamma\) from the uniform distribution on \([k]\).

Our starting point will be the proof of the public-coin lower bound of [19] for uniformity testing in a (non-private) distributed setting. Note that the proof in [19] proceeds by noting that once we restrict our attention to the hypothesis testing problem implied by Paninski’s construction, we can derandomize and find a deterministic protocol that outperforms the public-coin protocol. Therefore, it suffices to bound the performance of deterministic protocols. However, in our current application, relaxing to deterministic protocols will get rid of local privacy constraints and will not lead to useful bounds. Instead, we note in similar vein as the proof in [19] that we can derandomize public randomness and find a private-coin \(\varepsilon\)-LDP protocol that achieves the same performance for Paninski’s construction as the public-coin protocol we start with. Therefore, it suffices to restrict our attention to private-coin protocols.

Let \(W\) be an arbitrary \(\varepsilon\)-LDP private-coin mechanism for uniformity testing. For \(1\leq j\leq n\) and \(\theta,\theta'\in\{-1, +1\}^{k/2}\), define \(H_j(\theta, \theta')\) as \[\begin{align} H_j(\theta, \theta') &:=\frac{\gamma^2}{k} \sum_{m}\sum_{i_1,i_2\in [k/2]}\theta_{i_1}\theta'_{i_2} \frac{ \left( W_j(m \mid 2i_1-1)-W_j(m \mid 2i_1) \right) \left( W_j(m \mid 2i_2-1)-W_j(m \mid 2i_2) \right)}{ \sum_{i=1}^{k} W_j(m \mid i)}\,. \end{align}\] where \(m\in(\{0,1\}^\ast)^n\) denotes the tuple of outputs from the \(n\) users. Let \[\bar{W}_j(m) :=\frac{1}{k} \sum_{i=1}^{k} W_j(m \mid i)\] \(i.e.\), \(\bar{W}_j(m)\) is the probability of user \(j\) outputting \(m\) when the input distribution is uniform. Let \(\delta_{i,j}^m\) be such that \[W_j(m \mid 2i-1)-W_j(m \mid 2i)= \bar{W}_j(m) \delta_{i,j}^m.\] Then by the conditions for LDP, we must have \[\begin{align} \left\lvert \delta_{i,j}^m \right\rvert\leq e^\varepsilon-1\,. \end{align}\] Furthermore, we can rewrite \[\begin{align} H_j(\theta, \theta') &= \frac{\gamma^2}{k^2} \sum_{m}\sum_{i_1,i_2\in [k/2]}\theta_{i_1}\theta'_{i_2}{\bar{W}_j(m)\delta_{i_1,j}^m\delta_{i_2,j}^m} = \sum_{i_1,i_2\in [k/2]}\theta_{i_1}\theta'_{i_2}\left(\frac{\gamma^2}{k^2}\sum_{m}\bar{W}_j(m)\delta_{i_1,j}^m\delta_{i_2,j}^m\right)\\ &= \frac{\gamma^2}{k^2}\theta^T \mathbf{H}_j \theta', \end{align}\] where \(\mathbf{H}_j\) is an \([k/2]\times [k/2]\) matrix with \((i_1, i_2)\)th entry equal to \[\mathbf{H}_j(i_1, i_2) :={\sum_{m}\bar{W}_j(m)\delta_{i_1,j}^m\delta_{i_2,j}^m}\,.\] By using that \(\sum_m \bar{W}_j(m) = 1\), we further get that \[\left\lvert \mathbf{H}_j(i_1, i_2) \right\rvert \leq \left(e^\varepsilon-1\right)^2\,.\] For a given distribution \(p\in\Delta\mleft([k]\mright)\), denote by \(\mathcal{W}(p)\in\Delta\mleft((\{0,1\}^\ast)^n\mright)\) the product distribution over \(m\) (the tuple of \(n\) messages) when each user gets an independent sample from \(p\). In [19], it is shown that, with \(n\) users, the \(\chi^2\) distance between the distributions of (i) the output of the mechanism under the Paninski mixture, \(\mathcal{W}^{{\sf{}no}} :=\frac{1}{2^{k/2}}\sum_{\theta} \mathcal{W}(p_\theta)\), and (ii) the output of the mechanism under the uniform distribution \(\mathcal{W}^{\sf{}yes}:=\mathcal{W}(u)\), is bounded by \[\begin{align} \mathbb{E}_{\theta, \theta'}\left(\exp\left(\sum_{j=1}^nH_j(\theta, \theta')\right)\right)-1 =\mathbb{E}_{\theta, \theta'}\left(\exp\left(\frac{\gamma^2}{k^2}\theta^T (\sum_{j=1}^n\mathbf{H}_j)\theta'\right)\right)-1\,. \end{align}\] We will also rely on the following technical claim:

Using this claim, and choosing \(\lambda :=\frac{\gamma^2}{k^2}\) we obtain the following upper bound on the distance between the distributions of the output of the mechanisms in the two cases: \[\begin{align} {\operatorname{d}_{\rm TV}^{}\!\left({\mathcal{W}^{\sf{}no}, \mathcal{W}^{\sf{}yes}}\right)} &\leq \exp\left(\frac{\gamma^4}{k^4}\lVert\sum_{j=1}^n\mathbf{H}_j{\rVert}_F^2\right)-1 \leq \exp\left(\frac{\gamma^4}{k^4}n\left(\sum_{j=1}^n\lVert\mathbf{H}_j{\rVert}_F^2\right)\right)-1\\ &\leq \exp\left(\frac{\gamma^4 n^2}{k^4}\left((k/2)^2 \left(e^\varepsilon-1\right)^4\right)\right)-1 \leq \exp\left(\frac{\gamma^4 n^2}{4k^2}\left(e^\varepsilon-1\right)^4\right)-1\,. \end{align}\] This implies the claimed lower bound by a standard application of Le Cam’s two-point method (as e.g. detailed by Pollard [37]), as one must have \(n= \Omega(k/(\varepsilon^2\gamma^2))\) for the RHS to be \(\Omega(1)\). ◻

Proof. We once again take recourse to Pollard’s recipe and proceed as in the proof of 8. Denote by \(W\colon [k] \to \{0,1\}^k\) the channel from the input to the output of Rappor. Letting for conciseness \(q_\varepsilon:=e^\varepsilon/(1+e^\varepsilon)\), we first observe that for any observation \(i\in [k]\) one has \[\begin{align} W(m\mid i) &= \left(m_i q_\varepsilon+ (1-m_i)(1-q_\varepsilon)\right)\cdot q_\varepsilon^{\left\lvert \left\{\; \ell \;\colon\; \ell \neq i, m_\ell =0\; \right\} \right\rvert} (1-q_\varepsilon)^{\left\lvert \left\{\; \ell \;\colon\; \ell \neq i, m_\ell =1\; \right\} \right\rvert} \\ &= m_i q_\varepsilon^{m(0)+1}(1-q_\varepsilon)^{m(1)-1} + (1-m_i) q_\varepsilon^{m(0)-1}(1-q_\varepsilon)^{m(1)+1}, \end{align}\] where \(m(0)\) and \(m(1)\), respectively, denote the number of \(0\)’s and \(1\)’s in \(m\). As was seen in the previous proof of lower bound, for our purpose, we need to evaluate \(\sum_{i \in [k]}W(m\mid i)\) and \(W(m\mid i) - W(m\mid i')\). For the former quantity, we have \[\begin{align} \sum_{i\in [k]}W(m\mid i) &= q_\varepsilon^{m(0)}(1-q_\varepsilon)^{m(1)} \left(m(1) \frac{q_\varepsilon}{1-q_\varepsilon} + m(0) \frac{1-q_\varepsilon}{q_\varepsilon}\right). \end{align}\] For the latter, we have \[\begin{align} W(m\mid i) - W(m\mid i')&= q_\varepsilon^{m(0)}(1-q_\varepsilon)^{m(1)} (m_i - m_{i'})\left(\frac{q_\varepsilon}{1-q_\varepsilon} - \frac{1-q_\varepsilon}{q_\varepsilon}\right). \end{align}\] We are now in a position to prove the lower bound. We are considering protocols where each sample \(X_j\) is reported to the center using Rappor, and so, each sample is reported using the same channel \(W\) described above. Therefore, the \(k\times k\) matrix \(\mathbf{H}_j\) used in the previous proof does not depend on \(j\) and satisfies \[\begin{align} \mathbf{H}(i_1, i_2) :=\mathbf{H}_j(i_1, i_2) &= k\sum_{m}\frac{ \left( W(m|2i_1-1)-W(m|2i_1) \right) \left( W(m|2i_2-1)-W(m|2i_2) \right)}{ \sum_{i=1}^{k} W(m\mid i)}. \end{align}\] It follows that \[\begin{align} \mathbf{H}(i_1, i_2) &= k\cdot \frac{(e^{2\varepsilon} -1 )^2}{e^{\varepsilon}} \cdot \sum_{m} q_\varepsilon^{m(0)}(1-q_\varepsilon)^{m(1)}\cdot \frac{(m_{2i_1 - 1} - m_{2i_1}) (m_{2i_2 - 1} - m_{2i_2})}{m(1)e^{2\varepsilon}+ m(0)}. \end{align}\] The key observation that facilitates our bound is that for \(i_1\neq i_2\), the sum on the right-side is \(0\). Indeed, consider the set of messages of fixed type, namely those with \(m(0)\) and \(m(1)\) fixed. Note that in any such set, only messages with \(m_{2i_1}\neq m_{2i_1-1}\) and \(m_{2i_2}\neq m_{2i_2-1}\) contribute to the sum. Furthermore, for any fixed \(m_{2i_2}\neq m_{2i_2-1}\), the contributions corresponding to \(m_{2i_1}=1, m_{2i_1-1}=0\) and \(m_{2i_1}=0, m_{2i_1-1}=1\) negate each other when \(i_1\neq i_2\), whereby the overall sum is \(0\). Thus, we have \[\begin{align} \mathbf{H}(i_1, i_2)&=\mathbb{1}_{\left\{i_1=i_2\right\}} \frac{k(e^{2\varepsilon} -1 )^2}{e^{\varepsilon}} \cdot \sum_{m} q_\varepsilon^{m(0)}(1-q_\varepsilon)^{m(1)}\cdot \frac{|m_{2i_1 - 1} - m_{2i_1}|^2 }{m(1)e^{2\varepsilon}+ m(0)} \\ &\leq \mathbb{1}_{\left\{i_1=i_2\right\}} \frac{(e^{2\varepsilon} -1 )^2}{e^{\varepsilon}} \cdot \sum_{m} q_\varepsilon^{m(0)}(1-q_\varepsilon)^{m(1)} \\ &= \mathbb{1}_{\left\{i_1=i_2\right\}} \frac{(e^{2\varepsilon} -1 )^2}{e^{\varepsilon}}, \end{align}\] where the inequality holds since \(m(1)e^{2\varepsilon} + m(0)\geq k\) for every \(\varepsilon\geq 0\). It follows that \[\lVert\mathbf{H}{\rVert}_F^2\leq k\cdot \frac{(e^{2\varepsilon} -1 )^4}{e^{2\varepsilon}},\] whereby \[\begin{align} {\operatorname{d}_{\rm TV}^{}\!\left({\mathcal{W}^{\sf{}no}, \mathcal{W}^{\sf{}yes}}\right)} &\leq \exp\left(\frac{\gamma^4n^2}{k^4}\lVert\mathbf{H}{\rVert}_F^2\right)-1 \leq \exp\left(\frac{\gamma^4n^2}{k^4}\left(k\frac{(e^{2\varepsilon}-1)^4}{e^{2\varepsilon}}\right)\right)-1\\ &\le \exp\left(\frac{\gamma^4 n^2}{e^{2\varepsilon}k^3}\left(e^{2\varepsilon}-1\right)^4\right)-1, \end{align}\] which can only be \(\Omega (1)\) if \(n= \Omega\left(\frac{k^{3/2}}{\gamma^2\left(e^\varepsilon-1\right)^2}\right)\), establishing the result. ◻

Proof. The proof follows the same outline as the proof of 9 – we show once again that the matrix \(\mathbf{H}\) corresponding to using HR for reporting each users data is a diagonal matrix. Specifically, considering the set of messages as \(\{0,\dots, K-1\}\) and the inputs as \(\{0,\dots k-1\}\) for convenience, the matrix \(\mathbf{H}\) in the proof of lower bound is given by \[\begin{align} \mathbf{H}(i_1, i_2) &= k\sum_{m=0}^{K-1}\frac{ \left( W(m\mid 2i_1)-W(m\mid 2i_1+1) \right) \left( W(m\mid 2i_2)-W(m\mid 2i_2+1) \right)}{ \sum_{i=0}^{k-1} W(m\mid i)}, \quad 0\leq i_1, i_2\leq \frac{k-1}{2}\,, \nonumber \end{align}\] where \(W(m\mid i)\) denotes the probability that HR outputs \(m\) when the input is \(i\) and is given by \[\begin{align} W(m\mid i) &= \frac{2}{K(e^\varepsilon+1)}\left( e^{\varepsilon} \mathbb{1}_{\left\{m\in C_i\right\}}+ \mathbb{1}_{\left\{m\notin C_i\right\}} \right) =\frac{2}{K(e^\varepsilon+1)}\left( (e^{\varepsilon}-1) \mathbb{1}_{\left\{m\in C_i\right\}}+ 1 \right)\,. \end{align}\] With a slight abuse of notation, we use \(m\) and \(i\) interchangeably to denote their values and the binary vectors corresponding to binary representation of those values. Further, let \(\mleft\langle x, y \mright\rangle = \oplus\, x_i y_i\) denote the standard (parity) inner product for vectors over \(\mathbb{F}_2\). With this convention, for HR we have \[\mathbb{1}_{\left\{m\in C_i\right\}} = \mathbb{1}_{\left\{ \mleft\langle m, i \mright\rangle =0\right\}}.\] Note that for \(m=0\) and every \(i\), \(\mathbb{1}_{\left\{m\in C_i\right\}} = 1\), which implies that \(W(0\mid i)\) is the same for all \(i\). It follows that the term corresponding to \(m=0\) in the expression for \(\mathbf{H}(i_1, i_2)\) is \(0\). Moreover, using \(\sum_{i=0}^{k-1} \mathbb{1}_{\left\{ \mleft\langle m, i \mright\rangle =0\right\}}=K/2\) for \(m\neq 0\), we obtain \[\begin{align} \sum_{i=1}^{k}W(m\mid i) &= \frac{2}{K(e^\varepsilon+1)}\left( \Big(e^{\varepsilon}-1\Big)\sum_{i=0}^{k-1} \mathbb{1}_{\left\{ \mleft\langle m, i \mright\rangle =0\right\}}+ k\right) \\ &=\frac{2}{K(e^\varepsilon+1)}\left( \Big(e^{\varepsilon}-1\Big)\frac{K}{2}+ k\right) \\ &= c(\varepsilon, k, K)\cdot\frac{k}{K}\,, \end{align}\] where \(c(\varepsilon, k, K) =2((e^{\varepsilon}-1) K/2+ k)/(k(e^\varepsilon+1))\); by assumption, \(k\leq K \leq 2k\), which implies that \(c(\varepsilon, k, K) \in [1, 2]\). Therefore, for every \(0\leq i_1, i_2\leq (k-1)/2\), \[\begin{align} \mathbf{H}(i_1, i_2) &= c(\varepsilon, k, K)\cdot\frac{4(e^\varepsilon-1)^2}{K(e^\varepsilon+1)^2}\sum_{m=1}^{K-1} \left(\mathbb{1}_{\left\{ \mleft\langle m, 2i_1 \mright\rangle =0\right\}} - \mathbb{1}_{\left\{ \mleft\langle m, 2i_1+1 \mright\rangle =0\right\}}\right)\cdot \nonumber \\ & \left(\mathbb{1}_{\left\{ \mleft\langle m, 2i_2 \mright\rangle =0\right\}} - \mathbb{1}_{\left\{ \mleft\langle m, 2i_2+1 \mright\rangle =0\right\}}\right). \label{e:H-terms} \end{align}\tag{12}\] We claim that \(\mathbf{H}(i_1, i_2)=0\) for \(i_1\neq i_2\). Indeed, a case analysis yields \[\begin{align} \left(\mathbb{1}_{\left\{ \mleft\langle m, 2i_1 \mright\rangle =0\right\}} - \mathbb{1}_{\left\{ \mleft\langle m, 2i_1+1 \mright\rangle =0\right\}}\right) &\left(\mathbb{1}_{\left\{ \mleft\langle m, 2i_2 \mright\rangle =0\right\}} - \mathbb{1}_{\left\{ \mleft\langle m, 2i_2+1 \mright\rangle =0\right\}}\right)\\ &= \left(\mathbb{1}_{\left\{ \mleft\langle m, 2i_1 \mright\rangle = \mleft\langle m, 2i_2 \mright\rangle \right\}} - \mathbb{1}_{\left\{ \mleft\langle m, 2i_1 \mright\rangle \neq \mleft\langle m, 2i_2 \mright\rangle \right\}}\right)\mathbb{1}_{\left\{ \mleft\langle m, 1 \mright\rangle \neq 0\right\}}\,, \end{align}\] where the condition \(\mathbb{1}_{\left\{ \mleft\langle m, 1 \mright\rangle \neq 0\right\}}\) indicates that the expression is nonzero only when \(m\) is odd. Thus, the summands in 12 can be restricted to odd \(m\), and further, each summand equals \[\mathbb{1}_{\left\{ \mleft\langle m, 2i_1 \mright\rangle = \mleft\langle m, 2i_2 \mright\rangle \right\}} - \mathbb{1}_{\left\{ \mleft\langle m, 2i_1 \mright\rangle \neq \mleft\langle m, 2i_2 \mright\rangle \right\}} = \mathbb{1}_{\left\{ \mleft\langle m, 2(i_1\oplus i_2) \mright\rangle =0\right\}} - \mathbb{1}_{\left\{ \mleft\langle m, 2(i_1\oplus i_2) \mright\rangle =1\right\}}\,.\] We can simplify the expression on the right-side by noting that each odd \(m\) has the binary form \((b,1)\) and \(\mleft\langle (b,1), 2i \mright\rangle = \mleft\langle b, i \mright\rangle\). Hence, \[\begin{align} \sum_{m=1}^{K-1} \left(\mathbb{1}_{\left\{ \mleft\langle m, 2i_1 \mright\rangle =0\right\}} - \mathbb{1}_{\left\{ \mleft\langle m, 2i_1+1 \mright\rangle =0\right\}}\right)&\left(\mathbb{1}_{\left\{ \mleft\langle m, 2i_2 \mright\rangle =0\right\}} - \mathbb{1}_{\left\{ \mleft\langle m, 2i_2+1 \mright\rangle =0\right\}}\right) \\ &=\sum_{m=0}^{(K-1)/2} \left(\mathbb{1}_{\left\{ \mleft\langle m,(i_1\oplus i_2) \mright\rangle =0\right\}} - \mathbb{1}_{\left\{ \mleft\langle m,(i_1\oplus i_2) \mright\rangle =1\right\}}\right) \\ &= \frac{K-1}{2}\mathbb{1}_{\left\{i_1=i_2\right\}}. \end{align}\] since for any nonzero vector \(j\), \(| \left\{\; m \;\colon\; \mleft\langle m, j \mright\rangle \rangle =0\; \right\} | = | \left\{\; m \;\colon\; \mleft\langle m, j \mright\rangle \rangle =1 \; \right\} |\) . In summary, we have \[\mathbf{H}(i_1, i_2) =c(\varepsilon, k, K)\cdot \frac{4(e^\varepsilon-1)^2(K-1)}{K(e^\varepsilon+1)^2} \mathbb{1}_{\left\{i_1=i_2\right\}},\] whereby using \(c(\varepsilon, k, K)\in [1,2]\) we get \[\lVert\mathbf{H}{\rVert}_F^2 = \sum_{i_1, i_2} |\mathbf{H}(i_1, i_2)|^2 = O\left(k\frac{(e^\varepsilon-1)^4}{(e^\varepsilon+1)^4}\right).\] The proof is completed in the same manner as the proof of 9. ◻

Proof. The proof is similar to that of 4. Note that it follows in the manner of 9 that for every \((z_1,z_2)\in[K]\times[K]\), \[\begin{align} \mathcal{T}(p)&(z_1,z_2) \\ &= \sum_{(x_1,x_2)\in [k]\times[k]} W(z_1 \mid x_1)W(z_2 \mid x_2)p(x_1,x_2) \\ &= \frac{4}{K^2(e^\varepsilon+1)^2} \sum_{(x_1,x_2)\in [k]\times[k]} p(x_1,x_2) \left( (e^\varepsilon-1) \mathbb{1}_{\left\{z_1\in C_{x_1}\right\}} + 1 \right)\left( (e^\varepsilon-1) \mathbb{1}_{\left\{z_2\in C_{x_2}\right\}} + 1 \right) \\ &= \frac{1}{K^2}\sum_{(x_1,x_2)\in [k]\times[k]} p(x_1,x_2) \left( \alpha_{H}\chi_{\phi(x_1)}(z_1) + 1 \right)\left( \alpha_{H}\chi_{\phi(x_2)}(z_2) + 1 \right) \\ &= \frac{\alpha_{H}^2}{K^2}\sum_{x_1,x_2} p(x_1,x_2)\chi_{\phi(x_1)}(z_1)\chi_{\phi(x_2)}(z_2) + \frac{\alpha_{H}}{K^2}\Big( \sum_{x_1} p_1(x_1)\chi_{\phi(x_1)}(z_1) + \sum_{x_2} p_2(x_2)\chi_{\phi(x_2)}(z_2) \Big) + \frac{1}{K^2}, \end{align}\] where by the second-to-last identity above gives \(\mathcal{T}(p)(z_1,z_2)\in [1-\alpha_{H}^2,1+\alpha_{H}^2]\cdot \frac{1}{K^2}\) for every \((z_1,z_2)\). As an analogous expression holds for \(\mathcal{T}(q)(z_1,z_2)\), setting \(g:=\mathcal{T}(p) - \mathcal{T}(q)\) we have \[\begin{align} g(z_1,z_2) &= \frac{\alpha_{H}^2}{K^2}\sum_{(x_1,x_2)\in [k]\times[k]} \left(p(x_1,x_2) - p_1(x_1)p_2(x_2) \right) \chi_{\phi(x_1)}(z_1)\chi_{\phi(x_2)}(z_2) \\ &\qquad+ \frac{\alpha_{H}}{K^2}\Big( \sum_{x_1\in [k]} (p_1(x_1)-q_1(x_1)) \chi_{\phi(x_1)}(z_1) + \sum_{x_2\in [k]} (p_2(x_2)-q_2(x_2)) \chi_{\phi(x_2)}(z_2) \Big), \end{align}\] for every \((z_1,z_2)\in [K]\times[K]\). Now, as in 4, but looking at the corresponding characters for the Hadamard transform from \([k]\times[k]\) to \([K]\times[K]\),¹⁸ we get \[\begin{align} \hat{g}(T) &= \frac{\alpha_{H}^2}{K^2}\sum_{(x_1,x_2)\in[k]\times[k]}\left(p(x_1,x_2) - p_1(x_1)p_2(x_2) \right)\mathbb{1}_{\left\{T=(\phi(x_1),\phi(x_2))\right\}} \\ &\qquad+ \frac{\alpha_{H}}{K^2}\Big( \sum_{x_1\in[k]}\left(p_1(x_1)-q_1(x_1)\right)\mathbb{1}_{\left\{T=\phi(x_1)\right\}} + \sum_{x_2\in[k]}\left(p_2(x_2)-q_2(x_2)\right)\mathbb{1}_{\left\{T=\phi(x_2)\right\}} \Big)\,. \end{align}\] By Parseval’s theorem (1), \[\begin{align} \lVert g{\rVert}^2 &= \frac{1}{K^2}\sum_{(z_1,z_2)\in[K]\times[K]}\left( \mathcal{T}(p)(z_1,z_2) - \mathcal{T}(q)(z_1,z_2) \right)^2 \\ &= \sum_{T\in[K]\times[K]} \hat{g}(T)^2 \\ &= \frac{\alpha_{H}^4}{K^4}\sum_{(x_1,x_2)\in[k]\times[k]}\left(p(x_1,x_2) - q(x_1,x_2) \right)^2 \\ & + \frac{\alpha_{H}^2}{K^4}\Big( \sum_{x_1}\left(p_1(x_1)-q_1(x_1)\right)^2 + \sum_{x_2}\left(p_2(x_2)-q_2(x_2)\right)^2 \Big), \end{align}\] so that \[{\lVert\mathcal{T}(p)-\mathcal{T}(q){\rVert}}_2^2 = \frac{\alpha_{H}^4}{K^2}{\lVert p-q{\rVert}}_2^2 + \frac{\alpha_{H}^2}{K^2}\left( {\lVert p_1-q_1{\rVert}}_2^2 + {\lVert p_2-q_2{\rVert}}_2^2 \right) \geq \frac{\alpha_{H}^4}{K^2}{\lVert p-q{\rVert}}_2^2\,,\] as claimed. ◻

Proof of 13. The first statement is obvious, as then \(\mathcal{T}(p) = \mathcal{T}(p_1\otimes p_2)\). Turning to the second, assume that \(p\) is \(\gamma\)-far from being a product distribution, so that in particular \({\operatorname{d}_{\rm TV}^{}\!\left({p, q}\right)} > \gamma\). This implies by 5 that \({\lVert\mathcal{T}(p) - \mathcal{T}(q){\rVert}}_2^2 > (4\alpha_{H}^4\gamma^2)/(K^2k^2)\) which along with \({\lVert\mathcal{T}(q){\rVert}}_\infty \leq \frac{1+\alpha_{H}^2}{K^2} \leq \frac{2}{K^2}\) yields \[\chi^2( \mathcal{T}(p), \mathcal{T}(q) ) = \sum_{z\in[K]\times[K]}\frac{ (\mathcal{T}(p)(z) - \mathcal{T}(q)(z))^2 }{ \mathcal{T}(q)(z)} \geq \frac{K^2}{2}{\lVert\mathcal{T}(p) - \mathcal{T}(q){\rVert}}_2^2 > \frac{2\alpha_{H}^4\gamma^2}{k^2},\] as claimed. ◻

Proof. Let \(p=p_1\otimes p_2\in\Delta\mleft([k]\times[k]\mright)\) be a product distribution, and \(\tilde{p}_1\), \(\tilde{p}_2\) be the hypotheses obtained by using the estimator of 6 independently on the two marginals of \(p\), with distance parameter \(\gamma^2/3\). We claim that \(\tilde{p}:=\tilde{p}_1\otimes\tilde{p}_2\) can serve as our desired estimate. Indeed, by a union bound, with probability at least \(4/5\) it is the case that \(\chi^2(p_1,\tilde{p}_1) \leq \gamma^2/3\) and \(\chi^2(p_2,\tilde{p_2}) \leq \gamma^2/3\). When this happens, \[\begin{align} \chi^2(p,\tilde{p}) &= -1 + \sum_{(x_1,x_2)\in[k]\times[k]} \frac{p_1(x_1)^2p_2(x_2)^2}{\tilde{p}_1(x_1)\tilde{p}_2(x_2)} \\ & = -1 + \sum_{x_1\in[k]} \frac{p_1(x_1)^2}{\tilde{p}_1(x_1)}\sum_{x_2\in[k]} \frac{p_2(x_2)^2}{\tilde{p}_2(x_2)} \\ &= -1 + (\chi^2(p_1,\tilde{p}_1)+1)(\chi^2(p_2,\tilde{p}_2)+1) \\ & = \chi^2(p_1,\tilde{p}_1)\chi^2(p_2,\tilde{p_2})+\chi^2(p_1,\tilde{p}_1)+\chi^2(p_2,\tilde{p_2}) \\ &\leq \frac{\gamma^4}{9} + \frac{2}{3}\gamma^2 < \gamma^2, \end{align}\] concluding the proof. ◻

Proof. Setting \(\delta_{ij} = (p(i,j) - p_1(i)p_2(j))\) in 14, note that \[Z = \sum_{i,j}X_iY_j(p(i,j)-p_1(i)p_2(j))= p(S_1\times S_2)-p_1(S_1)p_2(S_2)\] and that \[\lVert\delta{\rVert}_F^2 = \sum_{i,j\in [k]}\delta_{i,j}^2 \geq \frac{ \Big(\sum_{i,j\in [k]}\left\lvert \delta_{i,j} \right\rvert\Big)^2}{k^2}\geq \frac{4\gamma^2}{k^2}.\] Thus, the claim follows from 14. ◻

Proof. Since \(X_1, X_2,\dots, X_k\) are \(4\)-symmetric, the expectations \(\mathbb{E}\mleft[X_aX_bX_cX_d\mright]\) depends only on the number of times each distinct element appears in the multiset \(\{a,b,c,d\}\). For ease of notation, we replace the highest frequency element in \(\{a,b,c,d\}\) with \(1\), second highest with \(2\), and so on, to obtain a representation \(S\) and denote \(m_{S} :=\mathbb{E}\mleft[\prod_{i\in S}X_i\mright]\). For instance, \(\mathbb{E}\mleft[X_a^2\mright] = m_{\{1,1\}}\) and \(\mathbb{E}\mleft[X_aX_b\mright]=m_{\{1,2\}}\) for distinct \(a,b\). With this notation at our disposal, we are ready to proceed with the proof.

Note first that \[\mathbb{E}\mleft[Z\mright] = \sum_{i\in[k]}\delta_i \mathbb{E}\mleft[X_i\mright] = m_{\{1\}} \sum_{i\in [k]} \delta_i =0.\] Moreover, for the variance of \(Z\), we have \[\begin{align} \operatorname{Var}\mleft(Z\mright) = \mathbb{E}\mleft[Z^2\mright] &= \sum_{i_1,i_2 \in [k]}\delta_{i_1}\delta_{i_2} \mathbb{E}\mleft[X_{i_1}X_{i_2}\mright] \notag\\ &= \sum_{i_1 \in [k]}\delta_{i_1}^2\mathbb{E}\mleft[X_{i_1}^2\mright] + \sum_{i_1\neq i_2}\delta_{i_1}\delta_{i_2}\mathbb{E}\mleft[X_{i_1}X_{i_2}\mright] \notag\\ &= m_{\{1,1\}}{\lVert\delta{\rVert}}_2^2 +m_{\{1,2\}} \sum_{i\neq j}\delta_{i_1}\delta_{i_2} \notag\\ &= m_{\{1,1\}}{\lVert\delta{\rVert}}_2^2 +m_{\{1,2\}} \left(\Big(\sum_{i\in[k]}\delta_i\Big)^2 - \sum_{i\in [k]}\delta_i^2\right) \notag\\ &= (m_{\{1,1\}}- m_{\{1,2\}}){\lVert\delta{\rVert}}_2^2 \notag\\ &= \bigg(\mathbb{E}\mleft[X_1^2\mright]-\mathbb{E}\mleft[X_1X_2\mright]\bigg){\lVert\delta{\rVert}}_2^2 \label{eq:paley:1}\,, \end{align}\tag{14}\] where we used \(\sum_{i\in[k]}\delta_i = 0\) in the previous identity. It follows from Chebyshev’s inequality that \[\Pr\mleft[\, Z^2\leq \frac{1}{1-2\alpha} \left(\mathbb{E}\mleft[X_1^2\mright]-\mathbb{E}\mleft[X_1X_2\mright]\right){\lVert\delta{\rVert}}_2^2\, \mright] \geq 1-2\alpha.\] For the lower tail bound, we derive a bound for \(\mathbb{E}\mleft[Z^4\mright]\) and invoke the Paley–Zygmund inequality. Specifically, we have \[\begin{align} \mathbb{E}\mleft[Z^4\mright] &= \sum_{i_1, i_2, i_3,i_4}\delta_{i_1}\delta_{i_2}\delta_{i_3}\delta_{i_4}\mathbb{E}\mleft[X_{i_1}X_{i_2}X_{i_3}X_{i_4}\mright] \\ &=m_{\{1,1,1,1\}}\Sigma_1 + m_{\{1,1,1,2\}}\Sigma_{2,1} + m_{\{1,1,2,2\}}\Sigma_{2,2} + m_{\{1,1,2,3\}}\Sigma_3 + m_{\{1,2,3,4\}}\Sigma_4, \end{align}\] where we have abbreviated \[\begin{align} \Sigma_1 &= {\lVert\delta{\rVert}}_4^4, \\ \Sigma_{2, 1}&= 4\sum_{i_1< i_2}\left(\delta_{i_1}^3\delta_{i_2} + \delta_{i_2}^3\delta_{i_1}\right), \\ \Sigma_{2, 2}&= 6\sum_{i_1< i_2} \delta_{i_1}^2\delta_{i_2}^2, \\ \Sigma_{3}&= 12\sum_{i_1<i_2<i_3} \left(\delta_{i_1}^2\delta_{i_2}\delta_{i_3}+\delta_{i_1}\delta_{i_2}^2\delta_{i_3} +\delta_{i_1}\delta_{i_2}\delta_{i_3}^2\right), \\ \Sigma_{4}&= 24\sum_{i_1<i_2<i_3<i_4}\delta_{i_1}\delta_{i_2}\delta_{i_3}\delta_{i_4}. \end{align}\] The expressions for \(\Sigma\)’s above can be simplified further by using \(\sum_{i\in[k]}\delta_i=0\). Observe now that \[\Sigma_1+\Sigma_{2,1}+\Sigma_{2,2} + \Sigma_3 +\Sigma_4 = \Big(\sum_{i\in [k]}\delta_i\Big)^4 =0.\] Also, for \(\Sigma_{2,1}\) and \(\Sigma_{2,2}\), we obtain \[\begin{align} \Sigma_{2,1} &= 4\left(\sum_{i}\delta_{i} \sum_{i}\delta_{i}^3 - \sum_{i}\delta_i^4\right) = -4{\lVert\delta{\rVert}}_4^4, \\ \Sigma_{2,2} &= 3\left(\sum_{i}\delta_{i}^2 \sum_{i}\delta_{i}^2 - \sum_{i}\delta_i^4\right) =3{\lVert\delta{\rVert}}_2^4 - 3{\lVert\delta{\rVert}}_4^4. \end{align}\] Finally, the expressions for \(\Sigma\)’s can be seen to satisfy, \[\left(\sum_{i}\delta_{i}\right)^2 \sum_{i}\delta_{i}^2 = \sum_i \delta_i^4 + \frac{1}{2} \Sigma_{2,1} + \frac{1}{3} \Sigma_{2,2} + \frac{1}{6} \Sigma_3,\] whereby \[\begin{align} \Sigma_3 = - 6\Sigma_1 -3\Sigma_{2,1} - 2\Sigma_{2,2} = 12{\lVert\delta{\rVert}}_4^4 - 6{\lVert\delta{\rVert}}_2^4 \end{align}\] Combining the relations above, we obtain \[\begin{align} \mathbb{E}\mleft[Z^4\mright] &= \big(m_{\{1,1,1,1\}} -4m_{\{1,1,1,2\}} -3m_{\{1,1,2,2\}} +12 m_{\{1,1,2,3\}} - 6m_{\{1,2,3,4\}}\big) {\lVert\delta{\rVert}}_4^4 \\ &\qquad+ \big(3m_{\{1,1,2,2\}} - 6m_{\{1,1,2,3\}}+3m_{\{1,2,3,4\}}\big){\lVert\delta{\rVert}}_2^4 \\ &\leq \big(m_{\{1,1,1,1\}}+ 3m_{\{1,1,2,2\}}+ 15 m_{\{1,1,2,3\}}\big){\lVert\delta{\rVert}}_2^4. \end{align}\] Note that by symmetry \[2(m_{\{1,1,2,2\}} - m_{\{1,1,2,3\}})= E[X_1^2(X_2-X_3)^2] \geq 0\] and by symmetry and the Cauchy–Schwarz inequality \[m_{\{1,1,1,1\}}=\mathbb{E}\mleft[X_1^4\mright]\geq \mathbb{E}\mleft[X_1^2X_2^2\mright] = m_{\{1,1,2,2\}}.\] Therefore, the previous inequality yields \[\begin{align} \label{eq:paley:2} \mathbb{E}\mleft[Z^4\mright]&\leq 19 \mathbb{E}\mleft[X_1^4\mright]{\lVert\delta{\rVert}}_2^4\,. \end{align}\tag{15}\] We now take recourse to the Paley–Zygmund inequality, restated below:

Applying this to \(Z^2\) and substituting the bounds of 14 15 above, and setting \[\theta :=1-\sqrt{\frac{38\alpha}{1-2\alpha}}\frac{\sqrt{\mathbb{E}\mleft[X_1^4\mright]{\lVert\delta{\rVert}}_2^4}}{(\mathbb{E}\mleft[X_1^2\mright]-\mathbb{E}\mleft[X_1X_2\mright]){\lVert\delta{\rVert}}_2^2} \leq 1-\sqrt{\frac{19\alpha}{1-2\alpha}}\frac{\sqrt{\mathbb{E}\mleft[Z^4\mright]}}{\mathbb{E}\mleft[Z^2\mright]}\,,\] we obtain \[\Pr\mleft[\, Z^2 \geq \theta (\mathbb{E}\mleft[X_1^2\mright]-\mathbb{E}\mleft[X_1X_2\mright]){\lVert\delta{\rVert}}_2^2\, \mright] \geq \frac{(1-\theta)^2(\mathbb{E}\mleft[X_1^2\mright]-\mathbb{E}\mleft[X_1X_2\mright])^2{\lVert\delta{\rVert}}_2^4}{ 19\mathbb{E}\mleft[X_1^4\mright]{\lVert\delta{\rVert}}_2^4+ (1-\theta)^2(\mathbb{E}\mleft[X_1^2\mright]-\mathbb{E}\mleft[X_1X_2\mright])^2{\lVert\delta{\rVert}}_2^4} = 2\alpha\,,\] which completes the proof. ◻

Proof of 4. Letting again \(\lambda :=\frac{\alpha_{R}}{k}+\beta_{R}\) and \(\lambda_x:=\frac{1}{n}\mathbb{E}\mleft[N_x\mright] = \alpha_{R}p_x+\beta_{R}\) for \(x\in[k]\), we have \[\operatorname{Var}\mleft(T\mright) = \sum_{x,y\in[k]} \operatorname{Cov}\mleft( f(N_x) , f(N_y) \mright)\,,\] where \(f\colon[0,\infty)\to\mathbb{R}\) is given by \(f(t) = (t-(n-1)\lambda)^2 - t + (n-1)\lambda^2\).

The key difficulty in analysis arises from the fact that Rappor renders the multiplicities \(N_x\)’s dependent random variable. They are negatively associated, but since \(f\) is not monotone this does not imply that the cross covariance terms are non-positive. Thus, we need to take recourse to a more direct, elaborate treatment.

Fix \(x\neq y\) in \([k]\). Expanding the covariance term, recalling \(\mathbb{E}\mleft[f(N_x)\mright] = n(n-1)(\lambda_x-\lambda)^2\) from the proof of 3 and abbreviating \(r:= 2(n-1)\lambda+1\) and \(m:=n-1\), we obtain after a few manipulations that \[\begin{align} &\operatorname{Cov}\mleft( f(N_x) , f(N_y) \mright)\\ &= \mathbb{E}\mleft[ (f(N_x)-\mathbb{E}\mleft[f(N_x)\mright])(f(N_y)-\mathbb{E}\mleft[f(N_y)\mright])\mright]\\ &= \mathbb{E}\mleft[N_x^2N_y^2\mright] - r\mathbb{E}\mleft[N_x^2N_y+N_xN_y^2\mright] + mn\lambda_y(2\lambda-\lambda_y)\mathbb{E}\mleft[N_x^2\mright] + mn\lambda_x(2\lambda-\lambda_x)\mathbb{E}\mleft[N_y^2\mright] \\ &\qquad + r^2\mathbb{E}\mleft[N_xN_y\mright] - rmn( \lambda_y(2\lambda-\lambda_y)\mathbb{E}\mleft[N_x\mright] + \lambda_x(2\lambda-\lambda_x)\mathbb{E}\mleft[N_y\mright] )\\ &\qquad + m^2n^2 \lambda_x\lambda_y(2\lambda-\lambda_x)(2\lambda-\lambda_y)\\ &= \mathbb{E}\mleft[N_x^2N_y^2\mright] - r\mathbb{E}\mleft[N_x^2N_y+N_xN_y^2\mright] - 2m^2n\lambda\lambda_y(2\lambda-\lambda_y)\mathbb{E}\mleft[N_x\mright] + m^2\lambda_y(2\lambda-\lambda_y)\mathbb{E}\mleft[N_x\mright]^2\\ &\qquad-2m^2n\lambda\lambda_x(2\lambda-\lambda_x)\mathbb{E}\mleft[N_y\mright] + m^2\lambda_x(2\lambda-\lambda_x)\mathbb{E}\mleft[N_y\mright]^2 \\ &\qquad + r^2\mathbb{E}\mleft[N_xN_y\mright] + m^2n^2 \lambda_x\lambda_y(2\lambda-\lambda_x)(2\lambda-\lambda_y). \end{align}\] Substituting \(r-1=2m\lambda\) and \(\mathbb{E}\mleft[N_y^2\mright] = \mathbb{E}\mleft[N_y\mright]+\frac{m}{n}\mathbb{E}\mleft[N_y\mright]^2\) in the previous identity, and similarly for \(N_x\), we get \[\begin{align} \label{eq:covariance} & \operatorname{Cov}\mleft( f(N_x) , f(N_y) \mright) \nonumber \\ &= \mathbb{E}\mleft[N_x^2N_y^2\mright] - (2m\lambda+1)\mathbb{E}\mleft[N_x^2N_y+N_xN_y^2\mright] - 2m^2\lambda(2\lambda-\lambda_y)\mathbb{E}\mleft[N_x\mright]\mathbb{E}\mleft[N_y\mright] \notag\\ &\qquad-2m^2\lambda(2\lambda-\lambda_x)\mathbb{E}\mleft[N_x\mright]\mathbb{E}\mleft[N_y\mright] + m^2\lambda_x(2\lambda-\lambda_x)\mathbb{E}\mleft[N_y\mright]^2 + m^2\lambda_y(2\lambda-\lambda_y)\mathbb{E}\mleft[N_x\mright]^2\notag\\ &\qquad + (2m\lambda+1)^2\mathbb{E}\mleft[N_xN_y\mright] + m^2\mathbb{E}\mleft[N_x\mright]\mathbb{E}\mleft[N_y\mright](2\lambda-\lambda_x)(2\lambda-\lambda_y). \end{align}\tag{16}\] We proceed by evaluating the expressions for \(\mathbb{E}\mleft[N_xN_y\mright]\), \(\mathbb{E}\mleft[N_x^2N_y\mright]\), \(\mathbb{E}\mleft[N_xN_y^2\mright]\), and \(\mathbb{E}\mleft[N_x^2N_y^2\mright]\) separately.

Specifically, by [fact:rappor:statistics], we get \[\begin{align} \mathbb{E}\mleft[N_xN_y\mright] &= \sum_{1\leq i,j\leq n} \Pr\mleft[\, {\boldsymbol{b}}_{ix} =1, {\boldsymbol{b}}_{jy}=1\, \mright] \nonumber \\ & = \sum_{i=1}^n( \lambda_x\lambda_y - \alpha_{R}^2p(x)p(y) ) + \sum_{i\neq j} \lambda_x\lambda_y \nonumber \\ &= n^2\lambda_x\lambda_y - n\alpha_{R}^2p(x)p(y). \label{eq:covariance:11} \end{align}\tag{17}\]

Turning to \(\mathbb{E}\mleft[N_x^2N_y\mright]\), we get \[\begin{align} \mathbb{E}\mleft[N_x^2 N_y\mright] &= \sum_{1\leq i,j,\ell\leq n} \Pr\mleft[\, {\boldsymbol{b}}_{ix} = 1, {\boldsymbol{b}}_{jx} = 1, {\boldsymbol{b}}_{\ell y} = 1 \, \mright] \\ &= n\Pr\mleft[\, {\boldsymbol{b}}_{ix} = 1, {\boldsymbol{b}}_{i y} = 1 \, \mright] + 6\binom{n}{3} \lambda_x^2 \lambda_y + 2\binom{n}{2}\left( \lambda_x\lambda_y+2\lambda_x(\lambda_x\lambda_y-\alpha_{R}^2p(x)p(y)) \right) \\ &= n\lambda_x\lambda_y - n\alpha_{R}^2p(x)p(y) + n(n-1)(n-2)\lambda_x^2 \lambda_y \\ &\qquad+ n(n-1) \lambda_x\lambda_y+ 2 n(n-1)\lambda_x^2\lambda_y - 2 n(n-1)\alpha_{R}^2\lambda_xp(x)p(y), \end{align}\] which yields \[\label{eq:covariance:21} \mathbb{E}\mleft[N_x^2 N_y\mright] = n^2 \lambda_x\lambda_y - (2m\lambda_x+1)n\alpha_{R}^2p(x)p(y) + mn^2\lambda_x^2 \lambda_y.\tag{18}\]

For the last term, note that \[\begin{align} \mathbb{E}\mleft[N_x^2 N_y^2\mright] &= \sum_{1\leq i,j,i',j'\leq n} \Pr\mleft[\, {\boldsymbol{b}}_{ix} = 1, {\boldsymbol{b}}_{jx} = 1, {\boldsymbol{b}}_{i' y} = 1, {\boldsymbol{b}}_{j' y} = 1 \, \mright] \\ &= n\left(\lambda_x\lambda_y-\alpha_{R}^2p(x)p(y)\right) + \binom{n}{2}\left(2\lambda_x\lambda_y + 4\lambda_x\left(\lambda_x\lambda_y-\alpha_{R}^2p(x)p(y)\right) \right.\\&\qquad\left.+ 4\lambda_y\left(\lambda_x\lambda_y-\alpha_{R}^2p(x)p(y)\right) + 4\left(\lambda_x\lambda_y-\alpha_{R}^2p(x)p(y)\right)^2 \right) \\ &\qquad+ \binom{n}{3}\left( 6\lambda_x^2\lambda_y+6\lambda_x\lambda_y^2 + 24\lambda_x\lambda_y\left(\lambda_x\lambda_y-\alpha_{R}^2p(x)p(y)\right) \right) \\ &\qquad + 24\binom{n}{4} \lambda_x^2\lambda_y^2 \end{align}\] where the second identity follows from counting the different possibilities for the values taken by \(i,i',j,j'\); we divide into cases based on the number of different values taken and apply [fact:rappor:statistics] for each subcase. Note that the total number of terms is \(n+14\binom{n}{2}+36\binom{n}{3}+24\binom{n}{4}=n^4\).

This after a tedious simplification leads to \[\begin{align} \label{eq:covariance:22} \mathbb{E}\mleft[N_x^2 N_y^2\mright] &= n\left(\lambda_x\lambda_y-\alpha_{R}^2p(x)p(y)\right) + mn\left(\lambda_x\lambda_y + 2\lambda_x\left(\lambda_x\lambda_y-\alpha_{R}^2p(x)p(y)\right) \right.\notag\\&\qquad\left.+ 2\lambda_y\left(\lambda_x\lambda_y-\alpha_{R}^2p(x)p(y)\right) + 2\left(\lambda_x\lambda_y-\alpha_{R}^2p(x)p(y)\right)^2 \right) \notag\\ &\qquad+ mn(m-1)\left( \lambda_x^2\lambda_y+\lambda_x\lambda_y^2 + 4\lambda_x\lambda_y\left(\lambda_x\lambda_y-\alpha_{R}^2p(x)p(y)\right) \right) \notag\\ &\qquad + mn(m-1)(m-2) \lambda_x^2\lambda_y^2 \notag\\ &= m^2n^2 \lambda_x^2 \lambda_y^2 + mn^2 (\lambda_x^2 \lambda_y + \lambda_x \lambda_y^2) + n^2 \lambda_x \lambda_y - 4\alpha_{R}^2m^2np(x) p(y) \lambda_x \lambda_y \notag\\ &\qquad- 2 \alpha_{R}^2 mn\left( p(x) p(y) \lambda_x + p(x) p(y) \lambda_y \right) + 2\alpha_{R}^4 mnp(x)^2 p(y)^2 -\alpha_{R}^2 np(x) p(y)\,, \end{align}\tag{19}\]

Upon combining 17 18 19 with 16 and further simplifying the expressions, we get \[\begin{align} \operatorname{Cov}\mleft( f(N_x) , f(N_y) \mright) &= 2 \alpha_{R}^4 n(n-1) \left( p(x)^2 p(y)^2 - 2(n-1) p(x) p(y) \left(p(x)-\tfrac{1}{k}\right)\left(p(y)-\tfrac{1}{k}\right) \right)\,. \end{align}\] We proceed by summing both sides over pairs of distinct \(x,y\in[k]\) to obtain \[\begin{align} &\sum_{x\neq y}\operatorname{Cov}\mleft( f(N_x) , f(N_y) \mright) \\ &= 2\alpha_{R}^4n(n-1)\sum_{x\neq y} p(x)^2p(y)^2 - 4\alpha_{R}^4n(n-1)^2 \sum_{x\neq y} p(x)p(y)\left(p(x)-\tfrac{1}{k}\right)\left(p(y)-\tfrac{1}{k}\right) \\ &= 2\alpha_{R}^4n(n-1)\left( {\lVert p{\rVert}}_2^4 - {\lVert p{\rVert}}_4^4 \right) - 4\alpha_{R}^4n(n-1)^2 \left( {\lVert p-u{\rVert}}_2^4 - \sum_{x\in[k]} p(x)^2\left(p(x)-\tfrac{1}{k}\right)^2 \right)\\ &\leq 2\alpha_{R}^4n^2+ 4\alpha_{R}^4n(n-1)^2 {\lVert p-u{\rVert}}_2^2\\ &\leq 2n^2 + 4\alpha_{R}^2n(n-1)^2{\lVert p-u{\rVert}}_2^2\,, \end{align}\] where we have used \(\sum_{x\in[k]} p(x)\left(p(x)-\frac{1}{k}\right) = {\lVert p{\rVert}}_2^2-1/k= {\lVert p-u{\rVert}}_2^2\) and bounded the non-negative terms.

This completes our bound for the cross-variance terms. Turning now to the variances, we note that \[\begin{align} \operatorname{Var}\mleft( f(N_x) \mright) &= 2 n(n-1) \lambda_x^2(1-\lambda_x)^2 + 4n(n-1)^2\lambda_x(1-\lambda_x) (\lambda-\lambda_x)^2 \\ &\leq \frac{1}{8}n^2 + \alpha_{R}^2n(n-1)^2\left(p(x)-\tfrac{1}{k}\right)^2, \end{align}\] where the previous inequality holds since \(\lambda_x\in[0,1]\). It follows that \[\begin{align} \sum_{x\in[k]}\operatorname{Var}\mleft( f(N_x) \mright) &\leq \frac{1}{8}n^2k+ \alpha_{R}^2n(n-1)^2{\lVert p-u{\rVert}}_2^2\,. \end{align}\] Putting everything together, we conclude \[\operatorname{Var}\mleft(T\mright) = \sum_{x\in[k]}\operatorname{Var}\mleft( f(N_x) \mright) + \sum_{x\neq y}\operatorname{Cov}\mleft( f(N_x) , f(N_y) \mright) \leq \frac{17}{8}n^2 + 5\alpha_{R}^2n(n-1)^2{\lVert p-u{\rVert}}_2^2\,,\] proving the lemma. ◻

Proof. The proof is similar to that of 6, with further technicalities difficulties arising since the random variables \((X_i,Y_j)\) assigned as weights to \(\delta_{ij}\), \(1\leq i,j\leq k\), are not \(4\)-symmetric (as a pair). However, \(\delta\) has an additional structure since both its rows and columns sum to zero; we complete the proof by exploiting this property and the fact that \(X_i\)’s and \(Y_j\)’s are individually \(4\)-symmetric. As before, we use the notation \(m_S :=\mathbb{E}\mleft[\prod_{i\in S} X_i\mright]\), and moreover, let \(m'_S :=\mathbb{E}\mleft[\prod_{i\in S} Y_i\mright]\).

First, observe that by independence of \(X_i\)’s and \(Y_j\)’s and since \(\sum_{(i,j)\in [k]\times[k]}\delta_{ij} = 0\), we have \[\mathbb{E}\mleft[Z\mright] = \sum_{(i,j)\in [k]\times[k]}\delta_{ij} \mathbb{E}\mleft[X_i\mright]\mathbb{E}\mleft[Y_j\mright] = m_{\{1\}}m'_{\{1\}}\sum_{(i,j)\in [k]\times[k]}\delta_{ij} = 0\,.\] Furthermore, \[\begin{align} \operatorname{Var}\mleft(Z\mright) = \mathbb{E}\mleft[Z^2\mright] &= \sum_{(i_1,j_1)\in[k]\times[k]}\sum_{(i_2,j_2)\in[k]\times[k]}\delta_{i_1j_1}\delta_{i_2j_2} \mathbb{E}\mleft[X_{i_1}X_{i_2}\mright]\mathbb{E}\mleft[Y_{j_1}Y_{j_2}\mright] \\ &= \sum_{i_1,i_2} \mathbb{E}\mleft[X_{i_1}X_{i_2}\mright] \sum_{j_1,j_2}\delta_{i_1j_1}\delta_{i_2j_2}\mathbb{E}\mleft[Y_{j_1}Y_{j_2}\mright]\\ &= \sum_{i_1,i_2} \mathbb{E}\mleft[X_{i_1}X_{i_2}\mright] \left( m'_{\{1,1\}}\sum_{j_1}\delta_{i_1j_1}\delta_{i_2j_1} + m'_{\{1,2\}} \sum_{j_1\neq j_2}\delta_{i_1j_1}\delta_{i_2j_2} \right)\\ &= \sum_{i_1,i_2} \mathbb{E}\mleft[X_{i_1}X_{i_2}\mright] \Bigg( (m'_{\{1,1\}}-m'_{\{1,2\}})\sum_{j}\delta_{i_1j}\delta_{i_2j} + m'_{\{1,2\}} \Big(\sum_{j}\delta_{i_1j} \Big)^2 \Bigg)\\ &= (m'_{\{1,1\}}-m'_{\{1,2\}})\sum_{i_1,i_2} \sum_{j}\delta_{i_1j}\delta_{i_2j} \mathbb{E}\mleft[X_{i_1}X_{i_2}\mright]\, , \end{align}\] where the previous identity uses \(\sum_{j}\delta_{i_1j} = 0\). Repeating the same manipulations with the outer sum, we get \[\begin{align} \operatorname{Var}\mleft(Z\mright) = \mathbb{E}\mleft[Z^2\mright] &= (m'_{\{1,1\}}-m'_{\{1,2\}})\sum_{j} \Bigg( m_{\{1,1\}}\sum_{i} \delta_{ij}^2 + m_{\{1,2\}}\sum_{i_1\neq i_2} \delta_{i_1j}\delta_{i_2j} \Bigg) \notag\\ &= (m'_{\{1,1\}}-m'_{\{1,2\}})\sum_{j} \Bigg( (m_{\{1,1\}}-m_{\{1,2\}})\sum_{i} \delta_{ij}^2 + m_{\{1,2\}}\Big(\sum_{i} \delta_{i,j}\Big)^2 \Bigg) \notag\\ &= (m_{\{1,1\}}-m_{\{1,2\}})(m'_{\{1,1\}}-m'_{\{1,2\}})\lVert\delta{\rVert}_F^2 \,. \end{align}\] Up to this point, our calculations are valid for any independent choice of \(4\)-symmetric \((X_1,\dots,X_k)\) and \((Y_1, \dots, Y_k)\). For our specific choice, using calculations from the proof of 2, we obtain the following: \[\frac{1}{16} \lVert\delta{\rVert}_F^2 \leq \operatorname{Var}\mleft(Z\mright) = \frac{1}{4} \mathbb{E}\mleft[(X_1-X_2)^2\mright]\mathbb{E}\mleft[(Y_1-Y_2)^2\mright] \lVert\delta{\rVert}_F^2 \leq \frac{1}{4}\lVert\delta{\rVert}_F^2\,.\] It remains to bound the fourth moment of \(Z\); for simplicity, we provide this proof only for our specific choice of random variables. We have \[\begin{align} \mathbb{E}\mleft[Z^4\mright] &= \sum_{(i_1,j_1)}\sum_{(i_2,j_2)}\sum_{(i_3,j_3)}\sum_{(i_4,j_4)}\delta_{i_1j_1}\delta_{i_2j_2}\delta_{i_3j_3}\delta_{i_4j_4} \mathbb{E}\mleft[X_{i_1}X_{i_2}X_{i_3}X_{i_4}\mright]\mathbb{E}\mleft[Y_{j_1}Y_{j_2}Y_{j_3}Y_{j_4}\mright] \notag\\ &= \sum_{i_1,i_2,i_3,i_4} \mathbb{E}\mleft[X_{i_1}X_{i_2}X_{i_3}X_{i_4}\mright] \sum_{j_1,j_2,j_3,j_4} \mathbb{E}\mleft[Y_{j_1}Y_{j_2}Y_{j_3}Y_{j_4}\mright] \delta_{i_1j_1}\delta_{i_2j_2}\delta_{i_3j_3}\delta_{i_4j_4} \nonumber\,. \end{align}\] Consider the inner summation for an arbitrary fixed choice of \(i_1, i_2, i_3, i_4\). We show first that the inner summation can be expressed as \[\begin{align} \alpha_k\sum_{j}\delta_{i_1j}\delta_{i_2j}\delta_{i_3j}\delta_{i_4j} + \beta_k\sum_{j}\delta_{i_1j}\delta_{i_2j}\cdot \sum_j\delta_{i_3j}\delta_{i_4j}, \label{e:remaining:term} \end{align}\tag{20}\] for appropriate coefficients \(\alpha_k\) and \(\beta_k\). To that end, we introduce the notations: For \(\ell\leq 4\), denote \[\begin{align} p_\ell(j_1, \dots, j_{\ell}) &:=\Pr\mleft[\, Y_{j_1}=1, \dots, Y_{j_\ell}=1\, \mright] \\ p_\ell(j_1, \dots, j_{\ell-1}) &:=\Pr\mleft[\, Y_{j_\ell}=1\mid Y_{j_1}=1, \dots, Y_{j_{\ell-1}}=1\, \mright], \quad j_\ell\notin\{j_1, \dots, j_{\ell-1}\}, \\ p_\ell(j_1, \dots, j_{m}) &:=\Pr\mleft[\, Y_{j_\ell}=1\mid Y_{j_1}=1, \dots, Y_{j_{m}}=1, Y_{j_{m+1}} =1, \dots, Y_{j_{\ell-1}} =1 \, \mright], \\ &\qquad\qquad\qquad j_r \notin \{j_1, \dots, j_{m}\},\,\, j_r \text{ distinct for } m+1< r\leq \ell, \end{align}\] and the corresponding notation \(q_\ell(j_1, \dots, j_{m}) :=1- p_\ell(j_1, \dots, j_m)\). With this in hand, we can write \[\begin{align} \sum_{j_1,j_2,j_3,j_4}&\delta_{i_1j_1}\delta_{i_2j_2}\delta_{i_3j_3}\delta_{i_4j_4}\mathbb{E}\mleft[Y_{j_1}Y_{j_2}Y_{j_3}Y_{j_4}\mright] \\ &=\sum_{j_1,j_2,j_3}\delta_{i_1j_1}\delta_{i_2j_2}\delta_{i_3j_3}\left(\sum_{j_4\in \{j_1, j_2, j_3\}}\delta_{i_4j_4} \mathbb{E}\mleft[Y_{j_1}Y_{j_2}Y_{j_3}\mright] + \sum_{j_4\notin \{j_1, j_2, j_3\}}\delta_{i_4j_4} \mathbb{E}\mleft[Y_{j_1}Y_{j_2}Y_{j_3}Y_{j_4}\mright]\right) \\ &=\sum_{j_1,j_2,j_3}p_3(j_1, j_2, j_3)\delta_{i_1j_1}\delta_{i_2j_2}\delta_{i_3j_3}\left(\sum_{j_4\in \{j_1, j_2, j_3\}}\delta_{i_4j_4} + p_4(j_1, j_2, j_3)\sum_{j_4\notin \{j_1, j_2, j_3\}}\delta_{i_4j_4}\right) \\ &=\sum_{j_1,j_2,j_3}p_3(j_1, j_2, j_3)q_4(j_1, j_2, j_3)\delta_{i_1j_1}\delta_{i_2j_2}\delta_{i_3j_3}\sum_{j_4\in \{j_1, j_2, j_3\}}\delta_{i_4j_4}, \end{align}\] where we have used \(\sum_{j}\delta_{i_4, j}=0\) in the previous identity. Next, note that each term in the sum above has, by symmetry, the form \[\begin{align} &\sum_{j_1,j_2,j_3}p_3(j_1,j_2, j_3)q_4(j_1, j_2,j_3)\delta_{i_1j_1}\delta_{i_2j_2}\delta_{i_3j_3}\delta_{i_4j_1} \\ &=\sum_{j_1,j_2}p_2(j_1, j_2) \Big( q_3(j_1, j_2)\sum_{j_3\in \{j_1, j_2\}}\delta_{i_1j_1}\delta_{i_2j_2}\delta_{i_3j_3}\delta_{i_4j_1} + p_3(j_1, j_2)q_4(j_1, j_2)\sum_{j_3\notin \{j_1, j_2\}}\delta_{i_1j_1}\delta_{i_2j_2}\delta_{i_3j_3}\delta_{i_4j_1}\Big) \\ &=\sum_{j_1,j_2}p_2(j_1, j_2) \Big(1- p_3(j_1, j_2)\big(1+q_4(j_1, j_2)\big)\Big) \sum_{j_3\in \{j_1, j_2\}}\delta_{i_1j_1}\delta_{i_2j_2}\delta_{i_3j_3}\delta_{i_4j_1}, \end{align}\] where we have once again used \(\sum_{j_3}\delta_{i_3, j_3}=0\) to obtain the last line from the second-to-last. This leaves us with terms of the form \[\begin{align} \sum_{j_1,j_2}p_2(j_1,j_2)\Big(1- p_3(j_1, j_2)\big(1+q_4(j_1, j_2)\big)\Big) \left( \delta_{i_1j_1}\delta_{i_2j_2}\delta_{i_3j_1}\delta_{i_4j_1} + \delta_{i_1j_1}\delta_{i_2j_2}\delta_{i_3j_2}\delta_{i_4j_1}\right). \end{align}\] Finally, splitting the summation above into terms with \(j_1=j_2\) and \(j_1\neq j_2\), we end up with terms of the form 20 . Note that the resulting coefficients \(\alpha_k,\beta_k\) entail terms dependent on \(k\) which can be handled and bounded (crucially, independently of \(k\)) in the manner of proof of 2.

To complete the proof, we handle each term in 20 separately. For the first, we obtain \[\begin{align} \sum_{j}\sum_{i_1,i_2,i_3, i_4}\delta_{i_1j}\delta_{i_2j}\delta_{i_3j}\delta_{i_4j} \mathbb{E}\mleft[X_1X_2X_3X_4\mright] \leq 19\mathbb{E}\mleft[X_1^4\mright]\sum_j\Big( \sum_{i}\delta_{ij}^2\Big)^2 \leq 19\mathbb{E}\mleft[X_1^4\mright]\lVert\delta{\rVert}_F^2\,, \nonumber \end{align}\] where the inequality uses 15 . For the second term, note that \[\begin{align} \sum_{i_1,i_2,i_3,i_4}X_{i_1}X_{i_2}X_{i_3}X_{i_4} \sum_{j}\delta_{i_1j}\delta_{i_2j}\cdot \sum_{j^\prime}\delta_{i_3j^\prime}\delta_{i_4j^\prime} &= \Big(\sum_{j}\Big(\sum_{i}X_i\delta_{ij}\Big)^2\Big)^2, \end{align}\] whereby the expected value of the left-side can be bounded by \[\begin{align} \mathbb{E}\mleft[\left(\sum_{j}\left(\sum_{i}X_i\delta_{ij}\right)^2\right)^2\mright] &= \sum_{j, j^\prime}\mathbb{E}\mleft[\left(\sum_{i}X_i\delta_{ij}\right)^2\left(\sum_{i}X_i\delta_{ij^\prime}\right)^2\mright] \\ &\leq \sum_{j, j^\prime}\sqrt{\mathbb{E}\mleft[\left(\sum_{i}X_i\delta_{ij}\right)^4\mright]\mathbb{E}\mleft[ \left(\sum_{i}X_i\delta_{ij^\prime}\right)^4\mright]} \\ &\leq 19 \mathbb{E}\mleft[X_1^4\mright] \sum_{j, j^\prime} {\lVert\delta_{\cdot, j}{\rVert}}_2^2{\lVert\delta_{\cdot, j^\prime}{\rVert}}_2^2, \end{align}\] where the final inequality uses 15 . The sum on the right-side can be seen to simplify as \[\begin{align} \sum_{j, j^\prime} {\lVert\delta_{\cdot, j}{\rVert}}_2^2{\lVert\delta_{\cdot, j^\prime}{\rVert}}_2^2 = \sum_{j, j^\prime}\sum_{i}\delta_{i,j}^2 \sum_{i}\delta_{i,j^\prime}^2 = \left(\sum_{ij}\delta_{i,j}^2\right)^2 =\lVert\delta{\rVert}_F^4. \end{align}\] Therefore, on combining the observations above, we obtain \[\mathbb{E}\mleft[Z^4\mright]\leq c^\prime \lVert\delta{\rVert}_F^4,\] for an appropriate absolute constant \(c'\). The proof is completed in the manner of that of 6 using the Paley–Zygmund inequality. ◻