HW1 Q2b

HW1 Q2b

daniel_c1 03 Nov 2019 18:45

Hi,

For clarification, in this question A is a function from {X0,X1} to {0,1}?
If so, I understand the right equation in 2b, but I don't quite understand how to connect between expressions like Pr [A(X0) = 1] and Pr [X0 = x] to show the left one, because A is genral function and we don't know how it picks betweeen X0 and X1.

Thanks

Re: HW1 Q2b

nbitansky 08 Nov 2019 07:52

Sorry for the delay. I seem to have missed this question.

$A$ is a Boolean function on the joint support of the distributions $X_0,X_1$.
Re the connecting $A$'s distinguishing advantage to the $\ell_1$ distance between the distributions, this is what this question is about. You need to show what is the connection.