概率论导论

1 Naive Definition of Probability 概率的朴素定义

1.

For each part, decide whether the blank should be filled in with $=,\le$ or $\gt$, and give a short but
clear explanation.

对每个部分, 确定空格填入$=,\le$ 或 $\gt$, 并给出简短清晰的解释.

• a) (probability that total after rolling 4 fair dice is 21)___(probability that total after rolling 4 fair dice is 22)

• a) (掷4次公正骰子后点数和为21的概率)___(掷4次公正骰子后点数和为22的概率)
  解 : 应填入$\gt$, 每个结果的概率相等, 可以用枚举法枚举点数和为21和点数和为22的可能情况的数目.

• b) (probability that a random 2 letter word is a palindrome)___(probability that a random 3 letter word is a palindrome)

• b) (随机选取2个字母构成回文串的概率)___(随机选取3个字母构成回文串的概率)
  解 : 应填入$=$, 对于3个字母构成的回文串, 其中间字母对最终结果没有影响, 与2个字符的情况等价.

2.

A random 5 card poker hand is dealt from a standard deck of cards. Find the probability of each of the following(in terms of binomial cofficients).
从一个标准牌库拿出5张扑克牌. 求解下面每种情况的概率.(用二项式系数$\tbinom{n}{k}$表示)

• a) A flush(all 5 cards beging the same suit; do not count a rayal flush, which is a flush with A,K,Q,J,10).

• a) 5张牌相同花色(排除5张牌是10 J Q K A的情况)的概率.
  解 : 所有可能的情况有$\tbinom{52}{5}$种, 5张都是同花 : 先选择一种花色, 在从同种花色中选择5张牌: $\tbinom{4}{1}\times \tbinom{13}{5}$; 考虑rayal flush, 即同花色的10 J Q K A: 考虑花色后选择的
  牌就确定了, 有$\tbinom{4}{1}$种. 所以最终概率为 : $\frac{\tbinom{4}{1}\times \tbinom{13}{5}-\tbinom{4}{1}}{\tbinom{52}{5}}$.

• b) Two pair(e.g., two 3’s, two 7’s, and an Ace).

• b) 两个对子(如两个3, 两个7和一个A).
  解 : 选择点数并选择2种花色-->在剩余点数种选择点数并选择2种花色-->在剩余点数种选择点数并选择1种花色
  概率为 : $\frac{\tbinom{13}{1}\times \tbinom{4}{2}\times \tbinom{12}{1}\times \tbinom{4}{2}\times \tbinom{11}{1}\times \tbinom{4}{1}}{\tbinom{52}{5}}$

3.

• a) How many paths are there from point (0,0) to point (110,111) in the plane such that each step either consists of going one unit up or one unit to the right?

• a) 从点(0,0)到点(110,111)在一个每次向上/右移动一单元的平面上共有多少种可能的路径?
  解 : 将路径编码为由字符U和R组成的序列, 例如:URUUUR..., 其中U和R分别代表第$i$步向上/向右. 对于从点(0,0)到点(110,111)的路径需要由110个R和111个U组成, 为确定一个序列我们需要确定U和R在序列中的位置 : 只需确定R在哪即可, 所以共有$\tbinom{221}{110}$个可能路径.

• b) How many paths are there from (0,0) to (210,211), where each step consists of going one uint up or one unit to the right, and the path has to go through (110,111)?

• b) 在与a)相同平面上从点(0,0)到(210,211)且必须经过点(110,111)有多少种可能路径?
  解 : 路径需要经过(110,111), 即从(0,0)-->(110,111)-->(210,211), 由上题可知到达(110,111)有$\tbinom{221}{110}$条路径. 接着我们需要100个R和100个U以到达(210,211), 由乘法原则共需要$\tbinom{211}{110}\times \tbinom{200}{100}$

4.

A norepeatword is a sequence of at least one(and possibly all) of the usual 26 letters a,b,...,z, with repetitions not allowed. For example, “course” is a norepeatedword, but “statistics” is not. Order matters, e.g., “course” is not same as “source”.

• A norepeatedword is chosen randomly, with all norepeatwords equally likely. Show that the probability that it uses all 26 letters is very close to $1/e$.

一个 无重复单词 是一个至少由一个字母(a~z)组成且不允许出现重复单词. 例如, course 是一个无重复单词,
但statistics不是. 考虑单词顺序 : course与source不同.

• 一个无重复单词被随机选择, 所有无重复单词被选择的可能性相同. 说明被选择的单词是由26个单词组成的概率
  接近$1/e$.

2 Story Proofs 讲述证明

5.

• Give a story proof that $\sum_{k=0}^{n}\tbinom{n}{k} = 2^n$

• 用讲述证明的方式证明等式$\sum_{k=0}^{n}\tbinom{n}{k} = 2^n$. (等式证明见第一章1.5节).
  解 : $\tbinom{n}{k}$可以看作从一个由字符0或1组成的长度为n的序列中选取k个位置为字符1,
  剩余位置为字符0. 而k从0到n即是长度为n的上述字符的所有可能 : 每个字符有两种可能, 根据
  乘法原则共有$2^n$种, 等式成立.

6.

• Give a story proof that
  $\;\;\;\;\;\;\frac{(2n)!}{2^n\times n!} = (2n-1)(2n-3)\cdots 3\times 1$
  解 : 可以用例 1.5.4思路 : 将2n个人两两组成n个合作伙伴, 下面将证明等式两边都是对有多少种组合
  方法的计数. 首先给2n个人编号$1$到$2n$. 一种方式是先让这2n个人任意排列, 然后将第1个和第2个
  组成一组, 第3个和第4个组成一组, 以此类推, 共有$(2n)!$种可能. 这里重复考虑了n组的顺序以及
  每组内部的顺序, 重复计数了$2^n\times n!$次, 所以除以重复计数次数. 另一种方式是对于1号选手, 他共有$2n-1$
  个伙伴选择, 接着对2号选手, 他有$2n-3$个伙伴选择(如果1选择了2号那么3号有$2n-3$种选择), 依次类推.

7.

• Show that for all positive integers $n$ and $k$ with $n\ge k$,
  $\;\;\;\;\;\;\tbinom{n}{k} + \tbinom{n}{k-1} = \tbinom{n+1}{k}$
  doing this in two ways : (a) algebraically and (b) with a “story”, giving an interpretation for why both sides count the same thing.
  Hint for the “story” proof: imagine n+1 people, with one of them pre-designated
  as “president”.

• 说明对于所有正整数$n$和$k$且$n\ge k$,
  $\;\;\;\;\;\;\tbinom{n}{k} + \tbinom{n}{k-1} = \tbinom{n+1}{k}$
  用两种方式说明 : (a)代数; (b)讲述证明, 解释为何两边计算的是同一个问题.
  讲述证明的提示 : 假象有$n + 1$个人并且有一个提前提名为主席.
  解 : 几何证明, 将左侧二项式系数展开:
  $\;\;\;\;$