الحدود المثلثة
توزيع الاحتمال على q الرموز هو نقطة في (q−1)-بعد الحدود المثلثة: مجموعة جميع الفواصل (p₁, ..., p_q) مع pᵢ ≥ 0 و Σ pᵢ = 1.
عند q = 2: الحدود المثلثة هي قطعة من خط المستقيم [0,1]، محددة بمصفوفة الاحتمال الواحدة p. عند q = 3: الحدود المثلثة هي ثلاثي الأضلاع المستقيم في ℝ². كل زاوية هي توزيع محدد (كل الاحتمال على رمز واحد)؛ النقطة الوسطى هي التوزيع المتساوي.
التروية H(p) تعطى رقم حقيقي لكل نقطة من الحدود المثلثة. الجبرية المكانية للوظيفة تحدد العديد من النتائج الأساسية.
الانحناء
H هي منحنية على الحدود المثلثة: لكل توزيعين p و q و أي λ ∈ [0,1]:
H(λp + (1−λ)q) ≥ λH(p) + (1−λ)H(q)
خلطة من توزيعين اثنين لديها تروية على الأقل كبيرة مثل المتوسط الموزون لترويح فردية. الفكرة: خلط مصادرين يزيد من عدم التأكد.
تأكيد الانحناء
لنظرية التروية البنفسجية H(p)، يكون الانحناء مرئيًا في الرسم: تتدحرج الكurve لأعلى، لا تتجاوز أي خطوط مرور بين نقطتين.
اختبار رسمي للانحناء: المشتقة الثانية H''(p) ≤ 0 في كل مكان.
H(p) = −p log₂(p) − (1−p) log₂(1−p)
H'(p) = −log₂(p) − 1/ln(2) + log₂(1−p) + 1/ln(2) = log₂((1−p)/p)
H''(p) = −1/(p ln(2)) − 1/((1−p) ln(2)) = −1/(p(1−p) ln(2)) < 0 for all p ∈ (0,1)
المشتقة الثانية صارمة سلبية في كل مكان في الداخل: H هي صارمة منحنية.
التوزيع المحدد للقدرة
القدرة القنوية هي أكبر من المعلومات المشتركة على جميع توزيعات المدخلة p(x):
C = max_{p(x)} I(X; Y)
حيث I(X; Y) = H(Y) − H(Y|X) = H(X) − H(X|Y) = H(X) + H(Y) − H(X,Y).
للقناة البيسيمترية البيزية مع معدل الخطأ Q: التوزيع المحدد للمدخلة هو التوزيع المنتظم p(0) = p(1) = 0.5.
لماذا: H(Y) يصل إلى أقصى حد عند التوزيع المنتظم للخروج. مع BSC، التوزيع المنتظم للدخول ينتج توزيعًا منتظمًا للخروج. أي توزيع آخر يقلل من H(Y) وبالتالي يقلل من I(X;Y).
جبريا: المعلومات المشتركة I(X;Y) هي دالة concave للوظيفتين p(x) على المثلث. أقصى حد ل دالة concave على مجموعة متماثلة (مثل القناة الصفراء) هو حاصل عند نقطة فريدة (المركز، بالنسبة لقناة متماثلة).
فرق كولباك-ليبيل للانحراف
الفرق كولباك-ليبيل للانحراف (الانحراف النسبي) من توزيع q إلى توزيع p:
D(p || q) = Σᵢ pᵢ log₂(pᵢ/qᵢ)
D(p || q) ≥ 0 دائمًا (نظرية جيبز). D(p || q) = 0 إذا و فقط إذا كان p = q.
D هو لا هو مسافة حقيقية: هو غير محايد (D(p||q) ≠ D(q||p) بشكل عام) ولا يلتزم بعدالة قانون المثلث. لكنه يعمل كقياس لمدى بعيد p عن q في فضاء الاحتمالات.
فرق كولباك-ليبيل للانحراف يظهر في كل مكان في نظرية المعلومات:
- المعلومات المتبادلة: I(X;Y) = D(p(x,y) || p(x)p(y)). المعلومات المتبادلة هي فرق كولباك-ليبيل للانحراف بين التوزيع المشترك والتكرار المزدوج للمحددات - مدى بعيد التوزيع المشترك عن الاستقلالية.
- نظرية جيبز: يتبع theorem theorem من D(p || q) ≥ 0.
- القدرة على التعامل: C = max_{p(x)} I(X;Y) = max_{p(x)} D(p(x,y) || p(x)p(y)).
حساب فرق كولباك-ليبيل للانحراف
مثال: p = (0.5, 0.5) ثنائي متساوي القيم، q = (0.8, 0.2) ثنائي متماثل.
D(p || q) = 0.5 log₂(0.5/0.8) + 0.5 log₂(0.5/0.2)
= 0.5 log₂(0.625) + 0.5 log₂(2.5)
≈ 0.5 × (−0.678) + 0.5 × 1.322 ≈ −0.339 + 0.661 ≈ 0.322 بت
Channel Capacity as Geometric Distance
تملك طاقات القناة تفسيرا جيو متريا في مساحة التوزيعات الاحتمالية.
لقناة p(y|x)، تحدد التوزيع الاحتمالي الأفضل p*(x). تفي الطاقة بما يلي:
C = D(p*(y) || r(y))
حيث p(y) = Σ p(x) p(y|x) هو التوزيع الخروجي تحت المدخلات المثلى، و r(y) = argmin_r max_x D(p(y|x) || r(y)) هو التوزيع الخروجي الأقل معلوماتي — النقطة في مساحة التوزيعات الخروجية الأقرب (في انحناءة KL) لجميع التوزيعات الخروجية المشتركة p(y|x=0) و p(y|x=1).
هذا هو التفسير الجيو متري: طاقة القناة هي نصف كرة انحناءة KL في مساحة التوزيعات الخروجية تحتوي جميع التوزيعات الخروجية المشتركة p(y|x=0) و p(y|x=1).
في BSC: p(y|x=0) = (1−Q، Q) و p(y|x=1) = (Q، 1−Q). بسبب التناظر، يكون التوزيع الأقل معلوماتي r(y) = (0.5، 0.5). الطاقة = D((1−Q، Q) || (0.5، 0.5)) = 1 − H(Q). تسترد الصيغة الناتج قياسي من الجيومتрія.
Capacity from KL Divergence
تأكيد الصيغة الجيو: C = D(p(y|x=0) || r(y)) لقناة BSC مع Q = 0.1، r(y) = (0.5، 0.5).
p(y|x=0) = (0.9، 0.1) (إرسال 0، استقبال 0 مع احتمال 0.9، استقبال 1 مع احتمال 0.1).
D((0.9، 0.1) || (0.5، 0.5)) = 0.9 لوغ₂(0.9/0.5) + 0.1 لوغ₂(0.1/0.5)
= 0.9 لوغ₂(1.8) + 0.1 لوغ₂(0.2)
لوغ₂(1.8) ≈ 0.848، لوغ₂(0.2) ≈ −2.322
= 0.9×0.848 + 0.1×(−2.322) ≈ 0.763 − 0.232 ≈ 0.531 بتس
تحقق: C = 1 − H(0.1) ≈ 1 − 0.469 = 0.531 بتس ✓
Rate-Distortion & the Limits of Compression
Rate-distortion theory extends information theory to lossy compression. Instead of asking 'what is the minimum bits to represent a source exactly?' it asks: 'given tolerance for some average distortion D, what is the minimum rate R(D) bits per symbol?'
The rate-distortion function R(D) is convex and decreasing in D: more distortion tolerance allows lower rates. At D = 0 (lossless): R(0) = H(source). As D increases, R(D) → 0.
Geometrically: R(D) traces a curve on the (rate, distortion) plane. Every achievable (R, D) pair lies on or above this curve. Points below the curve are impossible — you cannot compress below the fundamental limit at any distortion level.
The rate-distortion theorem (Shannon, 1959): for any R > R(D), codes exist achieving expected distortion at most D. For R < R(D): no code achieves expected distortion D. The curve is a geometric frontier in (rate, distortion) space.