3

$H$ is (Shannon) entropy.

In terms of the positive real number $t$, what distribution(s) $\hspace{.01 in}X$ on $\:[0\hspace{.005 in},\hspace{-0.03 in}\scriptsize+\normalsize\infty\hspace{-0.02 in})$
with mean $1$ will minimize the value of the following (one-player) game?


Player chooses a real number $s$ such that $\: 0 < s \leq t \:$ and a
finite partition $\:\left\langle B_0,...,B_n \right\rangle\:$ of $\:[0\hspace{.005 in},\hspace{-0.03 in}\scriptsize+\normalsize\infty\hspace{-0.02 in})^2$ into universally measurable sets.

Have $\;\;\; f \: : \: [0\hspace{.005 in},\hspace{-0.03 in}\scriptsize+\normalsize\infty\hspace{-0.02 in})^2 \: \to \: \{0\hspace{.005 in},...,\hspace{-0.01 in}n\} \;\;\;$ be given by $\;\; \langle x,\hspace{-0.03 in}y\rangle \: \in \: B_{f(\langle x,y\rangle)} \;\;\;$.

Challanger samples $x$ and $y$ independently from $X$, samples $b$ uniformly from $\{0\hspace{.005 in},\hspace{-0.04 in}1\}$,$\:$ then gives Player $\langle w,\hspace{-0.01 in}z\hspace{.01 in}\rangle \;\; := \;\; \begin{cases} \langle x,y+s\rangle & \text{if } \: b=0 \\ \langle x+s,y\rangle & \text{if } \: b=1 \end{cases}$

Player's score is $\:-\big(H\big(b \: | \; f(\langle w,\hspace{-0.01 in}z\hspace{.01 in}\rangle\big)\big) \;\;$.

flag
For why this matters, see $\:$ www.cs.utexas.edu/~shmat/shmat_esorics06.pdf . $\;\;$ – Ricky Demer Dec 7 at 21:40
Without trying to understand the details of your question but only reading the title, I would guess that the answer would be "Poisson". – Steve Huntsman Dec 7 at 21:42
What's the restriction on the partition? If the player chooses the trivial partition, the entropy is maximized. – Ori Gurel-Gurevich Dec 8 at 2:51
If the player chooses the trivial partition then the player's score is $-1$, $\hspace{1.8 in}$ which is the worst possible (for the player). $\:$ – Ricky Demer Dec 8 at 2:58
OK, but you asked to minimize the function (=maximized the entropy)... – Ori Gurel-Gurevich Dec 8 at 3:10
show 1 more comment

Your Answer

Get an OpenID
or

Browse other questions tagged or ask your own question.