Problem $4.(30$ points$)$

$($a$)$ You have multiple bikes to sell. For simplicity, assume that you get one offer every day, with Xi denoting the offer received on day i$.$ Here X$1,$ X$2,...$ are a sequence of independent random variables uniformly distributed in $[0,1].$ Now suppose that you accept every offer Xi$,$i $>=2$ such that Xi $>$ X$1.$ You always reject the offer X$1$ on day $1.$ Let Yn be the number of accepted offers until and including day n$.$ That is$,$ Yn $=$ Pni$=2$ I$($Xi $>$ X$1),$ where I$()$ is the indicator function. What is E$[$Yn$]?$

$1$A standard $52-$card deck is the set $\{2,3,4,5,6,7,8,9,10,$ jack, queen, king, ace$\}\backslash$times $\{$clubs$,$ diamonds, hearts, spades$\}.$

$1$

$($b$)$ Consider the problem setting in part $($a$)$ again, and now let Zn be the number of accepted offers until and including day n assuming X$1=1/2.$ That is$,$ Zn $=$ Pni$=2$ I$($Xi $>1/2),$ where I$()$ is the indicator function. What is E$[$Zn$]?$ Also, prove that with probability at least $1\backslash$delta $,$ for any $\backslash$delta in $(0,1),$ we have that Zn $<=$ n$2+$ O$($pn log$(1/\backslash$delta $)).$ That is$,$

PrZn $<=$ n$2+$O$($pnlog$(1/\backslash$delta $)>=1\backslash$delta

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