講座報(bào)告概率方法

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

證明，任意六個(gè)人中，總有三個(gè)人互相認(rèn)識(shí)，

或者互相不認(rèn)識(shí)。-----1947年匈牙利數(shù)學(xué)競(jìng)賽Ramsey數(shù)R(k,k)不失一般性,考慮以a端點(diǎn)的5條邊。因?yàn)橹挥袃煞N顏色，所以，至少有3邊同色。不妨設(shè)ab，ac，ad同為藍(lán)色。abcdefabcdefR(3,3):

證明，任意六個(gè)人中，總有三個(gè)人互相認(rèn)識(shí)，

或者互相不認(rèn)識(shí)。-----1947年匈牙利數(shù)學(xué)競(jìng)賽Ramsey數(shù)R(k,l)(1)R(3,3):

證明，任意六個(gè)人中，總有三個(gè)人互相認(rèn)識(shí)，

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

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

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

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

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

表示f是非負(fù)的，并且當(dāng)n趨于無窮時(shí)，g(n)/f(n)趨向于0

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

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

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

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

個(gè)頂點(diǎn)的集合

，令

為“由

誘導(dǎo)的

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

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

個(gè)頂點(diǎn)的集合

，令

為“由

誘導(dǎo)的

的子圖為單色的事件”。那么，又因?yàn)樵谥羞@樣的

有

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

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

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

這樣，對(duì)所有的，有：注意到

時(shí)，取

，滿足

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

這樣，對(duì)所有的，有：注意到

時(shí)，取

，滿足

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

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

當(dāng)且僅當(dāng)其不存在三個(gè)元素x，y，z，使得x+y=z。

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

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

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

當(dāng)且僅當(dāng)其不存在三個(gè)元素x，y，z，使得x+y=z。

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

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

為一個(gè)素?cái)?shù)，使得，同時(shí)令則

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

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

，當(dāng)

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

屬于

的個(gè)數(shù)的期望

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

的一個(gè)子集

（

的階

），使得：對(duì)所有的，。這樣顯然是sum-free的，這因?yàn)槿绻校M足，那么，必有但這與是的sum-free子集這一事實(shí)所矛盾。故完成證明。Sum-free集合問題對(duì)于每個(gè)固定的

，當(dāng)

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

屬于

的個(gè)數(shù)的期望

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

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

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

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

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

，所以

以概率

取值0，以概率

取值1。

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

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

，所以

以概率

取值0，以概率

取值1。

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

的矩陣形式來擺放燈泡，每一個(gè)燈泡要么是亮著的（），要么是熄滅的（）。同時(shí)存在著控制同一排或者同一列的轉(zhuǎn)換開關(guān)（

既是控制第

排的，而

則是控制第

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

的矩陣形式來擺放燈泡，每一個(gè)燈泡要么是亮著的（），要么是熄滅的（）。同時(shí)存在著控制同一排或者同一列的轉(zhuǎn)換開關(guān)（

既是控制第

排的，而

則是控制第

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

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

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

服從分布（

個(gè)獨(dú)立均勻分布{-1，1}下的隨機(jī)變量的和分布）。所以，證明：首先忽略行開關(guān)。獨(dú)立并均勻的讓，并設(shè)：對(duì)給定的，無論初始值如何，

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

服從分布（

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

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

與

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

此不等式在概率論中具有非常重要的地位，而其由于涉及到隨機(jī)變量的方差，故常稱其為二階矩方法。對(duì)一個(gè)隨機(jī)變量，一般記為期望，而記為方差。方差開根號(hào)后的則被稱為標(biāo)準(zhǔn)差。Chebyshev不等式

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

之間隨機(jī)的抽取一個(gè)數(shù)

。對(duì)于素?cái)?shù)

，令如果其他令，，對(duì)所有小于的素?cái)?shù)求和。于是我們有，因?yàn)闊o論如何的

，都不會(huì)擁有10個(gè)以上的大于

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

之間隨機(jī)的抽取一個(gè)數(shù)

。對(duì)于素?cái)?shù)

，令如果其他令，，對(duì)所有小于的素?cái)?shù)求和。于是我們有，因?yàn)闊o論如何的

，都不會(huì)擁有10個(gè)以上的大于

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

是不同的兩個(gè)素?cái)?shù)，所以

等價(jià)于

且

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

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

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