Designing Statistical Tests. For any statistical test A$,$ its C$.$I.

advantage in distinguishing two distributions D$0$ and D$1$ is denoted as AdvC.I.

D$0,$D$1($A$)$ and equals

AdvC.I.

D$0,$D$1($A$)=|$ Pr$[$A$($x$)=1$ : x $$ D$0]$ Pr$[$A$($x$)=1$ : x $$ D$1]|.$

Let D$0$ and D$1$ be the uniform distributions over the sets Z$9$ and Z$$

$21$ respectively, where

Z$9=\{0,1,2,3,4,5,6,7,8\}$ ; Z$$

$21=\{1,2,4,5,8,10,11,13,16,17,19,20\}.$

$1.(3$ points$)$ Compute the C$.$I. advantage of the following test distA:

$1$ def distA $($ x $)$ : # x is a sample from either $D$\_0$$ or $D$\_1$$

$2$ if is$\_$prime $($ x $)=1$: return $1$

$3$ else : return $0$

$2.(3$ points$)$ Compute the C$.$I. advantage of the following test distB:

$1$ def distB $($ x $)$ : # x is a sample from either $D$\_0$$ or $D$\_1$$

$2$ if x $<=10$: return $1$

$3$ else : return $0$

$3.(1$ points$)$ Which of distA or distB does a better job of distinguishing the two distributions

and why?

$4.(3$ point$)$ Empirically estimate the quantities computed in $($a$)$ and $($b$)$ using your favorite

programming language. Report the estimated probabilities and C$.$I. advantages over $1000$

trials. For full credit, include the code you wrote.

$4$