# How is it possible to define differential privacy on two databases that differ more than a single entry?

The original definition of $$\epsilon-$$differential privacy is for two databases $$D_1$$, $$D_2$$ that differ at most one entry and an randomized algorithm $$A$$.

We have a bound on the probability ratio $$\frac{Pr[A(D_1) \in S]}{Pr[A(D_2) \in S]} \leq e^\epsilon$$ where $$S$$ is subset of range of $$A$$.

How do we define such thing for two databases that differ more than one entry?

One of the advantages of differential privacy is composition. That is, if $$D_1$$ and $$D_k$$ differ on $$k$$ entries, then $$k\cdot\epsilon$$ differential privacy is achieved. This is easily shown by writing a series of equations. Specifically, let $$D_1$$ and $$D_k$$ differ on $$k$$ entries, and let $$D_i$$ be a database that differs from $$D_{i-1}$$ on one entry (for $$i=2,...,k$$). Then, $$\frac{\Pr[A(D_1)\in S]}{\Pr[A(D_k)\in S]} = \frac{\Pr[A(D_1)\in S]}{\Pr[A(D_2)\in S]} \cdot \frac{\Pr[A(D_2)\in S]}{\Pr[A(D_3)\in S]}\cdots \frac{\Pr[A(D_{k-1})\in S]}{\Pr[A(D_k)\in S]} \leq (e^\epsilon)^k = e^{k\cdot\epsilon}$$ where each $$\frac{\Pr[A(D_{i-1})\in S]}{\Pr[A(D_i)\in S]} \leq e^\epsilon$$ by the assumption of differential privacy for databases that differ on a single entry.