3
$\begingroup$

$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) \;\;$.

Improve this question
$\endgroup$
6
  • $\begingroup$ For why this matters, see $\:$ www.cs.utexas.edu/~shmat/shmat_esorics06.pdf . $\;\;$ $\endgroup$
    – user5810
    Commented Dec 7, 2012 at 21:40
  • $\begingroup$ Without trying to understand the details of your question but only reading the title, I would guess that the answer would be "Poisson". $\endgroup$
    – Steve Huntsman
    Commented Dec 7, 2012 at 21:42
  • $\begingroup$ What's the restriction on the partition? If the player chooses the trivial partition, the entropy is maximized. $\endgroup$
    – Ori Gurel-Gurevich
    Commented Dec 8, 2012 at 2:51
  • $\begingroup$ 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). $\:$ $\endgroup$
    – user5810
    Commented Dec 8, 2012 at 2:58
  • $\begingroup$ OK, but you asked to minimize the function (=maximized the entropy)... $\endgroup$
    – Ori Gurel-Gurevich
    Commented Dec 8, 2012 at 3:10

0

Reset to default

You must log in to answer this question.