I'm trying to understand algorithm L from reservoir sampling. One of the steps mentions that given n samples independently drawn from a uniform distribution U(0,1), we can simulate drawing n samples and getting the max with just drawing 1 sample can raising it to the power of 1/n.
That is max{random()_1, ...random()_n} = random()^(1/n)
Does anyone know how we get this result? Thanks
Define $z \sim D_z :=\max(r_1,\dots, r_n)$ for $r_i \sim_{\text{iid}} U(0,1)$ is $P(z \le s) = s^n$, (Proof), and reference its distribution by $D_z$.
Further, we can define $a \sim D_a:=U(0,1)^{1/n}$ and $t=a^{n}$, we have $P(a \le s) = P(t\le s^{n}) =s^{n}$.
Therefore, $P(z \le s)=s^n=P(a \le s)$, implying $D_a=D_z$ as suggested.