消息的最短可預期長度

一個包包含16個以下顏色的球：8紅色，4藍色，2綠色，1黑色和1白色。 Anisha從包裏隨機挑選一個球，並使用一串零和一個字符串給Babu發送它的顏色。她將袋子中的球取代並多次重複該實驗。每個實驗必須傳達給巴布的最短預期長度是多少？
的（a）3/2 （b）中記錄5 （c）中15/8 （d）31/16 （E）2消息的最短可預期長度

據我，由於球取出與更換。在任何時候，袋子裏都有16個不同顏色的球。爲了編碼5種顏色，應該需要log5（基數2）的上限，即3位，但給出的答案是（15/8）。有人能指出我的錯誤，並提供正確解決方案的一些提示嗎？

來源

2014-12-13 Racing

你的錯誤是張貼在網站上編程。請考慮重新發布此http://math.stackexchange.com/ – kinbiko 2014-12-13 08:55:42

使用靜態霍夫曼壓縮，您可以使用比罕見顏色更少的位對更常見的顏色進行編碼，這種情況下可以預期通常會選擇常用顏色。

如：

red 1 
blue 01 
green 001 
white 0001 
black 0000

平均爲16平會有

8 reds = 8 bits 
4 blues = 8 bits 
2 greens = 6 bits 
1 white = 4 bits 
1 black = 4 bits

的平均

來源

2014-12-13 09:07:47 Jasen

你的回答共30/16位是正確的最大值編碼需要。但考慮下面的編碼方案1-紅（1/2概率），01-藍（1/4概率），00-綠（1/8概率），001-黑（1/16概率），000-白（ 1/16概率）乘以概率的消息長度，你應該有1 + 5/8（不是15/8 ...雖然）

來源

2014-12-13 09:10:40 lonewasp

似乎不正確，如果A.發送001是綠色後面是紅色，還是黑色？ – Jasen 2014-12-14 03:34:55

您的問題讓我們瞭解到溝通渠道細節，可靠的信息傳遞和錯誤檢測/糾正碼。考慮像0/1編碼這樣的莫爾斯碼，消息之間保持沉默 - Anisha的實驗並不是即時的。對於「純粹的」最小平均消息長度，我仍然會考慮具有最小消息概率的消息集{0,1,00,01,000}。 – lonewasp 2014-12-18 20:35:19

消息的最短可預期長度

回答

相關問題