
Probability and Statistics Basic Probability and Statistics Math Forum 
 LinkBack  Thread Tools  Display Modes 
December 25th, 2016, 11: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{1p_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, 08:59 PM  #2  
Senior Member Joined: Sep 2015 From: CA Posts: 936 Thanks: 506  Quote:
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 $1p_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{1p_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{1p_0}{1+p_0}, \dfrac 2 n \dfrac{1p_0}{1+p_0}, \dots, \dfrac 2 n \dfrac{1p_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  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
an exercise from number theory  wtdf0201  Number Theory  2  January 19th, 2014 04:20 PM 
Evil integral in theory of information formula  binek  Calculus  0  October 15th, 2011 05:38 AM 
Queueing theory exercise ? SOS  peter20  Applied Math  1  January 29th, 2010 01:10 AM 
the exercise presents numerical information ?  kiwimath  Algebra  1  July 17th, 2009 09:40 AM 
Entropy (information theory)  trid2  Advanced Statistics  1  March 1st, 2009 07:24 PM 