Expected length of message in communication
up vote
0
down vote
favorite
The problem goes as follows:
A bag contains 16 balls of following colors: 8 red, 4 blue, 2 green, 1 black and 1 white. Alice picks a ball randomly from the bag and messages Bob its color using a string of zeros and ones. She replaces the ball in the bag and repeats this experiment many times. What is the minimum expected length of the message she has to convey to Bob per experiment?
Now, what I thought was that since we have to find the expected length of message, we can design an encoding for the colour of the balls.
So, we can represent it as:
Red = 0, Blue = 1, Green = 01, Black = 11 and White = 100.
Using this, I got the expected number of bits as:
$8 times 1 + 4 times 1 +2 times 2 + 1 times 2 + 1 times 3 = 21$, and dividing this 16 for the total number of draws, I got the answer as $21/16$.
However, this does not match with the solution.
What should be the correct approach?
expected-value
asked Dec 5 at 12:42
Gokul
332318
add a comment |
up vote
0
down vote
favorite
The problem goes as follows:
A bag contains 16 balls of following colors: 8 red, 4 blue, 2 green, 1 black and 1 white. Alice picks a ball randomly from the bag and messages Bob its color using a string of zeros and ones. She replaces the ball in the bag and repeats this experiment many times. What is the minimum expected length of the message she has to convey to Bob per experiment?
Now, what I thought was that since we have to find the expected length of message, we can design an encoding for the colour of the balls.
So, we can represent it as:
Red = 0, Blue = 1, Green = 01, Black = 11 and White = 100.
Using this, I got the expected number of bits as:
$8 times 1 + 4 times 1 +2 times 2 + 1 times 2 + 1 times 3 = 21$, and dividing this 16 for the total number of draws, I got the answer as $21/16$.
However, this does not match with the solution.
What should be the correct approach?
expected-value
asked Dec 5 at 12:42
Gokul
332318
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
The problem goes as follows:
A bag contains 16 balls of following colors: 8 red, 4 blue, 2 green, 1 black and 1 white. Alice picks a ball randomly from the bag and messages Bob its color using a string of zeros and ones. She replaces the ball in the bag and repeats this experiment many times. What is the minimum expected length of the message she has to convey to Bob per experiment?
Now, what I thought was that since we have to find the expected length of message, we can design an encoding for the colour of the balls.
So, we can represent it as:
Red = 0, Blue = 1, Green = 01, Black = 11 and White = 100.
Using this, I got the expected number of bits as:
$8 times 1 + 4 times 1 +2 times 2 + 1 times 2 + 1 times 3 = 21$, and dividing this 16 for the total number of draws, I got the answer as $21/16$.
However, this does not match with the solution.
What should be the correct approach?
expected-value
asked Dec 5 at 12:42
Gokul
332318
The problem goes as follows:
A bag contains 16 balls of following colors: 8 red, 4 blue, 2 green, 1 black and 1 white. Alice picks a ball randomly from the bag and messages Bob its color using a string of zeros and ones. She replaces the ball in the bag and repeats this experiment many times. What is the minimum expected length of the message she has to convey to Bob per experiment?
Now, what I thought was that since we have to find the expected length of message, we can design an encoding for the colour of the balls.
So, we can represent it as:
Red = 0, Blue = 1, Green = 01, Black = 11 and White = 100.
Using this, I got the expected number of bits as:
$8 times 1 + 4 times 1 +2 times 2 + 1 times 2 + 1 times 3 = 21$, and dividing this 16 for the total number of draws, I got the answer as $21/16$.
However, this does not match with the solution.
What should be the correct approach?
expected-value
expected-value
asked Dec 5 at 12:42
Gokul
332318
asked Dec 5 at 12:42
Gokul
332318
asked Dec 5 at 12:42
Gokul
332318
asked Dec 5 at 12:42
Gokul
332318
asked Dec 5 at 12:42
Gokul
332318
332318
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
up vote
0
down vote
You should be able to use some kind of compression when sending your data.
Because there are a different number of each color of ball i would suggest using A binary tree type of compression. Huffman compression is ideal for this.
Here's a great video on it Link
If you pre-compute the tree (and both Bob and Alice have access to it) that should be the best possible message size
answered Dec 5 at 12:47
TheD0ubleT
37718
I think this does align with Huffman encoding - we've used only one bit for the most frequent colour and then increased it from there. Can we do better than that?
– Gokul
Dec 5 at 12:51
I don't believe so. it should be the best mathematical possiblility. (or you could send nothing if it's red, 1 bit if it's blue...) But that means you have to send your data at regular intervals otherwise if you wait too long it will be counted as a red ball
– TheD0ubleT
Dec 5 at 12:54
Okay, when I do use the Huffman encoding, I get the correct answer. However, it's more than the method I've used above. I don't see what's wrong with what I've used as there is no ambiguity.
– Gokul
Dec 5 at 12:58
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3027023%2fexpected-length-of-message-in-communication%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
You should be able to use some kind of compression when sending your data.
Because there are a different number of each color of ball i would suggest using A binary tree type of compression. Huffman compression is ideal for this.
Here's a great video on it Link
If you pre-compute the tree (and both Bob and Alice have access to it) that should be the best possible message size
answered Dec 5 at 12:47
TheD0ubleT
37718
I think this does align with Huffman encoding - we've used only one bit for the most frequent colour and then increased it from there. Can we do better than that?
– Gokul
Dec 5 at 12:51
I don't believe so. it should be the best mathematical possiblility. (or you could send nothing if it's red, 1 bit if it's blue...) But that means you have to send your data at regular intervals otherwise if you wait too long it will be counted as a red ball
– TheD0ubleT
Dec 5 at 12:54
Okay, when I do use the Huffman encoding, I get the correct answer. However, it's more than the method I've used above. I don't see what's wrong with what I've used as there is no ambiguity.
– Gokul
Dec 5 at 12:58
add a comment |
up vote
0
down vote
You should be able to use some kind of compression when sending your data.
Because there are a different number of each color of ball i would suggest using A binary tree type of compression. Huffman compression is ideal for this.
Here's a great video on it Link
If you pre-compute the tree (and both Bob and Alice have access to it) that should be the best possible message size
answered Dec 5 at 12:47
TheD0ubleT
37718
I think this does align with Huffman encoding - we've used only one bit for the most frequent colour and then increased it from there. Can we do better than that?
– Gokul
Dec 5 at 12:51
I don't believe so. it should be the best mathematical possiblility. (or you could send nothing if it's red, 1 bit if it's blue...) But that means you have to send your data at regular intervals otherwise if you wait too long it will be counted as a red ball
– TheD0ubleT
Dec 5 at 12:54
Okay, when I do use the Huffman encoding, I get the correct answer. However, it's more than the method I've used above. I don't see what's wrong with what I've used as there is no ambiguity.
– Gokul
Dec 5 at 12:58
add a comment |
up vote
0
down vote
up vote
0
down vote
You should be able to use some kind of compression when sending your data.
Because there are a different number of each color of ball i would suggest using A binary tree type of compression. Huffman compression is ideal for this.
Here's a great video on it Link
If you pre-compute the tree (and both Bob and Alice have access to it) that should be the best possible message size
answered Dec 5 at 12:47
TheD0ubleT
37718
You should be able to use some kind of compression when sending your data.
Because there are a different number of each color of ball i would suggest using A binary tree type of compression. Huffman compression is ideal for this.
Here's a great video on it Link
If you pre-compute the tree (and both Bob and Alice have access to it) that should be the best possible message size
answered Dec 5 at 12:47
TheD0ubleT
37718
answered Dec 5 at 12:47
TheD0ubleT
37718
answered Dec 5 at 12:47
TheD0ubleT
37718
answered Dec 5 at 12:47
TheD0ubleT
37718
37718
I think this does align with Huffman encoding - we've used only one bit for the most frequent colour and then increased it from there. Can we do better than that?
– Gokul
Dec 5 at 12:51
I don't believe so. it should be the best mathematical possiblility. (or you could send nothing if it's red, 1 bit if it's blue...) But that means you have to send your data at regular intervals otherwise if you wait too long it will be counted as a red ball
– TheD0ubleT
Dec 5 at 12:54
Okay, when I do use the Huffman encoding, I get the correct answer. However, it's more than the method I've used above. I don't see what's wrong with what I've used as there is no ambiguity.
– Gokul
Dec 5 at 12:58
add a comment |
I think this does align with Huffman encoding - we've used only one bit for the most frequent colour and then increased it from there. Can we do better than that?
– Gokul
Dec 5 at 12:51
I don't believe so. it should be the best mathematical possiblility. (or you could send nothing if it's red, 1 bit if it's blue...) But that means you have to send your data at regular intervals otherwise if you wait too long it will be counted as a red ball
– TheD0ubleT
Dec 5 at 12:54
Okay, when I do use the Huffman encoding, I get the correct answer. However, it's more than the method I've used above. I don't see what's wrong with what I've used as there is no ambiguity.
– Gokul
Dec 5 at 12:58
I think this does align with Huffman encoding - we've used only one bit for the most frequent colour and then increased it from there. Can we do better than that?
– Gokul
Dec 5 at 12:51
I think this does align with Huffman encoding - we've used only one bit for the most frequent colour and then increased it from there. Can we do better than that?
– Gokul
Dec 5 at 12:51
I don't believe so. it should be the best mathematical possiblility. (or you could send nothing if it's red, 1 bit if it's blue...) But that means you have to send your data at regular intervals otherwise if you wait too long it will be counted as a red ball
– TheD0ubleT
Dec 5 at 12:54
I don't believe so. it should be the best mathematical possiblility. (or you could send nothing if it's red, 1 bit if it's blue...) But that means you have to send your data at regular intervals otherwise if you wait too long it will be counted as a red ball
– TheD0ubleT
Dec 5 at 12:54
Okay, when I do use the Huffman encoding, I get the correct answer. However, it's more than the method I've used above. I don't see what's wrong with what I've used as there is no ambiguity.
– Gokul
Dec 5 at 12:58
Okay, when I do use the Huffman encoding, I get the correct answer. However, it's more than the method I've used above. I don't see what's wrong with what I've used as there is no ambiguity.
– Gokul
Dec 5 at 12:58
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3027023%2fexpected-length-of-message-in-communication%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
