Bias – p. 4

Subsampling Bias (Continued)

These results are not fully developed.

We repeat the statement of Lemma B.1.1′:

Lemma B.1.1′ Let S be a sample from L and let Γ denote the collection of all nonempty subsets of L:

Then S is fair if and only if there is a function w : Γ → [0,1] such that:

, for all j ∈ L, and  , for all G ∈ Γ.

So, many properties of the collection of all fair samples can be explored by considering the somewhat more abstract collection of functions w : Γ → [0,1] such that:

, for all j ∈ L.

It can be shown—for what it is worth—that this collection of functions, denoted here by 𝕎_N, forms a convex polytope (a bounded convex polyhedron) of dimension 2^N − N − 1 in the vector space ℝ^Γ, which has dimension 2^N − 1.

A convex polytope can be uniquely identified by its vertices. Denote the set of all vertices of 𝕎_N by V(𝕎_N). The size of V(𝕎_N) is a rapidly growing function of N. For example, by my calculations the numbers of vertices of 𝕎_N for N = 1 to 7 are as follows:

The numbers in the table were determined with the assistance of a personal computer. The vertex counts for N ≥ 8 have not been calculated. It appears that the calculation for N = 8 would take years, possibly many years, using my current algorithm on a single desktop computer. (If only the value for N = 5 had been 1806 instead of 1292.)

Relating 𝕎_N to Correct Samples

The polytope 𝕎_N can also be related to correct samples. It can be shown that a sample S is correct if and only if there exists w ∈ 𝕎_N such that Pr[S = G] = w(G) / ‖w‖₁ for all G, where:

and where 1_Γ is the function in ℝ^Γ that maps every G ∈ Γ  to 1. In this case, ‖w‖₁, the L¹ norm of w, equals the inverse of the probability that any particular fragment will be included in S.

Significance of V(𝕎_N)

There is a simple correspondence between 𝕎_N and the collection of all fair samples from L, and there is also a simple correspondence between 𝕎_N and the collection of all correct samples. So, what is the significance of V(𝕎_N)? A vertex of 𝕎_N corresponds to a fair sample, S, for which the set {G ∈ Γ : Pr[S = G] > 0} is minimal. This set is minimal if it has no proper subset whose members can be assigned probabilities in a way that makes the resulting sample fair. A vertex of 𝕎_N also corresponds to a correct sample, S, for which the set {G ∈ Γ : Pr[S = G] > 0} is minimal in the same sense.

Another significance of V(𝕎_N) is that every member of 𝕎_N is a convex combination (or weighted average) of vertices. So, a complete description of V(𝕎_N) amounts to a complete description of 𝕎_N, which in turn amounts to a very good description of either the entire collection of fair samples or the entire collection of correct samples.

Counting the Vertices of 𝕎_N

Given a function w from Γ  to [0,1], it is relatively easy to test whether w ∈ 𝕎_N and whether w ∈ V(𝕎_N) (see Theorem B.3 below), but counting all the vertices appears difficult, or at least slow, for large N.

Theorem B.3 For any G ∈ Γ, let I_G denote the function from L to ℝ defined by:

(Note that I_G is also a vector in the vector space ℝ^N.) If w ∈ 𝕎_N, then w ∈ V(𝕎_N) if and only if the collection { I_G : G ∈ Γ and w(G) > 0 } is linearly independent in ℝ^N.

A consequence of the theorem is that if w is a vertex of 𝕎_N, then w(G) > 0 for at most N different sets G ∈ Γ. Call the collection {G ∈ Γ : w(G) > 0} the support of w, and denote it by Sup(w).

So, one way of enumerating the vertices of 𝕎_N involves enumerating the bases of the vector space ℝ^N that have the form {I_B1, I_B2, …, I_BN} where each B_i ∈ Γ, and solving a linear system for each such basis to find the unique values w₁, w₂, …, w_N such that:

Then let w : Γ → ℝ be the function defined by:

where for any sets G, H ∈ Γ,

If each w_i is nonnegative, then the function w so defined is a vertex of 𝕎_N. Otherwise, w ∉ 𝕎_N.

One complication here is the fact that the same vertex may be listed more than once, because the support of a vertex may not correspond to a complete basis for ℝ^N. (It is linearly independent, but it may have fewer than N members.) The algorithm can be adjusted to deal with this problem.

Obviously, enumerating the bases is a slow process when N is large, but any process of constructing all the vertices of 𝕎_N will be slow because V(𝕎_N) is so large. Counting the vertices when N is large would require additional mathematical insight into the problem (e.g., group actions and symmetries?).

An obvious upper bound for the size of V(𝕎_N) is given by:

but this bound is not at all tight.

When G = {i₁, i₂, …, i_k}, we may write e_G as e_{i1, i2, …, ik} . An example of a vertex in V(𝕎₇) written using this notation is:

Its support is {{1,2,3}, {4,5,6}, {1,4,7}, {2,5,7}, {3,6,7}}. Its values are v({1,2,3}) = v({4,5,6}) = 2/3, v({1,4,7}) = v({2,5,7}) = v({3,6,7}) = 1/3, and v(G) = 0 if G is any other nonempty subset of L. (The column vectors I_{1,2,3}, I_{4,5,6}, I_{1,4,7}, I_{2,5,7}, and I_{3,6,7} are linearly independent in ℝ⁷.)

The complete set of vertices of 𝕎₃ is written below:

Another fairly simple and intuitive but less economical way of representing a function:

when N is small is to write the vectors I_B1, I_B2, …, I_Bk side by side as column vectors and to write the coordinates w₁, w₂, …, w_k under the columns (omitting any columns for which w_i = 0). The vertices of 𝕎₃ are rewritten below using this notation:

Notice that all but one of these six vertices (v₂) have supports that partition L. Vertices of this type are simple and easy to find—there is one for each partition of L—but they become relatively more rare as N increases. The number of such vertices is the N^th Bell number B_N. The first few Bell numbers (starting with N = 1) are: 1, 2, 5, 15, 52, 203, 877. [A000110] Compare these numbers to the vertex counts in Table 1.

Note that the last vertex, v₆ or e_L, is the function that maps L to 1 and every other member of Γ  to 0. Call this vertex the trivial vertex. It corresponds to the trivial sample, which always includes every fragment in the lot. If S denotes the trivial sample, then Pr[S = G] = e_L(G) × m_G / m_L, which equals 1 if G = L and 0 if G ≠ L.

Any vertex besides e_L is called a nontrivial vertex. Any sample besides the trivial sample may be called a nontrivial sample. A proper sample is a sample S such that Pr[S = L] = 0. Obviously, a proper sample is nontrivial.

It can be shown that the trivial vertex e_L is connected to each other vertex of 𝕎_N by an edge of the polytope. So, if N > 1, then 𝕎_N can be considered a cone with apex e_L. All the interesting structure of 𝕎_N is found in the base of this cone.

The trivial vertex e_L is the only member of 𝕎_N whose 1-norm equals 1.

Every other point in the polytope has 1-norm greater than 1. The largest possible value for the 1-norm is N, and there is only one point in 𝕎_N (a vertex) whose norm equals this maximum. It is the function w that maps each singleton subset of L to 1 and maps every other nonempty subset to 0. The sets {w ∈ 𝕎_N : ‖w‖₁ = r}, for 1 ≤ r ≤ N, partition 𝕎_N into nonempty parallel slices.

There is a kind of duality relationship among points in the base of 𝕎_N, which relates each point w ∈ 𝕎_N to its dual w^*. If w ∈ 𝕎_N and w(L) = 0, then for ∅ ≠ G ⊂ L, define the dual of w by:

The dual operator defined here is different from, but in some ways similar to, the dual operator for a geometric algebra.

The support of w^* consists of the complement of every set in Sup(w). If w(L) = 0, then w assigns a nonzero value to a subset ∅ ≠ G ⊂ L if and only if w^* assigns a nonzero value to L \ G. It is easy to show that the dual operator is an involution, i.e., that w^** = w. Also:

 and 

If w is self-dual, i.e., if w^* = w, then ‖w‖₁ = 2. A vertex v ∈ V(𝕎_N) is self-dual if and only if v is of the form I_{{G, L \ G}} (a function in ℝ^Γ) for some ∅ ≠ G ⊂ L. The set of all self-dual w ∈ 𝕎_N is a simplex of dimension 2^N − 1 − 2, which is the convex hull of the collection of all self-dual vertices. For example, when N = 3, there are 3 self-dual vertices (v₃, v₄, and v₅ above), and their convex hull is a 2-simplex.

The group of symmetries of 𝕎_N includes all symmetries induced by permutations of the set L. The dual operator also permutes vertices of the polytope in a manner that preserves faces and adjacencies, although it does not preserve distances.

A simpler polytope (simpler than 𝕎_N) is obtained if we add constraints to require that w(G) = w(H) whenever |G| = |H|. In this case the resulting polytope 𝕌_N is a simplex of dimension N − 1, which has only N vertices, all of which are easily located. One can write the N vertices u₁, u₂, …, u_N as follows:

, for k = 1, 2, …, N.

The function u_k is a vertex of 𝕎_N if and only if k ∈ {1, N − 1, N}. So, not all the vertices of 𝕌_N are vertices of 𝕎_N unless N ≤ 3. In the case when N = 3, the three vertices u₁, u₂, and u₃ are equal to v₁, v₂, and v₆, respectively (see above).

For N > 2 the simplex 𝕌_N is a small subset of 𝕎_N. All the samples that can be obtained using the strategy described in Theorem B.1 are associated with functions w ∈ 𝕌_N. So, if N > 2, there are many, many fair samples that cannot be obtained by the strategy of Theorem B.1.

It seems that either fair samples or correct samples derived from functions w in 𝕌_N are better than other fair or correct samples, because they are more random. The type of sample that Gy uses to derive his expression for the fundamental sampling variance is essentially a correct sample of this type.

Group Actions

Perhaps the most obvious candidate to provide an interesting group action on 𝕎_N is the symmetric group Sym(L) or S_N, whose elements are all the permutations of the set L = {1, 2, …, N} and whose group operation is composition. If we compose permutations from left to right (in accordance with Keith’s training), the group acts on L on the right. There is an obvious way to make the same group act on the set Γ on the right. If G ∈ Γ and σ ∈ S_N, then define:

It is only slightly less obvious how to make the group S_N act on ℝ^Γ on the right. If w ∈ ℝ^Γ and σ ∈ S_N, then define w • σ by:

, for all G ∈ Γ.

This definition ensures that e_G • σ = e_G • σ . We also have the fact that the mapping w ↦ w • σ is a vector space automorphism. So, in particular, if w ∈ ℝ^Γ and we write:

then:

When restricted to the polytope 𝕎_N, this action becomes a right group action on 𝕎_N. When restricted to the vertex set V(𝕎_N), it becomes a right group action on V(𝕎_N). In fact, if restricted to the p-faces of 𝕎_N, for any 0 ≤ p ≤ 2^N − N − 1, it becomes a group action on those p-faces.

The primary reason for considering group actions on V(𝕎_N) is to count vertices of different types. The action of the group S_N partitions V(𝕎_N) into equivalence classes called orbits, the orbit of a vertex v being defined as:

The size of the orbit O_v can be calculated from the size of the stabilizer of v, defined as:

which is a subgroup of S_N. Since S_N is finite,

Finding and counting all the vertices in a given orbit O_v might be time-consuming, but it is conceivable that counting the permutations of L that leave v unchanged could be easier. Unfortunately there are complications, and it isn’t as easy as one might hope. Consider the six vertices of 𝕎₃, which were listed above. Obviously any permutation of L leaves vertex v₆ (e_L) fixed, because it leaves L fixed. So, the stabilizer of v₆ is the entire group S_N. The only nontrivial permutation that leaves v₃ fixed is the transposition (2,3), which leaves each member of Sup(v₃) unchanged. So, the stabilizer of v₃ is the cyclic subgroup of order 2 generated by (2,3). Similarly, the stabilizers for v₄ and v₅ are subgroups of order 2. Complications arise when we consider v₁ and v₂. Any nontrivial permutation of L moves at least two members of Sup(v₁), but it does so in a way that preserves Sup(v₁) itself (and the vertex) with no change. So, the stabilizer of v₁ is the entire group S_N (and similarly for v₂).

In this example it is easy to recognize the orbits. There are four of them: {v₁}, {v₂}, {v₃, v₄, v₅}, and {v₆}.

Measure Theory

One can also analyze the problem of fair sampling using the language of measure theory. The functions m : (L) → [0, ∞) and A : (L) → [0, ∞) can be viewed as finite positive measures on the measurable space (L, (L)). A function w : (L) → [0, 1] as described above leads to a positive measure W : (L) → [0, ∞) on the measurable space ((L), (L)). A sample space is obtained from ((L), (L)) by providing it with a prob­ability measure P. Then the criterion for fair sampling is that:

for any positive measure A defined on the measurable space (L, (L)). Rewriting,

where the measure W is given by:

The measure W must satisfy the following condition:

, for any positive measure A on (L, (L)).

In the case of a finite lot L with the discrete σ-algebra (L), the preceding requirement is equivalent to requiring that:

, for any j ∈ L,

where δ_j denotes a Dirac measure.

The use of measure theory makes the problem look much simpler in some ways, and it suggests ways to analyze fair sampling of infinite lots, with more general σ-algebras.

Unbiased Splitting

Although for N ≥ 2 it is always possible to take a fair proper sample from the lot, it may not be possible to split the lot probabilistically into two or more fractions, each of which constitutes a fair sample. In general, it is possible to split the lot into two fractions in such a way that each fraction is a fair sample if and only if no fragment in the lot accounts for more than half the lot’s total mass. (A proof is available.) If N = 2, this generally is impossible, because the two fragments never have exactly the same mass, and one fragment always provides more than half the total mass. For typical lab samples with large N, fair splitting is usually possible.

Theorem B.4 shows how a 3-fragment lot can be split probabilistically into two fair samples.

Theorem B.4 Let N = 3 and m₁ ≤ m₂, m₃ ≤ m_L / 2. If S is a sample such that:

and Pr[S = G] = 0 for all other subsets G ∈ Γ, then both S and L \ S are fair.

The result in Theorem B.4 is derived by solving a system of linear equations.

Another easy way to split a 3-fragment lot fairly is to choose a random binary partition of the lot with the probabilities given below and then choose one of the resulting subsets at random to be S.

Then:

This scheme S is both fair and correct. In fact, the correctness of S does not depend on how the random partition is chosen. Given any random or fixed partition of L, of any size, a sample obtained by selecting one of the members of at random is always correct. However, a careful choice of can guarantee that the sample and its complement are also fair.

The same scheme can be extended to larger lots. For N ≥ 3, choose a random binary partition using the probabilities shown below:

Then choose one of the two resulting fractions at random. The sample probabilities are given by:

The sample will always consist of either 1 or N − 1 fragments.

Notice that the final expression for p_j works even when the mass of one fragment, m_i, is exactly m_L / 2, giving p_i = 1 and p_j = 0 for j ≠ i, whereas the expression before it fails because of division by 0 in that case.

Derivation of p_j …

To find the expression for p_j, use Lemma B.1.1 and the assumptions stated above. Fix j with 1 ≤ j ≤ N and consider the possible samples that contain fragment j. Under the stated assumptions there are N such samples, corresponding to the N allowed partitions of L.

Then for any i and j,

Subtract a sum of terms from each side.

Rearrange and solve for p_i in terms of p_j.

Note that p₁ + p₂ + ⋯ + p_N = 1. So,

Solve the preceding equation for p_j.

The preceding scheme can be generalized further. If is a partition of L into three or more fractions, P₁, P₂, …, P_k, where each fraction P_i has mass less than m_L / 2, then a solution to the fair-splitting problem is given by:

(∗)

In all cases, Pr[S = G] = Pr[S = L \ G]. Both the sample S and the complementary sample L \ S are fair and correct. As before, this scheme can be extended to include the case where one fraction, P_i, weighs exactly m_L / 2, in which case Pr[S = P_i] = Pr[S = L \ P_i] = 0.5.

In general, if S is a fair sample such that Pr[S = G] = Pr[S = L \ G] for all G ⊆ L, then L \ S is also fair, because Pr[L \ S = G] = Pr[S = L \ G] = Pr[S = G] and S is fair. Furthermore, S and L \ S are both correct, since Pr[ j ∈ S] = Pr[ j ∈ L \ S] = 0.5.

Given m₁, m₂, …, m_N, where each m_j ≤ m_L / 2, and a linear ordering of the proper, nonempty subsets G₁, G₂, …, G_2^N−2 ⊆ L, solving an underdetermined 2N × (2^N − 2) linear system of rank 2N − 1 for the probabilities Pr[S = G_j], subject to nonnegativity constraints, will yield, at least in theory, all the solutions to the fair-splitting problem. The system can be represented as a matrix equation, Xp = J, where J denotes a column of 1’s, p is the column vector with entries p_j = Pr[S = G_j], and X is the 2N × (2^N − 2) matrix with entries given by:

For N = 3, an explicit matrix equation is shown below.

The solution space in this case is one-dimensional. The size of the problem and the dimension of the solution space grow rapidly with N.

Note: Although this algebra can be done in terms of the functions w ∈ 𝕎_N described above, there seems to be little advantage in doing so. The full set 𝕎_N can be defined and investigated without reference to the fragment masses, whereas the subset consisting of those functions w that solve the fair-splitting problem cannot be.

All solutions of the linear system satisfy the requirement that the sum of the probabilities must equal 1. Solutions might fail to satisfy nonnegativity constraints; however, under the stated assumptions, the particular solutions given by (∗) above are always nonnegative, fair, and correct.

The unique, minimum-length algebraic solution to the equation is given by X⁺J, which can be obtained using a singular value decomposition of X, although the solution might fail to satisfy the nonnegativity constraints. This solution, if nonnegative, is also correct, with Pr[ j ∈ S] ≡ 0.5.

The entire solution space, whether constrained to be nonnegative or not, has a symmetry that allows transposing all the probabilities Pr[S = G] and Pr[S = L \ G] for one solution to obtain another. This operation is length-preserving; so, the minimum-length solution, X⁺J, remains fixed under it, as do the solutions given by (∗).

For N ≥ 3, the (2^N − 2) × 1 column vector κ described below lies in the null space of X, implying that sufficiently small multiples of κ can be added to any particular solution to obtain new solutions, subject to the nonnegativity constraints.

The entire null space is the column space of the orthogonal projection matrix I − X⁺X, a basis for which can be found using a singular value decomposition of X.

For any p ≥ 2, if the mass of any fragment is more than m_L / p, it is impossible to split the lot into p fractions such that each fraction S_i is a fair sample (because if any S_i is a fair sample, then Pr[ j ∈ S_i] ≥ m_j / m_L for each fragment j). It seems likely that if each fragment weighs less than m_L / p, then the lot can be split into p fair fractions, but no proof is offered here for p > 2.

As I said: For what it is worth….