Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
For why this matters, see $\:$ www.cs.utexas.edu/~shmat/shmat_esorics06.pdf . $\;\;$ –  Ricky Demer Dec 7 '12 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 '12 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 '12 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 '12 at 2:58
    
OK, but you asked to minimize the function (=maximized the entropy)... –  Ori Gurel-Gurevich Dec 8 '12 at 3:10

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.