A fundamental concept throughout cryptography and theoretical computer science is that of the advan$-$

tage an algorithm has in distinguishing between two given distributions. We will define this here in the

context of secure communication we saw in the first lecture, and we will see more general versions of this

in later lectures. We will use the following notation.

Definition $2\mathrm{.}1($Advantage$).$ Consider two random variables $x_0,x_1$ over a finite space $x,$ and an

algorithm $A($possibly randomised$)$ that takes an input from $x$ and outputs $0$ or $1.$ The advantage of $A$

in distinguishing between the random variables $x_0$ and $x_1$ is defined as:

$ad{v}_A^{x_0,x_1}=|P{r}_{xlarr{x}_1}[A(x)=1]-P{r}_{xlarr{x}_0}[A(x)=1]|$

Observe that this quantity is always between $0$ and $1.$ We will see eventually how it serves as a

measure of how distinguishable two distributions are, starting now with the following.

Problem $2\mathrm{.}1(3$ points$).$ Suppose random variables $x_0$ and $x_1$ are such that for every xinx, we have

$Pr[x_0=x]=Pr[x_1=x].$ Prove that for any algorithm $A,ad{v}_A^{x_0,x_1}=0.$

Hint. Try to first prove this assuming that $A$ is deterministic, and then see how to extend it to randomised

algorithms.

Problem $2\mathrm{.}2(3$ points$).$ Suppose random variables $x_0$ and $x_1$ are such that for any algorithm $A,$ we

have $ad{v}_A^{x_0,x_1}=0.$ Prove that for every xinx,$Pr[x_0=x]=Pr[x_1=x].$