14
$\begingroup$

I'm starting to learn about information theory and I'm a bit stuck on this one. here's what I have so far:

1 possible strategy is to simply ask 'did outcome 1 occur?' if yes then we have our answer, if no we ask again 'did outcome 2 occur' etc. for a dice, the maximum number of questions with this strategy would be 5, since if for 1 - 5 the answer is no, that must mean that the outcome 6 must be positive. Based on my calculation, the average number of questions using this strategy is 2.5 (sum from 1 to 5 of $Q/6$, where Q is number of questions and 1/6 is the probabilty of rolling any of the faces on the dice).

Another strategy I thought of would be to split the probabilties – i.e. is the outcome even? if yes, we could ask 'is it greater than 3?' and then we either have the outcome (6) or we ask 'is it 4?' and from here we have a definitive answer. Likewise for the case of the first answer being no i.e. the number is odd.

I struggled to calculate the average number of questions for this. My logic was we must ask at least 2 questions for the answer to be fully determined. So, we must ask 1 question and then the outcome of the second question is subject to probabilty. Hence the average number of questions is: $1+(2/6)+(3/6)=1.83333...$

Is this right? Is my logic correct? Are there any other strategies worth looking at?

I'm really enjoying imformation theory and am really keen to learn more more more!

$\endgroup$
1

5 Answers 5

21
$\begingroup$

Each yes-no question asked can provide at most one bit of information. A fair dice roll has six equally probable outcomes, so $\log_26=2.585$ bits of entropy. Any strategy to correctly guess the dice roll cannot use fewer than this many questions on average.

A strategy that halves the search space with each new question as evenly as possible will take two questions to correctly guess for two rolls (say 1, 6) and three questions for the other four rolls, thus averaging $\frac83=2.667$ questions. This is optimal, since if three rolls only required two questions the average number of questions would be 2.5 – below the theoretical lower bound.

The strategy that asks whether the roll is 1, then 2, then 3 and so on requires 5 questions if the roll was 5 or 6, thus requiring $\frac{1+2+3+4+5+5}6=\frac{10}3=3.333$ questions on average; it is sub-optimal.

$\endgroup$
11
$\begingroup$

Your question is essentially a coding problem. When you have decided on your strategy, each outcome is a series of yes-no-answers. By encoding "yes" answers as $1$ and "no" answers as $0$, you get a binary codeword for each of the outcomes.

The set of the codewords must be a prefix code, that is, no codeword is a prefix of another. That's because, for example, if one outcome corresponds to answer sequence "yes-no-yes", you clearly can't have a outcome that corresponds to answer sequence "yes-no". (Otherwise you'd know the answer after 2 questions but still would ask a third question which would change the answer, which is clearly impossible.)

On the other hand, you can transform a prefix code to a question strategy; you'll just formulate your $k$th question as "Using this coding, is the $k$th bit in the codeword $1$?" and stop when you know the answer.

So your question is exactly equivalent to "What is the most efficient prefix code for a die throw outcome?" Here, efficiency is the expected value of the length of the codeword.

Given a known set of outcomes with a known probability distribution, the most efficient prefix code is the Huffman code. I'll leave constructing the code as an exercise for the reader, but the optimal expected length in this case is $2+\frac{2}{3}$.

$\endgroup$
1
3
$\begingroup$

For your first idea I'm not sure the estimation is correct. $1$ takes one guess, $2$ takes two, and so on, until $5$ takes five, and $6$ also takes five. So the estimate will be:

$\frac 16 +\frac 26 + \frac 36 +\frac 46 + \frac 56 +\frac 56 = 3 \frac 13.$

For the second method you have already said that there must be at least $2$ guesses, so how can the average be $1.8333...$? If you eliminate half on the first question you can get two numbers on the second guess, and the other four on the third question. So your estimate will be

$2 \times \frac 26 + 4 \times \frac 36 = 2 \frac 23.$

From here you can see that this is the better strategy of the two you've mentioned.

$\endgroup$
0
$\begingroup$

Let's look at this problem from a pure probabilistic point of view.

You have a probabilistic space $\Omega = \{1, 2, 3, 4, 5, 6\}$ with a $\sigma\text{-set}$ $P=2^{\Omega}$ (so any subset of $\Omega$ is in your $P$ and discrete probability with $p(n)=p(\{n\})=\frac{1}{6}$.

Now for each strategy you have a set of finite questions. For each of the 1-element sets from $P$ you can define what will be the answers to your set of question and as a result you'll see how many answers were provided. Your random variable $X$ is the number of questions asked for a given result and expected value $E|X$ is a product sum of random variable and respective probability, in your case it is $\Sigma_{i=1}^6p(i)\cdot X(i)=\frac16\Sigma_{i=1}^6X(i)$

Note, the abstract terms are useful for any probabilistic space and strategy, you may just need to adapt some of the formulas.

Now for your given examples, the strategy where you ask "Is it 1, is it 2..." etc your random variable $X_1$ is as follows (answers to questions in brackets): $$X_1(1)=1\text{ \{y\}}$$ $$X_1(2)=2\text{ \{ny\}}$$ $$X_1(3)=3\text{ \{nny\}}$$ $$X_1(4)=4\text{ \{nnny\}}$$ $$X_1(5)=5\text{ \{nnnny\}}$$ $$X_1(6)=5\text{ \{nnnnn\}}$$ So your expected value is $$E_1=\frac16\Sigma_{i=1}^6 X_1(i)=\frac{20}6=3\frac13$$

The difference compared to your result $2.5$ comes from the fact that you ignored that you need to ask 5 questions twice as often as you ask other questions.

Your second strategy cuts half of your remaining numbers (on average). Let's say your first two questions are always "Is it even" and then "Is it greater than 3". If those two doesn't provide you with a definite result you have two choices and need to ask one more question (let's assume you'll always ask about the lower possible number).

With this strategy your random variable $X_2$ and expected value $E_2$ are like that: $$X_1(1)=3\text{ \{nny\}}$$ $$X_1(2)=2\text{ \{yn\}}$$ $$X_1(3)=3\text{ \{nnn\}}$$ $$X_1(4)=3\text{ \{yyy\}}$$ $$X_1(5)=2\text{ \{ny\}}$$ $$X_1(6)=3\text{ \{yyn\}}$$ $$E_2=\frac16\Sigma_{i=1}^6 X_1(i)=\frac{16}6=2\frac23$$

I can't actually guess how did you calculate your second result so I'm not able to answer what did you do wrong.

As you can see the second strategy is better.

You also see how to properly calculate it for any other example.

$\endgroup$
0
$\begingroup$

Sequential questions indeed require on average $$\frac{1+2+3+4+5+5}6=\frac{10}3$$ trials.

If you split in two equal sets of $3$, there is no better option than sequential questions among $3$, and in total that takes

$$1+\frac{1+2+2}3=\frac83$$ trials.

More generally, the optimal strategy is two always split the current subset in two halves (ties broken arbitrarily).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .