$5.$ Consider the following program

$//$ Given a b i a s e d coin $,$ use i t to g ene rat e an unb ias ed b i t b

int x $,$ y:$=0,0$ ;

while $($ x$=$y $)$ f

x:$=0[$ p $]1$ ;

y:$=0[$ p $]1$ ; nn f l i p bia s ed b i t s u n t i l they ar e not equal

g

b:$=$ x ;

$($a$)$ Is this a Monte Carlo algorithm or a Las Vegas algorithm? $($Write

one line.$)$

$($b$)$ Show that in a single iteration, the probability of setting x $=$

$0^$ y $=1$ is the same as the probability of setting x $=1^$ y $=0.$

Why does this observation imply that the probability of setting

b to $0$ will be unbiased?

$($c$)$ Justify that this program terminates with probability $1$ provided

that $0<$ p $<1.($Hint: use a probabilistic variant.$)$