$\%$Q$4$

$\backslash$item Suppose we were to modify the $\{\backslash$em Go$-$with$-$weighted$-$Majority$\}$ algorithm where instead of attenuating the weight of each expert by $$1/2$$ on making a mistake, we attenuated by a factor of $$(1-\backslash$varepsilon$)$$$,$ for some $$\backslash$varepsilon $\backslash$in $(0,1/2)$$$.$ All other details of the algorithm remains the same.

$\backslash$hfill$\{(\{\backslash$bf $15$ points each$\})\}$

$\backslash$begin$\{$enumerate$\}$

$\%$Q$4$a

$\backslash$item For each round $t$$,$ let $w$\_\{$t$\}^\{($i$)\}$$ denote the weight of the $i$$\backslash$textsuperscript$\{$th$\}$ expert after round $t$$,$ and let $W$\_$t $=\backslash$sum$\_\{$i$=1\}^$N w$\_\{$t$\}^\{($i$)\}$$$.$ Let $T$ be the total number of rounds our algorithm runs for, and let $M$ be our algorithm's loss. Show that $W$\_$T $\backslash$le $(1-\backslash$varepsilon$/2)^$M $\backslash$cdot N$$.$