My Math Forum Information Theory exercise

 Probability and Statistics Basic Probability and Statistics Math Forum

 December 25th, 2016, 10:03 AM #1 Newbie   Joined: Dec 2016 From: US Posts: 6 Thanks: 0 Information Theory exercise Anyone could please tell me how to solve this exercise? Let there be $\displaystyle n+1$ boxes labeled $\displaystyle \omega=1,2,...,n$. One of the boxes contains a prize, the others are empty. The probability $\displaystyle p_0$ that the prize is in $\displaystyle \omega=0$ is much larger than the probability that it is in any other box: $\displaystyle p_0>>p_{\omega>0}$ and we take $\displaystyle p_{\omega>0}=\frac{1-p_0}{n}$ for simplicity. Note that, if $\displaystyle n$ is large, $\displaystyle p_0$ can nonetheless be also small. There are two possible options: 1) open the box $\displaystyle \omega=0$; 2) open simultaneously all boxes $\displaystyle \omega>\frac{n}{2}$ (imagine $\displaystyle n$ is even). Which one is the most convenient? Which one conveys most information on where the prize actually is?
December 25th, 2016, 07:59 PM   #2
Senior Member

Joined: Sep 2015
From: CA

Posts: 1,304
Thanks: 669

Quote:
 Originally Posted by mike22 Anyone could please tell me how to solve this exercise? Let there be $\displaystyle n+1$ boxes labeled $\displaystyle \omega=1,2,...,n$. One of the boxes contains a prize, the others are empty. The probability $\displaystyle p_0$ that the prize is in $\displaystyle \omega=0$ is much larger than the probability that it is in any other box: $\displaystyle p_0>>p_{\omega>0}$ and we take $\displaystyle p_{\omega>0}=\frac{1-p_0}{n}$ for simplicity. Note that, if $\displaystyle n$ is large, $\displaystyle p_0$ can nonetheless be also small. There are two possible options: 1) open the box $\displaystyle \omega=0$; 2) open simultaneously all boxes $\displaystyle \omega>\frac{n}{2}$ (imagine $\displaystyle n$ is even). Which one is the most convenient? Which one conveys most information on where the prize actually is?
What I'd think you want to do is select the method that produces the least random distribution as the outcome.

Method 1 has 2 outcomes

The prize is in box 0. The distribution becomes $\{1, 0, 0\dots, 0\}$
This occurs with probability $p_0$ and has entropy 0

The prize is not in box 0. The distribution becomes $\left \{0, \dfrac 1 n, \dfrac 1 n, \dots, \dfrac 1 n\right \}$
This occurs with probability $1-p_0$ and has entropy $\log(n)$

One can calculate an expected value of $H_1$ as $p_0$ ranges from $0 \to 1$

Similarly Method 2 has 2 outcomes

The prize is in one of the $\dfrac n 2$ boxes you open. The resulting distribution is $\{0, 0, \dots 1, 0, \dots \}$
This occurs with probability $\dfrac{1-p_0}{n}$ and has entropy 0.

The prize is not in one of the $\dfrac n 2$ boxes you open. The resulting distribution is (you'll have to show this)

$\left \{\dfrac{2p_0}{1+p_0}, \underset{\dfrac n 2}{\underbrace{\dfrac 2 n \dfrac{1-p_0}{1+p_0}, \dfrac 2 n \dfrac{1-p_0}{1+p_0}, \dots, \dfrac 2 n \dfrac{1-p_0}{1+p_0}}},\underset{\dfrac n 2}{\underbrace{0,0,\dots, 0}}\right \}$

and has it's associated average entropy.

You'll find method 2 provides a lower average entropy a posteori distribution across the entire range of $p_0$

 Tags entropy, exercise, information, mutual, probability, theory

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post wtdf0201 Number Theory 2 January 19th, 2014 03:20 PM binek Calculus 0 October 15th, 2011 05:38 AM peter20 Applied Math 1 January 29th, 2010 12:10 AM kiwimath Algebra 1 July 17th, 2009 09:40 AM trid2 Advanced Statistics 1 March 1st, 2009 06:24 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top