My Math Forum  

Go Back   My Math Forum > High School Math Forum > Probability and Statistics

Probability and Statistics Basic Probability and Statistics Math Forum


Reply
 
LinkBack Thread Tools Display Modes
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?
mike22 is offline  
 
December 25th, 2016, 07:59 PM   #2
Senior Member
 
romsek's Avatar
 
Joined: Sep 2015
From: Southern California, USA

Posts: 1,503
Thanks: 758

Quote:
Originally Posted by mike22 View Post
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$
romsek is online now  
Reply

  My Math Forum > High School Math Forum > Probability and Statistics

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 03: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 12: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 06:24 PM





Copyright © 2017 My Math Forum. All rights reserved.