[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. A mean statistics problem

  1. You are asked to find the typical temperature for a particular time of year centered around day 0. Suppose you have collected daily high temperatures x-n...xn for 2n+1 days in a row (with x0, the day 0 temperature, in the middle), but you are only allowed to report one "typical" temperature y. You will be punished for deviation from the typical temperature according to the formula p = ∑i (xi-y)². Given an explicit formula for the value of y that minimizes p.

  2. Now suppose you are allowed to include a predicted daily increment z, so that the guess for day i is now y+iz. Give an explicit formula for the values of y and z that between them minimize p = ∑i (xi - (y+iz))².

1.1. Solution

  1. We'll recast this as an orthogonal projection problem. Treat the xi as a vector x over a (2n+1)-dimensional space. We want to find the point in the 1-dimensional subspace where all coordinates are equal that is closest to x, i.e. to find the multiple of b = (1, 1, ..., 1) that is the orthogonal projection of x. From the orthogonal projection formula we get y = b(x⋅b)/(b⋅b) = b ∑xi/(2n+1). Or in terms of a single typical temperature y, we have y = ∑xi/(2n+1), the average temperature.

  2. Again we will do orthogonal projection, but now we are projecting onto a 2-dimensional subspace of all vectors of the form vi = y1 + zi. A basis for this space is given by b1 = (1, 1, 1, ..., 1) and b2 = (-n, ..., n). These happen to be orthogonal since b1⋅b2 = ∑[i=-n to n] i = 0. So we can project by taking y = x⋅b1/b1⋅b1 = ∑xi/(2n+1) as before and z = x⋅b2/b2⋅b2 = ∑ ixi / ∑ i². (The denominator for z can be converted to closed form if one really wants to.)

Also works: Take partial derivatives wrt y and z and set the result to zero; this gives the same answer if one is careful enough.

2. Equivalence relations and functions

Let f:A→B be some function.

  1. Show that the relation ~f, given by the rule x~fy if and only if f(x) = f(y), is an equivalence relation.

  2. Show the converse: if ~ is an equivalence relation on A, there exists a set B and a function f:A→B such that x~y if and only if f(x) = f(y).

2.1. Solution

Recall that ~ is an equivalence relation if it is (a) reflexive (x~x), (b) symmetric (x~y ⇒ y~x) and (c) transitive (x~y ∧ y~z ⇒ x~z).

  1. For the relation ~f, we have (a) f(x) = f(x), so x~fx; (b) x~fy ⇒ f(x)=f(y) ⇒ f(y)=f(x) ⇒ y~fx; and (c) x~fy ∧ y~fz ⇒ f(x) = f(y) ∧ f(y) = f(z) ⇒ f(x) = f(z) ⇒ x~fz. So ~f is reflexive, symmetric, and transitive.

  2. Given an equivalence relation ~ on A, let B = A/~ be the set of equivalence classes of ~, and let f:A→B be given by f(x) = [x] = {y|x~y}. Then f(x)=f(y) if and only if x and y are in the same equivalence class, i.e., if x~y.

3. Partial orders

Let A = ℕk be the set of all sequences of natural numbers of length k. Given two elements x and y of A, let x≤y if and only if xi≤yi for all i.

  1. Prove (by showing reflexivity, antisymmetry, and trasitivity) that ≤ as defined above is a partial order on ℕk.

  2. Give examples of choices of k for which ≤ is/is not a total order.
  3. Prove that (ℕk, ≤) contains no infinite descending chain, i.e. there is no infinite sequence a0, a1, a2, ..., where ai+1 < ai for all i.

  4. Now consider the set ℕ of all infinite sequences of natural numbers, where x ≤ y is defined to mean xi ≤ yi for all i∈ℕ. Prove or disprove: (ℕ, ≤) contains no infinite descending chain.

3.1. Solution

  1. Reflexivity: if x = y, then xi = yi ⇒ xi ≤ yi for all i, giving x ≤ y. Antisymmetry: if x ≤ y and y ≤ x, then for each i we also have xi ≤ yi and yi ≤ xi; it follows that xi=yi for all i and thus x = y. Transitivity: If x ≤ y and y ≤ z, then for each i, xi ≤ yi and yi ≤ zi, giving x ≤ z.

  2. Let k = 0, then N0 has exactly one element (the empty sequence), which is ≤ itself. It follows that any two elements of N0 are comparable and that (N0, ≤) is a totally ordered set. (The case k=1 also works, and is slightly more interesting). For a non-totally-ordered set, take k=2; then (0,1) and (1,0) (for example) are incomparable.

  3. Suppose we have an infinite descending chain a0 > a1 > ... . Write ai[0]...ai[k-1] for the k elements of ai; then we have ai+1[j] ≤ ai[j] for all i, j, and ai+1[j] < ai[j] for at least one j. It follows that ∑j ai+1[j] < ∑j ai[j] ≤ ∑j ai[j] - 1. An easy induction on i gives ∑j ai[j] ≤ ∑j a0[j] - i. But then for i > ∑j a0[j], we have ∑j ai[j] < 0, an impossibility. It follows that there is no infinite descending chain.

  4. Disproof by counterexample: Let ai[j] = 1 if i > j and 0 otherwise. Then ai+1[j] = ai[j] = 0 if j < i, ai+1[i] = 0 < ai[i] = 1, and ai+1[j] = ai[j] = 1 if j ≥ i+1. It follows that ai+1 < ai for all i, and the ai form an infinite descending chain.

4. Lattices

  1. Prove or disprove: In any lattice, x∨(y∧z) = (x∨y)∧(x∨z).
  2. Prove or disprove: In any lattice, x≥y ⇒ x∧(y∨z) = (x∧z)∨y.

4.1. Solution

These properties are known as the distributive law and the modular law, respectively. Both are false in general (although both hold in a lot of common lattices). The simplest counterexample to the modular law is the pentagon lattice N5, whose Hasse diagram looks like this:

  / \
 /   \
p     \
|      r
q     /
 \   /
  \ /

Here p≥q, but p∧(q∨r) = p∧1 = p while (p∧r)∨q = 0∨q = q ≠ p.

The distributive law also fails in N5: r∨(p∧q) = r∨p = 1, but (r∧p)∨(r∧q) = 0∨0 = 0 ≠ 1.

2014-06-17 11:57