第2講預(yù)備知識(shí)

1、第2講 預(yù)備知識(shí)1. 序列令X為非空集合，任何函數(shù)f :0,1,¼,n-1X稱為X中有窮序列，其長(zhǎng)度記為為len(f)=n。特別地，從空集到X的映射稱為空序列，其長(zhǎng)度為0。空序列也屬于有窮序列。任何映射稱為X中無(wú)窮序列，其長(zhǎng)度為len(f)=。令f為序列，對(duì)于任何稱為該序列的第i項(xiàng)。2. 字符串令為字符表，上的序列稱為串（string）。有窮串的集合記為*，無(wú)窮串的集合記為。長(zhǎng)度為0的串稱為空串（empty string），記為或者l。 例如，0,1*表示所有二元串的集合，該集合含空串。記號(hào)：十進(jìn)制字符表記為 0-9，拉丁字母表記為a-z, A-Z,a-zA-Z提問：0-9a-zA-

2、Z表示什么？0-9*又表示什么？串的長(zhǎng)度單位：若中有n個(gè)字符，則每個(gè)字符稱為n-元字符。n-元字符組成的串稱為n-元串。n-元串的長(zhǎng)度單位為“字符”，更具體地，稱為“n-元字符”、“n-進(jìn)制單位”。我們規(guī)定如下的單位換算關(guān)系：其中對(duì)數(shù)底默認(rèn)為2。注：以后log的底都默認(rèn)為2。提問：每個(gè)二元字符的單位為1比特（bit），那么bit這個(gè)名稱有什么來歷？提問：表示一個(gè)十進(jìn)制符號(hào)，至少需要多少二進(jìn)制符號(hào)？下面我們考慮符號(hào)串的二元表示。將任意的n-元串表示二元串，則所得的二元串的長(zhǎng)度至少為這個(gè)量稱為n-元串x的比特?cái)?shù)，記為bit(x).字符串的比特?cái)?shù)是其二元表示長(zhǎng)度的下界。串的連接運(yùn)算：連接（conca

3、tenation）是字符串的二元運(yùn)算。兩個(gè)串x,y的連接結(jié)果為xy?？沾c任何字符串x的左連接或者右連接都等于x，即x=x=x子串、前綴、后綴：前綴集（prefix-free set）：若一個(gè)字符串集合中任何兩個(gè)串互相不是對(duì)方的前綴，則該集合稱為前綴集。3. 隨機(jī)變量隨機(jī)變量是定義在樣本空間上的因變量，我們用它表示樣本點(diǎn)的某種數(shù)值屬性。例如，一個(gè)地區(qū)的所有人構(gòu)成一個(gè)樣本空間，其中每個(gè)人是一個(gè)可能被抽樣調(diào)查到的樣本點(diǎn)。假設(shè)這次調(diào)查所希望獲得的是每個(gè)人的年齡、身高和體重。這些都是每個(gè)人的數(shù)值屬性，是樣本空間上的3個(gè)不同的隨機(jī)變量。假如我們還需要統(tǒng)計(jì)每個(gè)人的文化程度。文化程度初略地可劃分為文盲、小學(xué)

4、畢業(yè)、中學(xué)畢業(yè)、大學(xué)畢業(yè)、碩士、博士等等級(jí)別。這是對(duì)文化程度的定性表示。為了便于數(shù)據(jù)處理和計(jì)算，我們可以對(duì)文化程度進(jìn)行定量表示，也就是將這些離散的級(jí)別表示為數(shù)值。這種樣本點(diǎn)屬性的數(shù)值表示也是隨機(jī)變量。因此，對(duì)于一次隨機(jī)試驗(yàn)來說，隨機(jī)變量有兩個(gè)作用：（1） 表示樣本點(diǎn)的數(shù)值屬性。（2） 對(duì)樣本點(diǎn)的非數(shù)值屬性進(jìn)行量化，從而轉(zhuǎn)化為數(shù)值屬性。為了便于使用，理論上規(guī)定隨機(jī)變量必須滿足如下條件： 實(shí)數(shù)區(qū)間的原像必須是隨機(jī)事件。這便于計(jì)算等事件的概率。定義 令為樣本空間，X是上的實(shí)值函數(shù)，若對(duì)于任何實(shí)數(shù)a，總是中的事件，則稱X為上的隨機(jī)變量。我們知道，離散樣本空間的每個(gè)子集都是事件，所以對(duì)于該樣本空間上的任

5、何數(shù)值函數(shù)X和任何數(shù)值a，總是事件。因此，樣本空間上的任何數(shù)值函數(shù)都是隨機(jī)變量。若X的值域是有窮的或者可列的，則稱X為離散的，否則稱為非離散的。下列概念刻畫了隨機(jī)變量的統(tǒng)計(jì)特征：定義 對(duì)于任何隨機(jī)變量X，若X是離散的，則表示X取值x的概率。我們記則p是從X的值域到單位區(qū)間0,1上的函數(shù)，稱為X的概率分布。概率分布完全給出了離散隨機(jī)變量的所有統(tǒng)計(jì)特性。然而，上述定義對(duì)非離散的隨機(jī)變量并不成立。事實(shí)上，若X的值域是一個(gè)區(qū)間，則簡(jiǎn)單事件X=x的概率通常為0. 下列概念對(duì)于任何隨機(jī)變量都是適用的，可以描述任何隨機(jī)變量的統(tǒng)計(jì)特性。定義 隨機(jī)變量X的分布函數(shù)定義為，對(duì)于任何實(shí)數(shù)x，定義 令X為隨機(jī)變量，其

6、分布函數(shù)為F。若存在實(shí)函使得則稱f為X的概率密度函數(shù)，簡(jiǎn)稱概率密度。存在概率密度的隨機(jī)變量稱為連續(xù)型隨機(jī)變量。注：概率密度函數(shù)一般用符號(hào)f表示，這也許源于“頻率”的英文單詞frequency。注意，離散的隨機(jī)變量也有概率密度函數(shù)。思考：離散隨機(jī)變量的概率密度f(wàn)與概率分布p有聯(lián)系嗎？4. 對(duì)數(shù)不等式有幾個(gè)來自數(shù)學(xué)分析和概率論的不等式，在信息論中經(jīng)常用到。這一講我們集中學(xué)習(xí)它們，為后面繼續(xù)學(xué)習(xí)信息論作準(zhǔn)備。定理4.1（對(duì)數(shù)不等式一）對(duì)于任何x>0，有 其中等號(hào)成立當(dāng)且僅當(dāng)x=1.畫圖：構(gòu)造直觀印象。畫出1-1/x和x-1的圖像，再在兩者之間畫出lnx的圖像。證明：令f(x)=lnx-x+1.

7、 我們有當(dāng)0<x<1時(shí)，導(dǎo)數(shù)f(x)>0，函數(shù)f是嚴(yán)格單調(diào)遞增的。當(dāng)x>1時(shí)，導(dǎo)數(shù)f(x)<0，函數(shù)f是嚴(yán)格單調(diào)遞減的。因此，f在x=1處的值最大，從而f(x)0，即根據(jù)嚴(yán)格單調(diào)性，等號(hào)成立當(dāng)且僅當(dāng)x=1.用代替上述不等式中的x， 可得證畢證明二：對(duì)于任何x，當(dāng)x>-1時(shí)，我們有用x代替1+x可得，當(dāng)x0時(shí)，我們有 其中等號(hào)成立當(dāng)且僅當(dāng)x=1。 證畢證明三：用微分中值定理。證明四：用積分中值定理。對(duì)數(shù)不等式存在有如下的變形。 推論4.2（對(duì)數(shù)不等式二）對(duì)于任何x>0，有 其中等號(hào)成立當(dāng)且僅當(dāng)x=1. 證明：？ 概率分布中有些概率是0，在信息論的計(jì)算中，

8、為了使我們的運(yùn)算和討論適用于0概率，我們將對(duì)數(shù)運(yùn)算進(jìn)行如下延拓。對(duì)數(shù)的延拓：根據(jù)連續(xù)性，可將對(duì)數(shù)的定義延拓到0和上。我們規(guī)定 log0=， 0log0=0而對(duì)于任何非負(fù)數(shù)x，我們規(guī)定 推論4.3（對(duì)數(shù)不等式三）對(duì)于任何x, y0，有 其中等號(hào)成立當(dāng)且僅當(dāng)x=1.證明：？5. 信息不等式與對(duì)數(shù)和不等式 定理5.1（信息不等式）對(duì)任何概率分布p=(p1, p2, , pn)和q=(q1,q2, , qn)，都有 其中等號(hào)成立，當(dāng)且僅當(dāng) p=q. 證明： 應(yīng)用對(duì)數(shù)不等式進(jìn)行證明。細(xì)節(jié)留作練習(xí)。 證畢定理5.2（對(duì)數(shù)和不等式） 對(duì)于任何兩組非負(fù)數(shù)和，其中等號(hào)成立當(dāng)且僅當(dāng)?shù)扔诔?shù)（常數(shù)包括無(wú)窮大）。注意

9、：對(duì)數(shù)和不等式遵守對(duì)數(shù)運(yùn)算的延拓規(guī)定。證明：令 應(yīng)用對(duì)數(shù)不等式可得其中等號(hào)成立當(dāng)且僅當(dāng)對(duì)（1）兩邊同乘以ai并分別累加，可得對(duì)數(shù)和不等式。 證畢思考：信息不等式與對(duì)數(shù)和不等式是相互等價(jià)的，可相互推出。應(yīng)用對(duì)數(shù)和不等式可以證明許多凸性結(jié)果，包括信息不等式。6. 函數(shù)的凸性凸集：設(shè)S是向量空間的一個(gè)子集。若對(duì)于S中任何兩個(gè)不相同的點(diǎn)以及任何參數(shù)，總有，則稱S為凸集（convex set）。注意，令，其中，則點(diǎn)x位于之間，并且所有這些點(diǎn)x構(gòu)成一條線段。隨著參數(shù)從0遞增到1，x從初始值x2開始逐漸變?yōu)閤1。對(duì)于凸集來說，這個(gè)線段是完全位于該凸集中的。定義6.1 令f為凸集S上的連續(xù)函數(shù)，且對(duì)于S中任何

10、兩個(gè)不同的點(diǎn)，總有 則稱f為上凸的（也稱凹的，concave）。若其中=不成立，則稱f為嚴(yán)格上凸的（也稱嚴(yán)格凹的，strictly concave）。將上述不等式中的改為和<，則分別稱f為下凸的（也稱為凸的，convex）和嚴(yán)格下凸的。上凸函數(shù)的直觀特征：函數(shù)位于弦之上在上凸函數(shù)的圖像中，任意兩點(diǎn)間的函數(shù)圖像總位于以這兩點(diǎn)為端點(diǎn)的弦之上。Bf(x1)f(x)Ax x2x1f(x2)其中，從而 定理6.2 設(shè)函數(shù)f(x)在某區(qū)間上有二階導(dǎo)函數(shù)f”(x)。若f”(x)總是小于0，則f是嚴(yán)格上凸的。若f”(x)總是大于0，則f是嚴(yán)格下凸的。證明：高數(shù)和數(shù)學(xué)分析等教材中一般都有證明。有的用拉格朗

11、日微分中值定理，有的用泰勒展開式。下面給出應(yīng)用微分中值定理的一種證明。讀者可嘗試其它證明方法。根據(jù)微分中值定理，存在，和，使得 若二階導(dǎo)總小于0，則 從而 若二階導(dǎo)總大于0，則 從而 證畢練習(xí)：1. 證明logx是嚴(yán)格上凸的。 2. 證明xlogx是嚴(yán)格下凸的。 7. 延森不等式 我們對(duì)上凸函數(shù)定義中的不等式進(jìn)行推廣，得如下Jessen不等式定理。定理7.1 （有限Jessen不等式） 若實(shí)函數(shù)f是上凸的，則對(duì)于定義域中任何n個(gè)點(diǎn)和任何概率分布p=(p1, p2, , pn)，總有 若實(shí)函數(shù)f是嚴(yán)格上凸的，則上述不等式中等號(hào)成立的充要條件是或者p為退化分布。證明：根據(jù)上凸函數(shù)的定義，應(yīng)用數(shù)學(xué)歸

12、納法可證明該不等式。方法是將右式中的n個(gè)點(diǎn)湊成n-1個(gè)點(diǎn)，可以應(yīng)用歸納假設(shè)。細(xì)節(jié)略。 證畢定理7.2（一般Jessen不等式）設(shè)f是某區(qū)間上的上凸函數(shù)，X是一個(gè)所有取值位于該區(qū)間中的隨機(jī)變量，則若f是嚴(yán)格上凸的，則Jensen不等式中等號(hào)成立的充要條件是X的概率分布為退化分布，即X的取值是唯一的。注意，其中X可以是任何離散型隨機(jī)變量或者連續(xù)型隨機(jī)變量。證明：令X是離散型隨機(jī)變量。若X的值是有限多的，則由定理7.1立刻得定理7.2的結(jié)論。若X的取值是無(wú)限的，可以將以無(wú)限取值情形構(gòu)造為n個(gè)取值的情形。從而定理7.1中的不等式成立，隨著n增大，這個(gè)不等式的左右兩邊形成兩個(gè)序列，對(duì)這兩個(gè)序列分別求極限

13、，就可得定理7.2的結(jié)論。證明細(xì)節(jié)請(qǐng)讀者完成。令X為連續(xù)型隨機(jī)變量。定理7.2中的不等式兩邊的期望是函數(shù)的積分，即黎曼和的極限。對(duì)其中的黎曼和應(yīng)用延森不等式，再求極限，即可得定理7.2的結(jié)論。證明細(xì)節(jié)請(qǐng)讀者完成。 證畢思考：延森不等式比信息不等式與對(duì)數(shù)和不等式更強(qiáng)大。1. 用延森不等式證明信息不等式。2. 用延森不等式證明對(duì)數(shù)和不等式。作業(yè)1. 分別用微分中值定理和積分中值定理證明對(duì)數(shù)不等式。2. 用數(shù)學(xué)歸納法證明定理7.1中的延森不等式。3. 用Jessen不等式證明對(duì)數(shù)和不等式。附錄：事件與概率的形式定義隨機(jī)事件這個(gè)概念用以表示關(guān)于樣本點(diǎn)的命題，例如樣本點(diǎn)的某個(gè)數(shù)值屬性X小于a。隨機(jī)事件用樣本空間的子集表示，例如，即隨機(jī)事件都是可以確定其發(fā)生概率的。事件A的概率記為P(A)，事件的概率記為或者P(X<a). 嚴(yán)格的定義如下：定義 （事件域與事件）令為樣本空間，F(xiàn)為的一些子集構(gòu)成的集合。若F滿足下列條件，則稱F為上的事件域（event field），其中的元素稱為上的事件（event）或者隨機(jī)事件（random event）：（1）F含樣本空間。（2）F對(duì)于差是封閉的。（3）F對(duì)于可列并是封閉的。定義（