Chỉnh sửa:
Dựa trên nhận xét của OP, một cách nghĩ về sự khác biệt giữa Guesswork và Shannon Entropy là như sau:
Shanon: Giả sử chúng ta có một biến ngẫu nhiên để mã hóa. Với sự phân phối của nó, mã Huffman hoặc quy trình mã hóa nguồn khác có thể được sử dụng và chiều dài dự kiến của các từ mã trong mã đó được liên kết chặt chẽ với entropy Shannon của biến ngẫu nhiên. Cây mã Huffman mô tả một quá trình đệ quy trong đó mạnh tùy ý các truy vấn có thể được thực hiện từ biến ngẫu nhiên. Ví dụ, người ta có thể yêu cầu, cho $X\in {1,\ldots,N\}$ câu hỏi
Là $X \leq N/3$?
và chọn nhánh trái của cây từ gốc nếu câu trả lời là có. Trong trường hợp của Huffman, chúng tôi muốn thu nhỏ cái cây và mặc dù chúng tôi sử dụng quy trình "hợp nhất" các lá từ dưới lên, nhưng cuối cùng, nếu câu hỏi là câu hỏi ở trên, thì $Pr[X\leq N/3]\approx 1/2.$ Chúng tôi tách trái/phải tại một điểm khiến xác suất của hai cây con cân bằng.
Phỏng đoán: Trong bối cảnh này, truy vấn không thể mạnh tùy ý nó thường là nguyên tử. Ý tôi là trong khi dựng cây, chúng ta được phép đặt một câu hỏi ở dạng
Là $X=1$?
Ví dụ. Giả định $Pr[X=1]$ là xác suất nguyên tử lớn nhất của dạng $Pr[X=x]$ ở đâu
$x\in \{1,2,\ldots,N\}$ đây là câu hỏi hay nhất để giảm thiểu số lần đoán. Trong trường hợp này, bạn vẫn sẽ có một cây nhưng cấu trúc chi phí thay đổi, bạn không thể loại trừ một cây con nếu câu trả lời là Không bạn chỉ có thể loại trừ một giá trị $X=1,$ Đây là những gì dẫn đến Đoán entropy hoặc $H_{1/2}(X).$
Các ứng dụng nơi điều này được sử dụng bao gồm các cuộc tấn công đoán lực lượng vũ phu. bạn không thể hỏi Chữ cái đầu tiên của mật khẩu có phải là A không? bạn cần nhập mật khẩu đầy đủ và được vào hoặc bị từ chối. Đây là lý do tại sao bạn không thể sử dụng các câu hỏi nguyên tử và hỏi về các phần của chuỗi chưa biết.
Lý lịch:
Đã có một số cuộc thảo luận ở đây về Đoán entropy (thực ra là Renyi entropy bậc 1/2) trong các câu hỏi dưới đây:
sự khác biệt giữa Shannon và Guessing entropies
bảo mật của xác thực mật khẩu được cung cấp entropy
Tóm lại, nếu bạn lo lắng về số lần đoán trung bình để xác định một biến ngẫu nhiên chưa biết thì bạn nên sử dụng Entropy đoán chứ không phải entropy Shannon vì entropy trước đây bị ràng buộc chặt chẽ với số lần đoán dự kiến.
Entropy trật tự Renyi $\alpha$ được định nghĩa bởi
$$
H_{\alpha}(X)=\frac{1}{1-\alpha} \log \left(\sum_{x} Pr(X=x)^{\alpha} \right)
$$
ở đâu $\alpha \in [0,1) \cup (1,\infty).$ Nó tuân theo
$$
\lim_{\alpha\rightarrow 1} H_{\alpha}(X)=H(X).
$$
Nó được thể hiện bởi John Pliam (xem đây ) nếu như $X$ là một biến ngẫu nhiên rời rạc với $M$ điểm hỗ trợ của nó $H(X)$ có thể gần với giá trị tối đa của nó $\log M$ trong khi xác suất của một người đoán tối ưu phát hiện ra giá trị thực của $X$ Trong $k$ câu hỏi tuần tự là ít hơn nhiều so với $2^{H(X)}=M.$
Hơn nữa, không chỉ số lần đoán dự kiến, mà cả những khoảnh khắc tùy ý
số lần đoán có thể liên quan đến các entropy Renyi theo thứ tự khác nhau.
Một kết quả dựa trên kỳ vọng là số lần đoán dự kiến
quyết tâm
một biến ngẫu nhiên $X$ (đối với trình tự đoán tối ưu) là
giới hạn trên bởi
$$2^{H_{1/2}(X)-1}$$
ở đâu $H_{1/2}(X)$ biểu thị entropy trật tự Renyi $\alpha=1/2$ và còn được gọi là đoán entropy. Hơn nữa, nó bị giới hạn dưới bởi (đối với tất cả các chuỗi đoán)
$$\frac{2^{H_{1/2}(X)}}{1 + \log M } \approx 2^{H_{1/2}(X)} / H_{max}(X)$ $
ở đâu $H_{max}(X)$ là entropy cực đại $\log M$ ở Renyi
hay vụ Shannon.
