Question

Question 6: Let n 2 1 be an integer and let A[1...n] be an array that stores a permutation of the set { 1, 2, . .. , n). If the array A s sorted. then Ak] = k for k = 1.2. .., n and, thus. TL k-1 If the array A is not sorted and Ak-i, where iメk, then Ak-서 is equal to the "distance" that the valuei must move in order to make the array sorted. Thus, the summation in (1) is a measure for the "sortedness" of the array A: If the summation is small, then A is "close" to being sorted. On the other hand, if the summation is large, then A is "far away" from being sorted. In this exercise, you will determine the expected value of the summation in (1) Assume that the array stores a uniformly random permutation of the set 1,2,..., n) For each k = 1, 2, , n, define the random variable Xs = 1시서 _ 서. and let k-1 ·Assume that n = 1, Determine the expected value E(X) . Assume that n 2. Is the sequence X1, X2, ..., Xn of random variables pairwise independent? . Assume that n 2 1. Let k be an integer with 1 < k< n. Prove that E(%) = n+1 + 2 Hint: Assume Ak] = i. If 1-i < k, then Ak)- I AIk]-서 = i-k. For any integer m 1, = k-i. If k + 1-i-n, then m(m 1) 1+2+3+。..+m= Assume that n1. Prove that Ex)1 3 Hint: 1+2+3+D(2n+1)

Answer 1