Sự cố tìm lỗi trong lon cà phê
Tôi không thể hiểu giải pháp mà tôi đã được đưa ra cho vấn đề này:
12 lon cà phê chứa đầy 12 ounce cà phê. 1 trong số các lon bị lỗi và có nhiều hơn hoặc ít hơn 12 ounce. Sử dụng một cái cân, trong đó 12 lon có thể vừa với hai bên của cân. Chúng tôi muốn sử dụng số dư để xác định cái nào có thể có lỗi. Số phép đo tối thiểu cần thiết để tìm lon bị lỗi là bao nhiêu?
Giải pháp mà tôi được đưa ra là: Vì cơ hội cho $12$ lon nặng hơn hoặc nhẹ hơn đều có khả năng như nhau, có $24$ trường hợp có xác suất $\frac{1}{24}$và thông tin dự kiến của vấn đề là $-\sum_{i=1}^{24} 1/24 \cdot log_2(1/24) = 3 + log_2(3)$ chút ít.
Có $3$khả năng đo, hai bên cân bằng nhau, bên trái nặng hơn hoặc bên phải nặng hơn. Thông tin thu được trên một phép đo phải$log_2(3)$. $n log_2(3) > 3 + log_2(3) => n > \frac{3}{log_2(3)} + 1 \rightarrow n=3$ là số lần đo tối thiểu.
Tôi không hiểu giải pháp này ở tất cả. tôi hiểu$P(can = error) = 1/12$và $P(can = Lighter | can = error) = 1/12 * 1/2 = 1/24$. Nhưng tôi không theo dõi lý do tại sao có "24 trường hợp." Tôi thấy rằng mỗi lon có$3$trạng thái, nhẹ, nặng hoặc bình thường. Vì vậy, entropy không nên$-(\frac{1}{24} \cdot log_2(\frac{1}{24}) + \frac{1}{24} \cdot log_2(\frac{1}{24}) + \frac{11}{12} \cdot log_2(\frac{11}{12})) = 0.4971502$?
Vấn đề này xuất phát từ cuốn sách: Khai phá dữ liệu thống kê-thông tin (Sy & Gupta).
Biên tập.
Công thức cho entropy: $H(X) = -\sum_1^n p(x) log_2(p(x))$.
Nếu $x$ là trạng thái của lon cà phê, sau đó: $$ \begin{array}{cc} p(x) = \{ & \begin{array}{cc} 1/24 & \text{can is light} \\ 1/24 & \text{can is heavy} \\ 11/12 & \text{can is normal} \end{array} \end{array} $$
Vì thế $$ H(X) = -\sum_1^n p(x) log_2(p(x)) = -1 \cdot (\frac{1}{24} \cdot log_2(\frac{1}{24}) + \frac{1}{24} \cdot log_2(\frac{1}{24}) + \frac{11}{12} \cdot log_2(\frac{11}{12})) = 0.4971502 $$
$12$ lon cà phê có nghĩa là tổng entropy là $12 * 0.497 = 5.965$
Trả lời
Như bạn đã nhắc chính xác, định nghĩa về entropy cho một biến ngẫu nhiên rời rạc ${\displaystyle X}$, kết quả có thể có của ai ${\displaystyle x_{1},...,x_{n}}$ xảy ra với xác suất ${\displaystyle P(x_{1}),..., P(x_{n})}$, Là
$${\displaystyle \mathrm {H} (X)=-\sum _{i=1}^{n}{\mathrm {P} (x_{i})\log {P} (x_{i})}}$$
Có thể thu được các định nghĩa khác nhau về entropy bằng cách thay đổi cơ số của logarit. Một trong những cách phổ biến nhất được sử dụng là trong cơ sở$2$, cho kết quả entropy theo bit hoặc "shannons". Lưu ý rằng thuật ngữ$-\log P(x_i)$ đại diện cho cái gọi là thông tin về bản thân Shannon - một thước đo cố gắng định lượng mức độ "bất ngờ" của một kết quả cụ thể, từ $0$ cho một kết quả xảy ra với xác suất $1$ đến $\infty$ cho một kết quả xảy ra với xác suất $0$. Theo quan điểm này, entropy có thể được hiểu là kỳ vọng về thông tin tự của một biến.
Một vấn đề quan trọng là tổng được sử dụng để xác định entropy phải được tính toán trên tất cả các kết quả có thể xảy ra. Đối với các trường hợp$>1$ các yếu tố được bao gồm (ví dụ: đồng xu, thùng, xúc xắc, v.v.), cần phải xem xét đồng thời tất cả các yếu tố - và không chỉ một hoặc một phần của chúng - để xác định tất cả các kết quả có thể xảy ra.
Trong câu hỏi được OP mô tả, chúng tôi có $12$lon cà phê: tất cả đều chứa cùng một lượng cà phê, trừ một lon có thể chứa nhiều hơn hoặc ít hơn những lon khác. Xem xét đồng thời tất cả các yếu tố của vấn đề - tức là$12$ lon - chúng tôi có $12$các trường hợp có thể xảy ra đối với lon "khác nhau" và đối với mỗi trường hợp này, sự khác biệt có thể là số lượng cà phê lớn hơn hoặc nhỏ hơn. Điều này trực tiếp dẫn đến$24$các trường hợp. Mỗi trường hợp này đều có khả năng xảy ra như nhau, do đó xác suất là$1/24$cho tất cả. Áp dụng công thức chúng tôi nhận được
$$\displaystyle \mathrm {H}=-\sum _{i=1}^{24}\, \frac{1}{24}\, \log_2 \left(\frac{1}{24}\right)= -\log_2 \left(\frac{1}{24}\right)= \log_2 (24)=\log_2 (8)+\log_2 (3)\\ =3+\log_2 (3)$$
Vấn đề trong tính toán của bạn đưa ra $H=0.4971502$là bạn tập trung vào ba khả năng của một lon (bình thường, nhẹ, nặng) thay vì xem xét tất cả các khả năng của cả bộ lon. Như đã nói ở trên, trong loại bài toán này, điều cơ bản là phải xem xét đồng thời tất cả các yếu tố.
Có $24$ các trường hợp bởi vì bạn cũng biết rằng chỉ $1$có thể là không phù hợp; tức là, các trạng thái của lon không độc lập với nhau.
Đầu tiên chúng ta hãy giải quyết trường hợp đơn giản nhất. Giảm vấn đề đặt thành 3 lon. Ghi nhãn các lon là$A, B, C$. Một trong số chúng bị lỗi.
Phép đo số 1: Bạn cân$A$ và $B$. Nếu chúng cân bằng, thì$C$ bị lỗi.
Phép đo # 2: Nếu$A$ và $B$ không cân bằng, loại bỏ $A$ từ số dư và thay thế bằng $C$. Bây giờ nếu họ cân bằng, thì$A$bị lỗi. Nếu không,$B$ bị lỗi.
Yêu cầu số đo tối thiểu = $1$
Số đo tối đa được yêu cầu = $2$
Hãy để chúng tôi thử $4$lon. Ghi nhãn$A, B, C, D$.
Phép đo # 1 : Cân$A, B$.
Nếu $A,B$ được cân bằng, sau đó loại bỏ $A$ và thay thế bằng $C$.
Phép đo # 2.a Nếu$B, C$ được cân bằng, D bị lỗi khác $C$ bị lỗi.
Nếu $A, B$ không cân bằng, sau đó loại bỏ $A$ và thay thế bằng $C$.
Phép đo # 2.b Nếu chúng cân bằng,$A$ bị lỗi khác $B$ bị lỗi
Các phép đo tối thiểu cần thiết: $2$
Các phép đo tối đa được yêu cầu: $2$
Đầu tiên chúng tôi làm một $3$-đo lường khe tương tự như $3$-có thể đo ở trên. Mỗi lô có$4$lon. Trường hợp tốt nhất của chúng tôi sẽ xác định rất nhiều lỗi$4$ lon trong $1$ đo lường, trường hợp xấu nhất $2$ đo.
Sau đó chúng tôi làm một $4$-có thể đo lường với lô bị lỗi và xác định lỗi trong $2$ đo.
Vì vậy, các phép đo tối thiểu là $1 + 2 = 3$.
Các phép đo tối đa là $2 + 2 = 4$.
Bây giờ chuyển nó thành entropy.
Lưu ý: Mỗi phép đo tiết lộ nhiều hơn một bit thông tin (về hai bài báo đang được đo và những bài khác không được đo).