[FrontPage] [TitleIndex] [WordIndex

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

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.

2. Inversions

An inversion in a permutation p of the numbers 1..n is a pair of positions i < j with pi > pj. 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 Xij be the indicator variable that is 1 iff there is an inversion at positions i and j. It is immediate from symmetry that E[Xij] = 1/2 (more technical argument: there is a bijection between permutations setting Xij=1 and permutations setting Xij = 0, defined by swapping pi with pj and leaving everything else in place, so the sizes of the two sets of permutations are equal). So E[X] = ∑i<j E[Xij] = (n choose 2)/2 = n(n-1)/4.

  2. This is trickier. We will still use the variables Xij, each of which has Var[Xij] = E[(Xij)2] - (EXij)2 = 1/2 - 1/4 = 1/4. Now we can compute Var[X] = Var[∑Xij] = ∑ Var[Xij] + 2 ∑{ij kl} Cov(Xij, Xkl). 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 Xij and Xkl are independent, as the (uniform random) choice of which way to flip pi and pj has no effect on the similarly random choice of which way to flip pk and pl. 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[XijXil] = Pr[pi > pj and pi > pk]. There are 2 permutations of the three values that make this work, since pi must be biggest but the other two can be ordered however we like. This gives Cov(Xij, Xil) = 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[XijXjl] = Pr[pi > pj > pl] = 1/(3!) = 1/6, and Cov(Xij, Xjl) = 1/6 - (1/2)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[XijXkj] = Pr[pi > pj and pk > pj]. This is symmetric to the i=k case and Cov(Xij, Xkj) = 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

\begin{eqnarray*}
\sum_{i=0}^{n} i &=& \frac{n(n+1)}{2},\\
\sum_{i=0}^{n} i^2 &=& \frac{n(n+1)(2n+1)}{6}.
\end{eqnarray*}

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=0n (n-i)/n = 1/(n+1) ∑i=0n 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=0n ((n-i)/n) * (i/(n-1)) = 1/((n+1)(n)(n-1)) ∑i=0n (n-i)*i = 1/((n+1)(n)(n-1)) [n2(n+1)/2 - ∑i=0n i2] = 1/((n+1)(n)(n-1)) [n2(n+1)/2 - n(n+1)(2n+1)/6] = 1/(6n(n-1)) [3n2 - n(2n+1] = (n2 - n)/(6(n2-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=0n (xn - x2) = (2/(n(n+1))) [n2(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

  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.

  1. Technically, if R ranges over all sets, it's too big to be a set itself. If this worries you, assume that R is restricted to some very large universe of sets. (1)


2014-06-17 11:57