$($b$)$ Consider the problem setting in part $($a$)$ again, and now let $Z_n$ be the number of accepted offers until

and including day $n$ assuming $x_1=\frac{1}{2}.$ That is$,Z_n={\displaystyle \underset{i=2}{\overset{n}{}}}I(x_i>\frac{1}{2}),$ where $I(*)$ is the indicator

function. What is $E[Z_n]?$ Also, prove that with probability at least $1-,$ for any $in(0,1),$ we have that

$Z_n\frac{n}{2}+O(\sqrt[\phantom{2}]{nlog(\frac{1}{})}).$ That is$,$

Hint: Use Chernoff$-$Hoeffding bounds $($Look here or here$)$ Also familiarize yourself with the Big O notation.