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?
分别是1/n和1/n!
In HIRE-ASSISTANT, assuming that the candidates are presented in a random order, what is the probability that you will hire exactly twice?
如果第一个雇员的质量是k,那么质量高于k的雇员都必须在质量最高的雇员后面.
假设有n个雇员，质量分别是1,2,...,n.当第一个质量为k时，只雇佣2次的概率p = 1/(n-k).因为有n-k个质量比k高的，而且必须要最高的那个在前.而第一个质量为k的概率是1/n.所以
Use indicator random variables to compute the expected value of the sum of n dice.
Expectation of a single die
 = \frac{1+2+3+4+5+6}{6} = 3.5 )
Expectation of N dies
 = \sum_{i = 1}^{n} E(X_i) = 3.5n )
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?
每个人都是1/n的期望，所以总的是1
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.
最简单的解法如下:
因为概率是一样的，所以出现正序和逆序是等量的，总共有n(n-1)/2对，所以期望是n(n-1)/4对.
Follow @louis1992 on github to help finish this task.