講座報告概率方法

概率方法王學欽博士E-mail:數(shù)學與計算科學學院中山醫(yī)學院幾個例子Ramsey數(shù)；Buffon投針；素因子的個數(shù)一些符號Landan漸進符號；概率符號概率在數(shù)論中的應用Ramsey數(shù)；Sum-free集合問題Buffon投針問題的解（幾何方法）期望的線性性質(zhì)Buffon投針（概率方法）；不平衡的燈Chebyshev不等式素因子的個數(shù)；不同和問題Ramsey數(shù)R(k,l)(1)用a,b,c,d,e,f六點表示六個人。如果兩人互相認識，就在相應頂點間連一條紅邊，如果互相不認識，就連上一條藍邊。這樣原問題就相當于對于任意的雙色完全圖K6中必存在一個單色三角形。abcdefR(3,3):

證明，任意六個人中，總有三個人互相認識，

或者互相不認識。-----1947年匈牙利數(shù)學競賽Ramsey數(shù)R(k,k)不失一般性,考慮以a端點的5條邊。因為只有兩種顏色，所以，至少有3邊同色。不妨設ab，ac，ad同為藍色。abcdefabcdefR(3,3):

證明，任意六個人中，總有三個人互相認識，

或者互相不認識。-----1947年匈牙利數(shù)學競賽Ramsey數(shù)R(k,l)(1)R(3,3):

證明，任意六個人中，總有三個人互相認識，

或者互相不認識。-----1947年匈牙利數(shù)學競賽Ramsey數(shù)R(k,k)在b，c，d三者間，若有任意一條為藍色，例如bd為藍色，則abd構成藍色三角形。abcdef在b，c，d三者間，若沒有一條為藍色，則他們之間均是紅色連線，此時bcd就會構成紅色三角形。abcdefRamsey數(shù)R(k,l)(1)Ramsey數(shù)R(k,l)(2)

給定兩個自然數(shù)k和l,是否存在n，使得任意一個雙色完全圖Kn，要么含有紅色的完全子圖Kk，要么含有藍色的完全子圖Kl？而稱具有這樣性質(zhì)的最小自然數(shù)n為Ramsey數(shù)，記作R(k,l)。我們關心的是R(k,l)的值或者上下界。在這里，我們只簡單討論Ramsey數(shù)R(k,k)的下界。(k,l)=(3,3),Ramsey數(shù)R(3,3)=6。這是因為：K5中可以不出現(xiàn)單色三角形。假設在平面上畫上間距為d的平行線，現(xiàn)在隨?機投擲?長度為L的的針，求針與其中至少?一條平行線相交的概率。當L≤d時，所求的概率是2L/πd。Buffon投針素因子的個數(shù)1920年，Hardy和Ramanujan證明了“幾乎所有”n的素因子的個數(shù)“非?？拷?/p>

。素因子的個數(shù)1920年，Hardy和Ramanujan證明了“幾乎所有”n的素因子的個數(shù)“非?？拷?/p>

。嚴格的數(shù)學表述如下：令為所有n的素因子的個數(shù)和讓任意緩慢的趨向無窮大。那么幾個例子Ramsey數(shù)；Buffon投針；素因子的個數(shù)一些符號Landan漸進符號；概率符號概率在數(shù)論中的應用Ramsey數(shù)；Sum-free集合問題Buffon投針問題的解（幾何方法）期望的線性性質(zhì)Buffon投針（概率方法）；不平衡的燈Chebyshev不等式素因子的個數(shù)；不同和問題Landan漸進符號令n為一個正變量，f(n)與g(n)為n的實函數(shù)。

表示f是非負的，并且對于所有的n，存在常數(shù)C，使得|g(n)|≤C·f(n)

表示f是非負的，并且當n趨于無窮時，g(n)/f(n)趨向于0

表示f(n)=o(g(n))

表示f(n)=(1+o(1))·g(n)概率符號假設E為某個概率空間（有限）的一個事件：P(A)表示事件A發(fā)生的概率。I(A)表示事件A的示性函數(shù)，如果A發(fā)生則I(A)=1，若不發(fā)生則為0。假設X是一個離散的隨機變量：E(X)=∑x[x·P(X=x)]，定義為其期望。Var(X)=E(X-EX)2=EX2-(EX)2，定義為其方差。而后有E(I(A))=P(A)，Var(I(A))=P(A)-P(A)2。幾個例子Ramsey數(shù)；Buffon投針；素因子的個數(shù)一些符號Landan漸進符號；概率符號概率在數(shù)論中的應用Ramsey數(shù)；Sum-free集合問題Buffon投針問題的解（幾何方法）期望的線性性質(zhì)Buffon投針（概率方法）；不平衡的燈Chebyshev不等式素因子的個數(shù)；不同和問題定理1：如果，那么。

這樣，對所有的，有：Ramsey數(shù).R(k,k)的下確界定理1：如果，那么。

這樣，對所有的，有：證明：在一個雙色完全圖中，考慮由兩種顏色（紅或藍）等可能的對邊著色。對于任一個具有

個頂點的集合

，令

為“由

誘導的

的子圖為單色的事件”。那么，Ramsey數(shù).R(k,k)的下確界定理1：如果，那么。

這樣，對所有的，有：證明：在一個雙色完全圖中，考慮由兩種顏色（紅或藍）等可能的對邊著色。對于任一個具有

個頂點的集合

，令

為“由

誘導的

的子圖為單色的事件”。那么，又因為在中這樣的

有

個，所以至少有一個事件發(fā)生的概率最多為。這樣，沒有一個事件會發(fā)生的概率為正，也就是說，存在一個不含有單色的雙色完全圖

。于是有。Ramsey數(shù).R(k,k)的下確界定理1：如果，那么。

這樣，對所有的，有：定理1：如果，那么。

這樣，對所有的，有：注意到

時，取

，滿足

因此，。證畢定理1：如果，那么。

這樣，對所有的，有：注意到

時，取

，滿足

因此，。證畢這個例子體現(xiàn)了概率方法的精髓。我們并沒有直接通過構造性或確定性的方法來證明單色子圖的存在，而是以一種非確定性的方法來處理問題。注：Erd?s（埃爾德什）是第一個理解這種方法并成功的運用以解決了許多應用問題的人。Sum-free集合問題定義：一個可換群G的子集

被稱為sum-free（和自由）的，

當且僅當其不存在三個元素x，y，z，使得x+y=z。

換言之，。定理[Erd?s1965]：每一個由n個非零整數(shù)所組成的集合

，存在一個sum-free的子集，并且子集的大?。A）比的三分之一要大：。Sum-free集合問題定義：一個可換群G的子集

被稱為sum-free（和自由）的，

當且僅當其不存在三個元素x，y，z，使得x+y=z。

換言之，。定理[Erd?s1965]：每一個由n個非零整數(shù)所組成的集合

，存在一個sum-free的子集，并且子集的大小（階）比的三分之一要大：。證明：令

為一個素數(shù)，使得，同時令則

顯然是循環(huán)群的一個sum-free子集，而且，根據(jù)

上的均勻分布選取一個正整數(shù)，定義對于每個固定的

，當

遍歷所有1至p-1的整數(shù)時，也遍歷所有中的非零元素。這樣。因此，使得

屬于

的個數(shù)的期望

。Sum-free集合問題由此可知，存在一個和

的一個子集

（

的階

），使得：對所有的，。這樣顯然是sum-free的，這因為如果有，并滿足，那么，必有但這與是的sum-free子集這一事實所矛盾。故完成證明。Sum-free集合問題對于每個固定的

，當

遍歷所有1至p-1的整數(shù)時，也遍歷所有中的非零元素。這樣。因此，使得

屬于

的個數(shù)的期望

。幾個例子Ramsey數(shù)；Buffon投針；素因子的個數(shù)一些符號Landan漸進符號；概率符號概率在數(shù)論中的應用Ramsey數(shù)；Sum-free集合問題Buffon投針問題的解（幾何方法）期望的線性性質(zhì)Buffon投針（概率方法）；不平衡的燈Chebyshev不等式素因子的個數(shù)；不同和問題南端線=參照線qyLMeasuretotheclosestlinenorthofthemeasuringendDdBuffon投針的計算（幾何方法）由于針的長度小于線的間距，所以必有一條平行線與針相鄰但不相交。我們將這個線作為參照線（南端的線）。如果，則表示出現(xiàn)了相交。關系式獨立均勻分布獨立均勻分布現(xiàn)在我們有：左圖是

與的聯(lián)合分布圖，其中紅色區(qū)域表示，即能夠相交，而白色區(qū)域則表示沒有相交。最后只需要計算出紅色區(qū)域所占整體區(qū)域的比例即可。Buffon投針的計算（幾何方法）左圖是

與的聯(lián)合分布圖，其中紅色區(qū)域表示，即能夠相交，而白色區(qū)域則表示沒有相交。最后只需要計算出紅色區(qū)域所占整體區(qū)域的比例即可。Buffon投針的計算（幾何方法）幾個例子Ramsey數(shù)；Buffon投針；素因子的個數(shù)一些符號Landan漸進符號；概率符號概率在數(shù)論中的應用Ramsey數(shù)；Sum-free集合問題Buffon投針問題的解（幾何方法）期望的線性性質(zhì)Buffon投針（概率方法）；不平衡的燈Chebyshev不等式素因子的個數(shù)；不同和問題期望的線性性質(zhì)令為隨機變量，。那么這個期望的線性性質(zhì)的威力在于其并沒有受到之間是否獨立的限制。在應用中，經(jīng)常使用這樣的事實：在樣本空間中比存在一個點使得：

或在下面的例子中可以看到這個方法的使用。Buffon投針的計算（概率方法）現(xiàn)在我們用另一種思維來看待Buffon投針的問題。平行線的間距已經(jīng)給定。對于一個長度是

的針，定義一個隨機變量，其為此針與平行線相交的點數(shù)。由于

，所以

以概率

取值0，以概率

取值1。

既是我們需要求的值，這也同時是的期望：Buffon投針的計算（概率方法）現(xiàn)在我們用另一種思維來看待Buffon投針的問題。平行線的間距已經(jīng)給定。對于一個長度是

的針，定義一個隨機變量，其為此針與平行線相交的點數(shù)。由于

，所以

以概率

取值0，以概率

取值1。

既是我們需要求的值，這也同時是的期望：接下來我們再找一根針，長度為，將其與先前的那根針頭尾連接起來，并保持活動不固定死。類似的依然可以定義一個隨機變量。雖然與不獨立，但是它們的期望依然滿足線性性質(zhì)：Buffon投針的計算（概率方法）由于上述期望的線性性質(zhì)，兩根針無論構成什么樣子的鏈接方式，其與平行線的交點個數(shù)的期望是不變的。而多根針頭尾連在一起依然保持了這樣的性質(zhì)。同時多根針可以組成任意的形狀。另一方面，容易看出是與有關系的，而在針長度的合理范圍內(nèi)，它們成線性關系：因此接下來我們所要做的事情就是確定的大小。Buffon投針的計算（概率方法）由于上述期望的線性性質(zhì)，兩根針無論構成什么樣子的鏈接方式，其與平行線的交點個數(shù)的期望是不變的。而多根針頭尾連在一起依然保持了這樣的性質(zhì)。同時多根針可以組成任意的形狀。另一方面，容易看出是與有關系的，而在針長度的合理范圍內(nèi)，它們成線性關系：因此接下來我們所要做的事情就是確定的大小。之后我們考慮形狀固定的鐵絲，其長度為，定義為鐵絲與平行線相交的交點個數(shù)?？梢詫⑦@個鐵絲近似想象成很多針所連接起來的，所以將會近似等于，而取其極限，我們得到：Buffon投針的計算（概率方法）最后，為了求解出的大小，我們只需要選取適當形狀的鐵絲來進行求解。令鐵絲為一個圓圈，其直徑為。顯然我們有：代入到公式中，，解得Buffon投針的計算（概率方法）最后，為了求解出的大小，我們只需要選取適當形狀的鐵絲來進行求解。令鐵絲為一個圓圈，其直徑為。顯然我們有：代入到公式中，，解得所以，對于一個針而言，我們有證畢不平衡的燈我們先來看一個定理。定理：令，，則存在，使得不平衡的燈我們先來看一個定理。定理：令，，則存在，使得現(xiàn)在我們針對此定理給出一個現(xiàn)實生活中的解釋：假若按照

的矩陣形式來擺放燈泡，每一個燈泡要么是亮著的（），要么是熄滅的（）。同時存在著控制同一排或者同一列的轉換開關（

既是控制第

排的，而

則是控制第

列的）。不平衡的燈我們先來看一個定理。定理：令，，則存在，使得現(xiàn)在我們針對此定理給出一個現(xiàn)實生活中的解釋：假若按照

的矩陣形式來擺放燈泡，每一個燈泡要么是亮著的（），要么是熄滅的（）。同時存在著控制同一排或者同一列的轉換開關（

既是控制第

排的，而

則是控制第

列的）。而上述定理的意思是，對于燈泡任意的初始設置，我們都有可能通過調(diào)整開關而使得（開著的燈個數(shù)）—（關著的燈個數(shù)）至少為：證明：首先忽略行開關。獨立并均勻的讓，并設：對給定的，無論初始值如何，

將會均勻的等于+1或者-1，并且在不同的之間他們相互獨立。這里既是說，無論第行燈泡的初始值如何，在隨機選擇列開關后，他們的開關狀態(tài)都將服從均勻分布，并一共有的等可能選擇。證明：首先忽略行開關。獨立并均勻的讓，并設：對給定的，無論初始值如何，

將會均勻的等于+1或者-1，并且在不同的之間他們相互獨立。這里既是說，無論第行燈泡的初始值如何，在隨機選擇列開關后，他們的開關狀態(tài)都將服從均勻分布，并一共有的等可能選擇。故

服從分布（

個獨立均勻分布{-1，1}下的隨機變量的和分布）。所以，證明：首先忽略行開關。獨立并均勻的讓，并設：對給定的，無論初始值如何，

將會均勻的等于+1或者-1，并且在不同的之間他們相互獨立。這里既是說，無論第行燈泡的初始值如何，在隨機選擇列開關后，他們的開關狀態(tài)都將服從均勻分布，并一共有的等可能選擇。故

服從分布（

個獨立均勻分布{-1，1}下的隨機變量的和分布）。所以，注：在隨機游走中，一個人每次等可能的向前或者向后走一步，在走了n步后，計算他離遠點的距離，上述結果就是此距離的均值。再利用期望的線性性質(zhì)，由此可以看出，肯定存在一組，使得

至少是上述的取值，然后我們只需要通過選取

與

的符號相同，就有：證畢幾個例子Ramsey數(shù)；Buffon投針；素因子的個數(shù)一些符號Landan漸進符號；概率符號概率在數(shù)論中的應用Ramsey數(shù)；Sum-free集合問題Buffon投針問題的解（幾何方法）期望的線性性質(zhì)Buffon投針（概率方法）；不平衡的燈Chebyshev不等式素因子的個數(shù)；不同和問題Chebyshev不等式

此不等式在概率論中具有非常重要的地位，而其由于涉及到隨機變量的方差，故常稱其為二階矩方法。對一個隨機變量，一般記為期望，而記為方差。方差開根號后的則被稱為標準差。Chebyshev不等式

此不等式在概率論中具有非常重要的地位，而其由于涉及到隨機變量的方差，故常稱其為二階矩方法。對一個隨機變量，一般記為期望，而記為方差。方差開根號后的則被稱為標準差。對任意正實數(shù)，證明即下面的這條式子：令為所有n的素因子的個數(shù)，讓任意緩慢的趨向無窮大。那么素因子的個數(shù)定理：證明：從1到

之間隨機的抽取一個數(shù)

。對于素數(shù)

，令如果其他令，，對所有小于的素數(shù)求和。于是我們有，因為無論如何的

，都不會擁有10個以上的大于

的素因子。（這里的10可以是其他比較大的常數(shù)）令為所有n的素因子的個數(shù)，讓任意緩慢的趨向無窮大。那么素因子的個數(shù)定理：證明：從1到

之間隨機的抽取一個數(shù)

。對于素數(shù)

，令如果其他令，，對所有小于的素數(shù)求和。于是我們有，因為無論如何的

，都不會擁有10個以上的大于

的素因子。（這里的10可以是其他比較大的常數(shù)）因此，在探索與的漸進性質(zhì)時，它們將會有漸進相似的邊界?，F(xiàn)在，我們知道：又因為，所以現(xiàn)在，我們知道：又因為，所以再由于期望的線性性質(zhì)和一個重要事實：我們有下面的結果：現(xiàn)在，我們知道：又因為，所以再由于期望的線性性質(zhì)和一個重要事實：我們有下面的結果：接下來我們要探討隨機變量的方差的漸進表達。隨機變量的方差：由于，所以隨機變量的方差：由于，所以另一方面，由于與

是不同的兩個素數(shù)，所以

等價于

且

，即等價于。因此，所以，由此可得，類似的我們也可以得到，這也就是說明，協(xié)方差對方差沒有影響，所以。所以，由此可得，類似的我們也可以得到，這也就是說明，協(xié)方差對方差沒有影響，所以。最后利用Chebyshev不等式：對任意成立。又因為與之間相差10以內(nèi)，所以此性質(zhì)對同樣適用。這樣就完成了證明。不同和定義：包含正整數(shù)，的集合具有不同和的性質(zhì)，如果任意元素之間的和均不相同。均不相同。即不同和定義：包含正整數(shù)，的集合具有不同和的性質(zhì)，如果任意元素之間的和均不相同。均不相同。即現(xiàn)在定義：對于集合

，在其具有不同和性質(zhì)的所有子集中，元素最多的集合的元素個數(shù)就定義為。不同和定義：包含正整數(shù)，的集合具有不同和的性質(zhì)，如果任意元素之間的和均不相同。均不相同。即現(xiàn)在定義：對于集合

，在其具有不同和性質(zhì)的所有子集中，元素