易校尉，涂 平，陳 欣

(武漢工業(yè)學(xué)院數(shù)學(xué)與計(jì)算機(jī)學(xué)院，湖北武漢 430048)

1 問題介紹

目前算法分析領(lǐng)域的一個(gè)熱點(diǎn)是利用隨機(jī)化的方法求解一些特殊NP問題的近似解，這些隨機(jī)算法的時(shí)間復(fù)雜度分析往往是比較困難的問題，一般著眼于計(jì)算或者是估計(jì)所給算法所需時(shí)間的數(shù)學(xué)期望。作者在一個(gè)問題的隨機(jī)算法實(shí)踐中曾遇到這樣一個(gè)問題(類似的問題在遺傳算法等隨機(jī)搜索算法中經(jīng)常出現(xiàn)):有四個(gè)數(shù)集:A、B、C、D，每次隨機(jī)地從這四個(gè)數(shù)集的兩個(gè)數(shù)集中選取兩個(gè)數(shù)，如此重復(fù)多次，直至每個(gè)數(shù)集都至少有兩個(gè)數(shù)被選取，求試驗(yàn)重復(fù)次數(shù)的數(shù)學(xué)期望。

為方便說明，可以把上面介紹的問題簡化為:桌上有四個(gè)洞，每次拋兩個(gè)球，這兩個(gè)球隨機(jī)地等可能地進(jìn)入其中的兩個(gè)洞(這兩個(gè)球不能進(jìn)同一個(gè)洞)，一旦發(fā)現(xiàn)每個(gè)洞內(nèi)至少有兩個(gè)球就不再拋球。問:平均要拋多少次球?

2 拋球次數(shù)的分布律

2.1 問題的初步分析及符號(hào)說明

設(shè)An表示事件:“前n－1次拋球后至少有一個(gè)洞內(nèi)少于兩個(gè)球，而第n次拋球后每個(gè)洞內(nèi)至少有兩個(gè)球”;Bn－1表示事件:“前 n－1次拋球后，有兩個(gè)洞內(nèi)各有一球，而其余兩個(gè)洞內(nèi)各至少有兩個(gè)球”;Cn－1表示事件:“前 n－1次拋球后，有一個(gè)洞內(nèi)有一球，而其余三個(gè)洞內(nèi)各至少有兩個(gè)球”

X為一隨機(jī)變量，表示停止拋球后的拋球次數(shù)，所求的問題即為求EX。此外，注意到P{X=n}=P(An)，其中n＞3。由全概率公式，有

2.2 第一種情形的概率

考慮到1號(hào)洞和2號(hào)洞的兩個(gè)球有可能是同一次拋球入洞，也可能是在兩次不同的拋球中入洞，由全概率公式有:

2.3 第二種情形的概率

首先注意，當(dāng)n＜5時(shí)

設(shè)En－1表示事件“前n－1次拋球后，1號(hào)洞內(nèi)恰有一球”。

由全概率公式，有

故由(8)及(12)有:當(dāng)n＞4時(shí)，

2.4 X 的分布律

由(1)、(5)及(7)有:

當(dāng) n＞4時(shí)，由(1)、(6)及(13)有:

即:當(dāng)n＞4時(shí)，

3 拋球次數(shù)的數(shù)學(xué)期望

3.1 要用到的幾個(gè)級(jí)數(shù)

3.2 拋球次數(shù)數(shù)學(xué)期望的計(jì)算

由離散型隨機(jī)變量的數(shù)學(xué)期望公式及(16)、(17)可知:拋球次數(shù)的數(shù)學(xué)期望為

4 計(jì)算機(jī)模擬算法及結(jié)果分析

上面的數(shù)學(xué)分析部分比較復(fù)雜，下面給出了多次重復(fù)試驗(yàn)所獲得的拋球次數(shù)的平均值，由大數(shù)定理可知，當(dāng)重復(fù)試驗(yàn)次數(shù)很大時(shí)，其平均值應(yīng)十分接近所求得的數(shù)學(xué)期望。

模擬程序分以下幾個(gè)模塊。

模塊一:tryt(int a［］)隨機(jī)地拋兩個(gè)球(兩個(gè)進(jìn)入不同的洞中)。

模塊二:isok(int a［］)用于判斷是否每個(gè)洞中至少有兩個(gè)球。

模塊三:countOfOkTry(int a［］)返回單次試驗(yàn)成功的拋球次數(shù)。

編制程序?qū)⒃撛囼?yàn)重復(fù)十萬次，計(jì)算拋球次數(shù)的平均值為6.573780，與理論值6.5738十分接近。說明上面的數(shù)學(xué)分析部分是準(zhǔn)確無誤的。

5 問題的推廣

利用所獲得的拋球次數(shù)的分布律(14)、(15)式可以算得拋球次數(shù)的方差，該方差的計(jì)算并無本質(zhì)困難，只是相對(duì)于數(shù)學(xué)期望的計(jì)算略為復(fù)雜而已，而且可以用計(jì)算機(jī)程序進(jìn)行模擬以驗(yàn)證其正確性。

本文只討論了4個(gè)洞，每次拋2個(gè)球的情形，可以進(jìn)一步討論m個(gè)洞，每次拋n個(gè)球的情形(其中n＜m)。這個(gè)一般問題到目前為止尚無一般結(jié)論，只能就特殊情形進(jìn)行個(gè)別討論。

［1］羅斯.應(yīng)用隨機(jī)過程——概率模型導(dǎo)論［M］.龔光魯，譯.北京:人民郵電出版社，2011.

［2］科曼.算法導(dǎo)論［M］.潘金貴，譯.北京:機(jī)械工業(yè)出版社.2006.

［3］丁建立.遺傳算法與螞蟻算法的融合［J］.計(jì)算機(jī)研究與發(fā)展，2003(9).

［4］克努特.計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)(第2卷)半數(shù)值算法［M］.蘇運(yùn)霖，譯.北京:機(jī)械工業(yè)出版社，2008.

［5］格雷厄姆.具體數(shù)學(xué)［M］.北京:機(jī)械工業(yè)出版社，2007.