1. Increasing subsequences

Consider a random permutation of the numbers 1..2n. Suppose we take the subsequence consisting of the 1st, 3rd, 5th, etc. numbers in this sequence.

1. What is the probability that this subsequence is increasing?
2. What is the probability that this subsequence and the subsequence consisting of the 2nd, 4th, 6th, etc. cards are both increasing?

1.1. Solution

1. To produce a permutation on 2n numbers where the odd-position subsequence is increasing, we can first choose which n of the 2n numbers go in the odd-position sequence, and then choose an ordering for the even-position numbers (there is only one choice for the order of the odd-position numbers). This gives (2n choose n)*n! sequences out of (2n)! total sequences, for a probability of (2n choose n)*n! / (2n!) = (2n!)*n!/(n!n!(2n!)) = 1/(n!).

2. Now we just have to pick which numbers go in which subsequence: the probability that both subsequences are increasing is (2n choose n)/(2n!) = (2n!)/(n!n!(2n!)) = 1/(n!)².

2. Inversions

An inversion in a permutation p of the numbers 1..n is a pair of positions i < j with p_i > p_j. For example, 123 has no inversions, 312 has two inversions (31 and 32) and 321 has three inversions (32, 31, and 21).

1. Compute the expected number of inversions X in a random permutation on 1..n. (Hint: consider a single pair of positions and then use linearity of expectations.)
2. Compute the variance of X.

2.1. Solution

1. For each i < j, let X_ij be the indicator variable that is 1 iff there is an inversion at positions i and j. It is immediate from symmetry that E[X_ij] = 1/2 (more technical argument: there is a bijection between permutations setting X_ij=1 and permutations setting X_ij = 0, defined by swapping p_i with p_j and leaving everything else in place, so the sizes of the two sets of permutations are equal). So E[X] = ∑_i<j E[X_ij] = (n choose 2)/2 = n(n-1)/4.

2. This is trickier. We will still use the variables X_ij, each of which has Var[X_ij] = E[(X_ij)²] - (EX_ij)² = 1/2 - 1/4 = 1/4. Now we can compute Var[X] = Var[∑X_ij] = ∑ Var[X_ij] + 2 ∑_{{ij kl}} Cov(X_ij, X_kl). The first sum is easy: it's just (1/4)(n choose 2). The last part is messier. Observe first that if there is no overlap between ij and kl, then X_ij and X_kl are independent, as the (uniform random) choice of which way to flip p_i and p_j has no effect on the similarly random choice of which way to flip p_k and p_l. So the only place where we might get nonzero covariance is where ij and kl overlap. There are several cases. Below, we assume without loss of generality that i <= k:

   1. The overlap is in the first position: i=k. Then E[X_ijX_il] = Pr[p_i > p_j and p_i > p_k]. There are 2 permutations of the three values that make this work, since p_i must be biggest but the other two can be ordered however we like. This gives Cov(X_ij, X_il) = 2/6 - 1/4 = 1/12. There are (n choose 3) ways to get this case. Having picked a triplet {a,b,c} we must make i=a but have two choices for which of a,b to make j,l; however, these two choices give the same pair {ij,il}.

   2. The overlap is in the middle position: j=k. Then E[X_ijX_jl] = Pr[p_i > p_j > p_l] = 1/(3!) = 1/6, and Cov(X_ij, X_jl) = 1/6 - (1/2)² = 1/6 - 1/4 = -1/12. There are (n choose 3) ways to get this case. Note that the case i=l is equivalent and so doesn't add any cases.

   3. The overlap is in the last position: j=l. Then E[X_ijX_kj] = Pr[p_i > p_j and p_k > p_j]. This is symmetric to the i=k case and Cov(X_ij, X_kj) = 1/12. There are (n choose 3) ways to get this case.

   Here the first two cases cancel each other out, but we are still left with a contribution of 2(n choose 3)/12 from the last case. So the total variance is (1/4)(n choose 2) + (1/6)(n choose 3).

3. A deck of cards

A dealer constructs a deck of cards by choosing a number X between 0 and n uniformly at random (i.e., so that each possible value occurs with probability 1/(n+1)), and then putting in X red cards and n-X black cards. The dealer then shuffles the deck, obtaining a uniform random permutation of the n cards.

Suppose that the dealer turns over the first card and it's black. Conditioned on this event:

1. What is the probability that none of the cards in the deck are red?

2. What is the probability that the next card in the deck is red? (Assume in this case that n >= 2.)

3. What is the expected value of X, the number of red cards in the deck?

It may be useful for some of these cases to recall the formulas

3.1. Solution

We'll let B be the event that the first card is black.

1. We want Pr[X=0|B] = Pr[X=0 and B]/Pr[B] = Pr[X=0]/Pr[B], where the equation holds because X=0 implies that B occurs. To compute Pr[X=0], observe that all n+1 possible values of X are equally likely, so P[X=0] = 1/(n+1). For Pr[B], the direct way is to sum Pr[B|X=i]Pr[X=i] over all values of i. This gives 1/(n+1) ∑_i=0ⁿ (n-i)/n = 1/(n+1) ∑_i=0ⁿ i/n = (1/(n(n+1)))*((n(n+1))/2) = 1/2. So we get Pr[X=0|B] = (1/(n+1))/(1/2) = 2/(n+1).

2. Let R be the event that the second card is red. Now we want Pr[R|B] = Pr[R and B]/Pr[B]. We've already computed Pr[B] = 1/2. To compute Pr[R and B], again we'll sum over cases: Pr[R and B] = ∑ Pr[R and B|X=i] Pr[X=i] = 1/(n+1) ∑_i=0ⁿ ((n-i)/n) * (i/(n-1)) = 1/((n+1)(n)(n-1)) ∑_i=0ⁿ (n-i)*i = 1/((n+1)(n)(n-1)) [n²(n+1)/2 - ∑_i=0ⁿ i²] = 1/((n+1)(n)(n-1)) [n²(n+1)/2 - n(n+1)(2n+1)/6] = 1/(6n(n-1)) [3n² - n(2n+1] = (n² - n)/(6(n²-n)) = 1/6. Dividing Pr[R and B] by Pr[B] then gives Pr[R|B] = (1/6)/(1/2) = 1/3.

3. Now we want E[X|B] = ∑_x x Pr[X=x|B]. So let's start by computing Pr[X=x|B]; this is Pr[X=x and B]/Pr[B]. For the numerator we have Pr[X=x and B] = Pr[X=x] * Pr[B|X=x] = (1/(n+1)) * (n-x)/n = (n-x)/(n(n+1)). So Pr[X=x and B] is just 2(n-x)/(n(n+1)). Now we can compute ∑_x x Pr[X=x|B] = ∑_x 2x(n-x)/(n(n+1)) = (2/(n(n+1))) ∑_x=0ⁿ (xn - x²) = (2/(n(n+1))) [n²(n+1)/2 - n(n+1)(2n+1)/6] = (1/3)[3n - (2n+1)] = (n-1)/3.

4. Some related relations

Consider the binary relation R on sets given by R = { (A,B) : there exists an injection f:A->B }.¹

1. Show that R is reflexive.
2. Show that R is transitive.
3. Prove or disprove: R is a partial order.

4. Show that R is a refinement of the usual subset relation, in the sense that if A⊆B, then A R B holds.

4.1. Solution

1. xRx for any x since the indentity function fa=a is an injection from x to x.

2. If xRy and yRz we have injections f:x->y and g:y->z. Then gf:x->z is an injection, since if gfa = gfa', we have fa=fa' and thus a=a'.

3. R is not a partial order, since it is not antisymmetric: we have for example {1}R{2} and {2}R{1} but {1} != {2}.

4. Let f(a) = a, then f:A->B is an injection when A⊆B.