学习安排（8月11日-8月13日）
1.主要学习视频Week4
链接（http://www.xuetangx.com/courses/MITx/6_00_2x/2014_T2/courseware/d39541ec36564a88af34d319a2f16bd7/）
2.辅助内容：教材第16、18和20章
蒙特卡罗模拟
帕斯卡的问题
即“连续掷一对骰子24次得到两个6”这个赌注是否有利可图。解决方法：
- 第一次投掷时，每个骰子掷出6的概率是1/6，所以两个骰子都掷出6的概率是1/36；
- 因此，第一次投掷时没有掷出两个6的概率是1 – 1/36 = 35/36；
- 因此，连续24次投掷都没有掷出两个6的概率是(35/36)24，差不多是0.51，所以掷出两个6的概率是1 – (35/36)24，大约是0.49。长期来看，在24次投掷中掷出两个6这个赌注是无利可图的。
def rollDie():
return random.choice([1,2,3,4,5,6])
def checkPascal(numTrials):
"""假设numTrials是正整数
输出获胜概率的估值"""
numWins = 0
for i in range(numTrials):
for j in range(24):
d1 = rollDie()
d2 = rollDie()
if d1 == 6 and d2 == 6:
numWins += 1
break
print('Probability of winning =', numWins/numTrials)
过线或不过线
在双骰儿赌博中，掷手（即掷骰子的人）可以选择在“过线”或“不过线”之间投注。
- 过线：如果初掷是“自然点”（7或11） ，那么掷手获胜；如果初掷是“垃圾点”（2、 3或12） ，那么掷手失败。如果掷出其他数字，这个数字就成为“点数”，掷手继续掷骰子。如果掷手在掷出7之前掷出这个点数，那么掷手获胜，否则掷手失败。
- 不过线：如果初掷是7或11，那么掷手失败；如果初掷是2或3，那么掷手获胜；如果初掷是12，则是平局（赌博的行话称为push）。如果掷出其他数字，那么这个数字成为“点数”，掷手继续掷骰子。如果掷手在掷出这个点数之前掷出7，那么掷手获胜，否则掷手失败。
是否有一种赌注比另一种更好呢？还是说二者都一样？我们编写一个程序模拟一个双骰儿游戏的过程，然后看看结果。
import random
def rollDie():
return random.choice([1,2,3,4,5,6])
class CrapsGame(object):
def __init__(self):
self.passWins, self.passLosses = 0, 0
self.dpWins, self.dpLosses, self.dpPushes = 0, 0, 0
def playHand(self):
throw = rollDie() + rollDie()
if throw == 5 or throw == 11:
self.passWins += 1
self.dpLosses += 1
elif throw == 2 or throw == 3 or throw == 12:
self.passLosses += 1
if throw == 12:
self.dpPushes +=1
else:
self.dpWins +=1
else:
point = throw
while True:
throw = rollDie() + rollDie()
if throw == point:
self.passWins += 1
self.dpLosses += 1
break
elif throw == 7:
self.passLosses += 1
self.dpWins += 1
break
def passResults(self):
return (self.passWins, self.passLosses)
def dpResults(self):
return (self.dpWins, self.dpLosses, self.dpPushes)
def crapsSim(handsPerGame, numGames):
"""handsPerGame, numGames是正整数
玩numGames游戏，每次handsPerGame手；输出结果
"""
games = []
#玩numGames次游戏
for t in range(numGames):
c = CrapsGame()
for i in range(handsPerGame):
c.playHand()
games.append(c)
#为每次游戏生成统计量
pROIPerGame, dpROIPerGame = [], []
for g in games:
wins, losses = g.passResults()
pROIPerGame.append((wins - losses)/float(handsPerGame))
wins, losses, pushes = g.dpResults()
dpROIPerGame.append((wins - losses)/float(handsPerGame))
#生成并输出摘要统计量
meanROI = str(round((100*sum(pROIPerGame)/numGames), 4)) + '%'
sigma = str(round(100*stdDev(pROIPerGame), 4)) + '%'
print('Pass:', 'Mean ROI =', meanROI, 'Std. Dev. =', sigma)
meanROI = str(round((100*sum(dpROIPerGame)/numGames), 4)) +'%'
sigma = str(round(100*stdDev(dpROIPerGame), 4)) + '%'
print('Don\'t pass:','Mean ROI =', meanROI, 'Std Dev =', sigma)
crapsSim的结构与很多典型的模拟程序一样：
(1) 运行多次游戏（可以将一次游戏看作前面模拟中的一次实验），然后将结果累加。每次游戏都包括很多手，所以需要一个嵌套循环；
(2) 为每次游戏生成统计量并保存；
(3) 最后，生成并输出摘要统计。在本例中，它输出每种赌注的投资回报率（ROI）的期望值，以及ROI的标准差。
如果玩家可以偷偷地使用一对做了弊的骰子，这种骰子出现5的概率要大于出现2的概率（5和2分别在骰子两个相对的面上），那会怎么样呢？为了测试这种情况，我们只需将rollDie的实现替换为以下代码：
def rollDie():
return random.choice([1,1,2,3,3,4,4,5,5,5,6,6])
这种骰子的微小改变会使获胜的几率发生戏剧性的变化。
使用查表法提高性能
如果运行crapsSim(100000000, 10)，对于大多数计算机来说，等待这个程序结束的时间太长了。这就提出了一个问题：是否有简单的方法可以加速这种模拟？
playHand的结果与循环执行的次数没有关系，只与跳出循环的条件有关。对于每个可能的点数，我们可以很容易地计算出掷出7之前掷出这个点数的概率。例如，假设这个点数是8，掷手会不断地掷骰子，直到掷出这个点数或者掷出7。有5种方式可以掷出8（<6, 2>、 <2, 6>、<3, 5>、 <5, 3>和<4, 4>），有6种方式可以掷出7，所以字典中键为8的值就是表达式5/11的值。（箱子里面有36个球,红球6个.蓝球5个,其他是白球,有放回的拿球,在拿到红球之前拿到蓝球的概率）
def playHand(self):
"""playHand函数的另外一种更快的实现方式
pointsDict = {4:1/3, 5:2/5, 6:5/11, 8:5/11, 9:2/5, 10:1/3}
throw = rollDie() + rollDie()
if throw == 7 or throw == 11:
self.passWins += 1
self.dpLosses += 1
elif throw == 2 or throw == 3 or throw == 12:
self.passLosses += 1
if throw == 12:
self.dpPushes += 1
else:
self.dpWins += 1
else:
if random.random() <= pointsDict[throw]: #在掷出7之前掷出点数
self.passWins += 1
self.dpLosses += 1
else: #在掷出点数之前掷出7
self.passLosses += 1
self.dpWins += 1
使用查表法替代计算的这种思想用途十分广泛。性能出现问题时，经常会采用这种方法。查表法是以空间换时间这种通用思想的一个典型例子。在对散列表的分析中，我们还看到了这种思想的另外一个例子：散列表越大，碰撞就越少，平均查找时间就越少。
