Skip to content

Latest commit

 

History

History
52 lines (33 loc) · 2.34 KB

File metadata and controls

52 lines (33 loc) · 2.34 KB

Exercises 5.2-1


In HIRE-ASSISTANT, assuming that the candidates are presented in a random order, what is the probability that you will hire exactly one time? What is the probability that you will hire exactly n times?

Answer

分别是1/n和1/n!

Exercises 5.2-2


In HIRE-ASSISTANT, assuming that the candidates are presented in a random order, what is the probability that you will hire exactly twice?

Answer

如果第一个雇员的质量是k,那么质量高于k的雇员都必须在质量最高的雇员后面.

假设有n个雇员,质量分别是1,2,...,n.当第一个质量为k时,只雇佣2次的概率p = 1/(n-k).因为有n-k个质量比k高的,而且必须要最高的那个在前.而第一个质量为k的概率是1/n.所以

Exercises 5.2-3


Use indicator random variables to compute the expected value of the sum of n dice.

Answer

Expectation of a single die

Expectation of N dies

Exercises 5.2-4


Use indicator random variables to solve the following problem, which is known as the hat- check problem. Each of n customers gives a hat to a hat-check person at a restaurant. The hat- check person gives the hats back to the customers in a random order. What is the expected number of customers that get back their own hat?

Answer

每个人都是1/n的期望,所以总的是1

Exercises 5.2-5


Let A[1...n] be an array of n distinct numbers. If i < j and A[i] > A[j], then the pair (i, j) is called an inversion of A. (See Problem 2-4 for more on inversions.) Suppose that each element of A is chosen randomly, independently, and uniformly from the range 1 through n. Use indicator random variables to compute the expected number of inversions.

Answer

最简单的解法如下:

因为概率是一样的,所以出现正序和逆序是等量的,总共有n(n-1)/2对,所以期望是n(n-1)/4对.


Follow @louis1992 on github to help finish this task.