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...x_n for 2n+1 days in a row (with x₀, 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 (x_i-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 (x_i - (y+iz))².

1.1. Solution

1. We'll recast this as an orthogonal projection problem. Treat the x_i 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 ∑x_i/(2n+1). Or in terms of a single typical temperature y, we have y = ∑x_i/(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 v_i = y1 + zi. A basis for this space is given by b₁ = (1, 1, 1, ..., 1) and b₂ = (-n, ..., n). These happen to be orthogonal since b₁⋅b₂ = ∑[i=-n to n] i = 0. So we can project by taking y = x⋅b₁/b₁⋅b₁ = ∑x_i/(2n+1) as before and z = x⋅b₂/b₂⋅b₂ = ∑ ix_i / ∑ 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 x_i≤y_i 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 a₀, a₁, a₂, ..., where a_i+1 < a_i for all i.

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

3.1. Solution

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

2. Let k = 0, then N⁰ has exactly one element (the empty sequence), which is ≤ itself. It follows that any two elements of N⁰ are comparable and that (N⁰, ≤) 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 a₀ > a₁ > ... . Write a_i[0]...a_i[k-1] for the k elements of a_i; then we have a_i+1[j] ≤ a_i[j] for all i, j, and a_i+1[j] < a_i[j] for at least one j. It follows that ∑_j a_i+1[j] < ∑_j a_i[j] ≤ ∑_j a_i[j] - 1. An easy induction on i gives ∑_j a_i[j] ≤ ∑_j a₀[j] - i. But then for i > ∑_j a₀[j], we have ∑_j a_i[j] < 0, an impossibility. It follows that there is no infinite descending chain.

4. Disproof by counterexample: Let a_i[j] = 1 if i > j and 0 otherwise. Then a_i+1[j] = a_i[j] = 0 if j < i, a_i+1[i] = 0 < a_i[i] = 1, and a_i+1[j] = a_i[j] = 1 if j ≥ i+1. It follows that a_i+1 < a_i for all i, and the a_i 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 N₅, whose Hasse diagram looks like this:

   1
  / \
 /   \
p     \
|      r
q     /
 \   /
  \ /
   0

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

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