根据离散概率返回int值的算法的疑惑

Question

这是在《算法》这本书上看到的一题，我没能想通左边期望的结果与右边算法的关系。

现假设a[]有5个元素，每个元素的值都为0.2。如果按照左边期望出现的结果，右边的算法当到a[3]出现i的概率为sum=0.8，但是i=3出现的概率应为a[3]=0.2。是我没理解期望结果（离散概率随机）的意思还是算法没有想清楚？

麻烦大家给解答，谢谢。

Answer 1

很简单，比如随机生成一个学生的成绩。为简化起见，学生的成绩用5分制吧。可以得 1 2 3 4 5 分。
显然，得某个分数的概率是不同的，假设分别是 0.05 0.15 0.4 0.3 0.1 （也就是说5%的人得到1分，15%的人得到 2 分 ...）
现在要按照这个分布率随机生成一个成绩，怎么做呢，首先生成一个0~1的随机数，比如生成了0.4710234 (我随便写的)
让这个值=r
把 0 0.05 0.15 0.4 0.3 0.1 放入a，因为数组下标从0开始，但是实际上没有0分，我们在数组前补一个0.
然后循环了。
sum = 0
先和a[0]的累加，sum = 0，判断是否大于r，也就是0.4710234，显然没有，继续
然后和1分的累加，sum = 0.05，判断是否大于r，没有，继续
和2分的累加 sum = 0.3 继续
和3分的累加 sum = 0.7，超过了 r，所以，返回当前下标 3
也就是说，根据随机数0.4710234，我们生成了一个学生的分数 3
因为随机数r是均匀分布在0~1之间的，所以根据数组a，我们生成1 2 3 4 5分的概率正好就是我们要的。