一. 幾何
1. 在半徑為1的圓中隨機(jī)選取一點(diǎn)
- 方法1: 在x軸
[-1,1]，y軸[-1,1]的正方形隨機(jī)選取一點(diǎn)，如果此點(diǎn)在圓內(nèi)，則即為所求的點(diǎn)瓶珊。如果不在圓內(nèi)啸箫，則重新隨機(jī)直到選到了為止耸彪。 - 方法2: 從
[0, 2*pi)隨機(jī)選取一個(gè)角度，再在這個(gè)方向的半徑上隨機(jī)選取一個(gè)點(diǎn)忘苛。但半徑上的點(diǎn)不能均勻選取蝉娜，選取的概率要和離圓心的距離成正比，這樣才能保證隨機(jī)點(diǎn)在圓內(nèi)是均勻分布的扎唾。
二. 概率
1. 一根木棒召川，截成三截，組成三角形的概率是多少胸遇？
- 設(shè)第一段截
x荧呐，第二段截y，第三段1 - x - y纸镊”恫考慮所有可能的截法。 - 可能的截法中必須保證三條邊都是正數(shù)且小于原來邊長逗威，則有
0 < x < 1峰搪，0 < y < 1，0 < 1 - x - y < 1凯旭，畫圖可知概耻，(x,y)必須在單位正方形的左下角的半個(gè)直角三角形里使套，面積為1/2。 - 然后考慮能形成三角形的截法鞠柄。首先要滿足剛才的三個(gè)條件
0 < x < 1侦高，0 < y < 1，0 < 1 - x - y < 1厌杜，然后必須符合三角形的邊的要求矫膨，即兩邊之和大于第三邊，x + y > 1 - x - y期奔，x + 1 - x - y > y侧馅，y + 1 - x - y > x，化簡即得0 < x < 1/2呐萌，0 < y < 1/2馁痴，1/2 < x + y < 1畫圖可知，此時(shí)(x,y)必須在邊長為1/2的三角形的右上角的半個(gè)直角三角形里肺孤，面積為1/8罗晕。于是最終概率為(1/8) / (1/2) = 1/4。
2. 有一蘋果赠堵，兩個(gè)人拋硬幣來決定誰吃這個(gè)蘋果小渊，先拋到正面者吃。問先拋者吃到蘋果的概率是多少茫叭？
- 給所有的拋硬幣操作從1開始編號(hào)酬屉，顯然先手者只可能在奇數(shù)
(1,3,5,7…)次拋硬幣得到蘋果，而后手只可能在偶數(shù)次(2,4,6,8…)拋硬幣得到蘋果揍愁。 - 設(shè)先手者得到蘋果的概率為
p呐萨，第1次拋硬幣得到蘋果的概率為1/2，在第3次(3,5,7…)以后得到蘋果的概率為p/4（這是因?yàn)檫@種只有在第1次和第2次拋硬幣都沒有拋到正面（概率為1/4=1/2*1/2）的時(shí)候才有可能發(fā)生莽囤，而且此時(shí)先手者在此面臨和開始相同的局面）谬擦。 - 所以可以列出等式
p=1/2+p/4，解得p=2/3朽缎。
三. 期望
1. 拋一個(gè)六面的色子惨远，連續(xù)拋直到拋到6為止，問期望的拋的次數(shù)是多少话肖。
- 因?yàn)槊看螔伒?的概率相等北秽，都是
1/6，于是期望的次數(shù)就是1/(1/6)=6次狼牺。 - 假設(shè)期望的次數(shù)為
E羡儿。考慮第一次拋是钥，如果已經(jīng)拋到6了（概率為1/6）掠归，那么就不用再拋了缅叠。如果沒拋到6（概率為5/6），那么還需要繼續(xù)拋虏冻，可是還要拋多少次呢肤粱？顯然，現(xiàn)在開始知道拋到6的次數(shù)仍然是E厨相，但是剛剛已經(jīng)拋了一次了于是可以得到這個(gè)等式E = 1 * 1/6 + (1 + E) * 5/6领曼，解得E = 6。即期望的次數(shù)為6次蛮穿。
2. 一個(gè)木桶里面有 m個(gè)白球庶骄，每分鐘從桶中隨機(jī)取出一個(gè)球涂成紅色（無論白或紅都涂紅）再放回，問將桶中球全部涂紅的期望時(shí)間是多少践磅？
- 令桶中有i個(gè)紅球后再把全部球涂紅的期望時(shí)間為
a[i]单刁，此時(shí)再取出一個(gè)球，如果是紅色的（概率為i/m）府适，則直接放回羔飞，且剩余的期望時(shí)間仍是a[i]。 - 如果是白色的（概率為
1-i/m）檐春，則涂紅后放回逻淌，剩余的期望時(shí)間為a[i+1]，則a[i] = (1 + a[i]) * i/m + (1 + a[i+1]) * (1 – i/m)即a[i] = a[i+1] + m/(m-i)顯然疟暖，有a[m] = 0可以解得a[0] = m/m + m/(m-1) + … + m/1 + 0
3. 你有一把寶劍卡儒。每使用一個(gè)寶石，有 50% 的概率會(huì)成功讓寶劍升一級誓篱，50% 的概率會(huì)失敗朋贬。如果寶劍的級數(shù)大于等于5的話，那么失敗會(huì)使得寶劍降1級窜骄。如果寶劍的級數(shù)小于5的話，失敗沒有效果摆屯。問題是：期望用多少個(gè)寶石可以讓一把1級的寶劍升到9級邻遏？
- 用
a[i]表示從第i-1級升到第i級期望使用的寶石數(shù)量。 - 當(dāng)
i<=5時(shí)虐骑，因?yàn)椴粫?huì)降級准验，則期望的數(shù)量均為2，即a[2] = a[3] = a[4] = a[5] = 2 - 當(dāng)
i>5時(shí)廷没，因?yàn)闀?huì)降級糊饱，成功時(shí)一個(gè)寶石就夠了，不成功時(shí)需要倒退一級颠黎，需要先使用a[i-1]個(gè)寶石先回到i-1級另锋，再使用a[i]個(gè)寶石升到第i級滞项，即a[i] = 1 * 1/2 + (1 + a[i-1] + a[i]) * 1/2即a[i] = a[i-1] + 2可知，a[6]= 4, a[7] = 6, a[8] = 8, a[9] = 10則1級到9級需要的寶石數(shù)為a[2]+…+a[9] = 36夭坪。
4. 平均要取多少個(gè)(0,1)中的隨機(jī)數(shù)才能讓和超過 1
e 次文判， 其中 e 是自然對數(shù)的底
- 首先思考幾個(gè)簡單的問題:
- 任取
2個(gè)0到1之間的實(shí)數(shù), 它們的和小于1的概率是多少?
滿足x+y<1的點(diǎn)(x, y)占據(jù)了正方形(0, 1) * (0, 1)的一半面積, 因此這兩個(gè)實(shí)數(shù)之和小于1的概率為1/2=1/2! - 任取
3個(gè)0到1之間的實(shí)數(shù), 它們的和小于1的概率是多少?
3個(gè)數(shù)之和小于1的概率是1/6, 它是平面x+y+z=1在單位立方體中截得的一個(gè)三棱錐, 這個(gè)1/6可以例用截面與底面的相似比關(guān)系, 通過簡單的積分求得:
-
4個(gè)0到1之間的隨機(jī)數(shù)的和小于1的概率就等于四維超立方體一角的"體積", 它的"底面"是一個(gè)體積為1/6的三棱錐, 在第四維上對其進(jìn)行積分便可得到其"體積":
- 以此類推,
n個(gè)0到1之間的隨機(jī)數(shù)的和小于1的概率為1/n!, 反過來n個(gè)0到1之間的隨機(jī)數(shù)的和大于1的概率為1 - 1/n!
- 任取
- 加到第
n個(gè)數(shù)才剛好超過1的概率:
- 因此, 要想讓和超過
1, 需要累加的期望次數(shù)為:
5. 有一個(gè)隨機(jī)數(shù)生成器凭迹，不斷生成 [0,1] 的浮點(diǎn)數(shù) n 次夺衍，把這 n 個(gè)數(shù)放入到一個(gè)數(shù)組中，但是這個(gè)數(shù)組里面的值你都看不到是個(gè)黑箱客冈，要求用概率的角度分析出第 k 小的數(shù)是什么亡鼠？
- 不妨考慮引入第
n+1個(gè)隨機(jī)變量赏殃，由于分布是均勻的，且取值是[0,1]间涵，所以可以認(rèn)為第k小的變量的期望等于第n+1個(gè)變量小于等于第k小的變量的概率嗓奢。 - 那么問題就變?yōu)榱巳绾吻筮@個(gè)概率，從統(tǒng)計(jì)方案數(shù)出發(fā)浑厚。
- 它們的大小關(guān)系一共有
(n+1)!種股耽，而n+1個(gè)變量小于等于第k個(gè)變量的方案數(shù)一共有k×n!，因?yàn)榈?n+1個(gè)變量一共有k個(gè)位置可以插入钳幅。所以概率為k/(n+1)物蝙，也就是第k小的期望。 - 其他解法-概率密度
四. 隨機(jī)數(shù)產(chǎn)生
1. 已知有個(gè) rand7() 的函數(shù)敢艰，返回1到7隨機(jī)自然數(shù)诬乞，怎樣利用這個(gè) rand7()構(gòu)造 rand10()，隨機(jī) 1~10钠导。
- 產(chǎn)生隨機(jī)數(shù)的主要原則是每個(gè)數(shù)出現(xiàn)的概率是相等的震嫉，如果可以得到一組等概率出現(xiàn)的數(shù)字，那么就可以從中找到映射為
1~10的方法牡属。 -
rand7()返回1~7的自然數(shù)票堵，構(gòu)造新的函數(shù)(rand7()-1)*7 + rand7()，這個(gè)函數(shù)會(huì)隨機(jī)產(chǎn)生1~49的自然數(shù)逮栅。原因是1~49中的每個(gè)數(shù)只有唯一的第一個(gè)rand7()的值和第二個(gè)rand7()的值表示悴势，于是它們出現(xiàn)的概率是相等。 - 但是這里的數(shù)字太多措伐，可以丟棄
41~49的數(shù)字特纤，把1~40的數(shù)字分成10組，每組映射成1~10中的一個(gè)侥加，于是可以得到隨機(jī)的結(jié)果捧存。 - 具體方法是，利用
(rand7()-1)*7 + rand7()產(chǎn)生隨機(jī)數(shù)x，如果大于40則繼續(xù)隨機(jī)直到小于等于40為止昔穴，如果小于等于40镰官，則產(chǎn)生的隨機(jī)數(shù)為(x-1)/4+1
2. 已知一隨機(jī)發(fā)生器，產(chǎn)生0的概率是 p傻咖，產(chǎn)生1的概率是 1-p朋魔，現(xiàn)在要你構(gòu)造一個(gè)發(fā)生器，使得它產(chǎn)生0和1的概率均為 1/2卿操。
- 考慮連續(xù)產(chǎn)生兩個(gè)隨機(jī)數(shù)警检，結(jié)果只有四種可能：
00、01害淤、10扇雕、11，其中產(chǎn)生01和產(chǎn)生10的概率是相等的窥摄，均為p*(1-p)镶奉，于是可以利用這個(gè)概率相等的特性等概率地產(chǎn)生01隨機(jī)數(shù)。比如把01映射為0,10映射為1崭放。 - 于是整個(gè)方案就是：產(chǎn)生兩個(gè)隨機(jī)數(shù)哨苛，如果結(jié)果是00或11就丟棄重來，如果結(jié)果是01則產(chǎn)生0币砂，結(jié)果是10則產(chǎn)生1建峭。
3. 已知一隨機(jī)發(fā)生器，產(chǎn)生的數(shù)字的分布不清楚决摧，現(xiàn)在要你構(gòu)造一個(gè)發(fā)生器亿蒸，使得它產(chǎn)生0和1的概率均為 1/2。
- 考慮連續(xù)產(chǎn)生兩個(gè)隨機(jī)數(shù)
a掌桩、b边锁，結(jié)果有三種情況a==b，a>b波岛，a<b - 其中由于a和b的對稱性茅坛，
a>b和a<b出現(xiàn)的概率是相等的，于是可以利用這個(gè)概率相等的特性等概率地產(chǎn)生01隨機(jī)數(shù)盆色。
4. 已知一隨機(jī)發(fā)生器灰蛙，產(chǎn)生0的概率是 p，產(chǎn)生1的概率是 1-p隔躲，構(gòu)造一個(gè)發(fā)生器，使得它構(gòu)造 1物延、2宣旱、3 的概率均為 1/3; 更一般地，構(gòu)造一個(gè)發(fā)生器叛薯，使得它構(gòu)造 1浑吟、2笙纤、3、…n 的概率均為 1/n组力。
- 要從
n個(gè)數(shù)中等概率地產(chǎn)生一個(gè)隨機(jī)數(shù)省容，關(guān)鍵是要找到n個(gè)或更多個(gè)出現(xiàn)概率相等的事件，然后我們重復(fù)隨機(jī)地產(chǎn)生事件燎字，如果是跟這n個(gè)事件不同的事件直接忽略腥椒，直到產(chǎn)生這n個(gè)事件中的一個(gè)，然后就產(chǎn)生跟這個(gè)事件匹配的隨機(jī)數(shù)候衍。 - 由于
n個(gè)事件發(fā)生的概率相等笼蛛，于是產(chǎn)生的隨機(jī)數(shù)的概率也是相等的◎嚷梗考慮連續(xù)產(chǎn)生x個(gè)隨機(jī)數(shù)滨砍，結(jié)果應(yīng)該是x個(gè)0跟1的組合，為了使某些結(jié)果出現(xiàn)的概率相等妖异，我們應(yīng)該要讓這個(gè)結(jié)果中0和1出現(xiàn)的次數(shù)相等惋戏，即各占一半。 - 于是
x的長度必須是偶數(shù)的他膳，為了方便响逢，考慮連續(xù)產(chǎn)生2x個(gè)隨機(jī)數(shù)。每 -
x個(gè)0跟1各出現(xiàn)一半的結(jié)果可以賦予1到n的某個(gè)數(shù)矩乐，為了能夠表示這n個(gè)數(shù)龄句，需要0跟1各出現(xiàn)一半的總結(jié)果數(shù)大于等于n，即C(2*x, x) >= n解出最小的x即為效率最高的x散罕。 - 然后把前
n個(gè)0和1個(gè)出現(xiàn)一半的結(jié)果分別賦予1到n的值分歇。隨機(jī)時(shí)連續(xù)產(chǎn)生2*x個(gè)數(shù)，如果不是這n個(gè)結(jié)果中的一個(gè)則重新隨機(jī)欧漱，如果是的話則產(chǎn)生對應(yīng)的值作為隨機(jī)結(jié)果职抡。
五. 蓄水池抽樣
1. 給出從 n 個(gè)數(shù)中隨機(jī)選擇 m 個(gè)的方法。注意误甚，n 非常大缚甩，并且一開始不知道其具體值。數(shù)字流式給出窑邦，當(dāng)給完之后擅威，你必須立刻給出隨機(jī)的結(jié)果。
- 首先前
m個(gè)數(shù)字是必須拿的冈钦。 - 第
i個(gè)數(shù)到來的時(shí)候郊丛，以m/i的概率決定是否要選擇這個(gè)數(shù)字。如果選擇了這個(gè)數(shù)字，則隨機(jī)地替換掉m個(gè)數(shù)字中的一個(gè)厉熟。 - 如果前
i-1個(gè)數(shù)字的時(shí)候保證了每個(gè)數(shù)字被選取的概率相等导盅，則這樣做之后可以保證每個(gè)數(shù)字被選取的概率也相等，為m/i揍瑟。- 第
i個(gè)數(shù)選擇的概率是m/i白翻，因?yàn)樗惴ň褪沁@樣決定的。 - 考慮前
i-1個(gè)數(shù)字中的任意一個(gè)绢片，它在第i個(gè)數(shù)之前被選擇的概率是m/(i-1)滤馍。在第i個(gè)數(shù)字的時(shí)候，這個(gè)數(shù)字要被選擇的話又兩種可能杉畜，一是第i個(gè)數(shù)沒有被選中（概率是1-m/i）纪蜒，二是第i個(gè)數(shù)倍選中了（概率是m/i）但是替換掉的數(shù)字不是它（概率是1-1/m），于是這個(gè)數(shù)在第i個(gè)數(shù)時(shí)仍然被選擇的概率是m/(i-1) * ((1-m/i) + (m/i * (1-1/m))) = m / (i-1) * ((i-1) / i) = m/i此叠。 - 由數(shù)學(xué)歸納法原理知纯续，對于任意的
n，當(dāng)給完n個(gè)數(shù)的時(shí)候灭袁，選擇的結(jié)果可以保證這n個(gè)數(shù)中每個(gè)被選中的概率都是相等猬错。
- 第
六. 策略
1. 一個(gè)活動(dòng)，女生們手里都拿著長短不一的玫瑰花茸歧，無序地排成一排倦炒，一個(gè)男生從隊(duì)頭走到隊(duì)尾，試圖拿到盡可能長的玫瑰花软瞎，規(guī)則是:一旦他拿了一朵逢唤，后面就不能再拿了，如果錯(cuò)過了某朵花涤浇，就不能再回頭鳖藕，問最好的策略是什么?
- 從數(shù)學(xué)模型上說，就是先拒掉前面
k個(gè)人只锭，不管這些玫瑰花有多長著恩；然后從第k+1個(gè)人開始，一旦看到比之前所有花都要長蜻展，就毫不猶豫地選擇喉誊。 - 不難看出，
k的取值很講究纵顾，太小了達(dá)不到試的效果伍茄，太大了又會(huì)導(dǎo)致真正可選的余地不多了。 - 這就變成了一個(gè)純數(shù)學(xué)問題：在玫瑰花總數(shù)
n已知的情況下施逾，當(dāng)k等于何值時(shí)幻林，按上述策略選中最長玫瑰花的概率最大贞盯？如何求出最優(yōu)的k值音念？- 對于某個(gè)固定的
k沪饺，如果最長的玫瑰花出現(xiàn)在了第i個(gè)位置（k < i ≤ n），要想讓它被選中闷愤，就必須得滿足前i-1個(gè)人中的最好的人在前k個(gè)人里整葡，這有k/(i-1)的可能〖テ辏考慮所有可能的i遭居，我們便得到了試探前k個(gè)女生之后能選中最佳女生的總概率P(k)：
- 用
x來表示k/n的值，并且假設(shè)n充分大旬渠，則上述公式可以寫成：
- 對
-x · ln x求導(dǎo)俱萍，并令這個(gè)導(dǎo)數(shù)為0，可以解出x的最優(yōu)值1/e
- 對于某個(gè)固定的
