Blind sampling is optimal when nothing is known: if E[π_j²] is the same for every key, every proposal has cost ≥ n·E[Σπ²] and uniform attains it

For all $\htmlData{mx=1}{J \in \htmlData{mx=0}{\operatorname{Type}}}$, $\htmlData{mx=3}{A, r : \htmlData{mx=0}{J} \mathrel{\htmlData{mx=2}{\to}} \htmlData{mx=1}{\mathbb{R}}}$ and $\htmlData{mx=1}{\mathit{Abar} \in \htmlData{mx=0}{\mathbb{R}}}$, if $\htmlData{mx=5}{\forall j,\ \htmlData{mx=2}{\htmlData{mx=0}{A}(\htmlData{mx=1}{j})} \mathrel{\htmlData{mx=4}{=}} \htmlData{mx=3}{\mathit{Abar}}}$, $0 \mathrel{\htmlData{mx=1}{\leq}} \htmlData{mx=0}{\mathit{Abar}}$, $\htmlData{mx=4}{\forall j,\ 0 \mathrel{\htmlData{mx=3}{<}} \htmlData{mx=2}{\htmlData{mx=0}{r}(\htmlData{mx=1}{j})}}$ and $\htmlData{mx=3}{\sum_{j} \htmlData{mx=2}{\htmlData{mx=0}{r}(\htmlData{mx=1}{j})}} \mathrel{\htmlData{mx=4}{=}} 1$ (given $\htmlData{mx=2}{\htmlData{mx=0}{\operatorname{Fintype}}\,\htmlData{mx=1}{J}}$ and $\htmlData{mx=2}{\htmlData{mx=0}{\operatorname{Nonempty}}\,\htmlData{mx=1}{J}}$), then