Common ancestors

In small towns, it is usual that almost everybody is a distant cousin of almost everybody else. What are the kinship statistics of a closed, homogeneous, stable population? The answer depends on the population size, the fertility distribution and mating customs. We will set up some terminology and define a very simplistic population model. The treatment is formally loose as we talk about sets and sequences of sets where we should be dealing with random variables and stochastic processes.

We denote the mother and father of x by m(x) and f(x), respectively. y is an ancestor of x if y = x or y is an ancestor of m(x) or f(x). Given two individuals x and y, their kinship proximity k(x,y) is defined as:

• if y is an ancestor of x or x is an ancestor of y, k(x,y) is the number of generations between x and y,
• else, k(x,y) := min{k(a,x) + k(a,y) : a is a common ancestor of x and y}.
  

A population X is stratified if it can be decomposed into a disjoint family of subsets or generations {X_i: i integer} such that for every x in X_i, {f(x),m(x)} is included in X_i−1. We define the kinship distribution at generation i as

K_i(n) := P(k(x,y) = n), x, y in X_i, n = 0,1,2,...

where P stands for "probability". Note that the stratification of X implies that k(x,y) is always even when x and y belong to the same generation (because two individuals of the same generation are always at the same distance to their common ancestor), so K_i(n) = 0 if n is odd. X is a stable population if K_i(n) = K_j(n) for every i, j; in this case we denote the kinship distribution simply by K(n). Let us define the fertility distribution at generation i as the following function:

r_i(n) := P(x has exactly n children), x is a woman in X_i, n = 0,1,2,...

X is said to be homogeneous if r_i(n) = r_j(n) for every i, j, in which case we simply write the unique fertility distribution as r(n).

We will study a very simplified model of population dynamics. So, we require that our population X have the following properties:

• X is stratified, stable and homogeneous.
  
• The median value of r(n) is 2, i.e. the population size does not change over time.
  
• X is a strict monogamy, i.e. any two individuals have the same mother if and only if they have the same father.
• Siblings do not mate. As for intergenerational incest, it is automatically ruled out by the stratified nature of X.
  

In a later entry we will explore X kinship distribution by means of computer simulation.

Convexity in (Zn,L∞): results

I have written an implementation of the wavefront algorithm for (Z²,L_∞). You will need Boost to compile it. The mode of usage is the same as the algorithm for (Z²,L₁). The figure shows the L_∞ wavefront hulls for several sets, confront them with the corresponding L₁ hulls.

Note that there is no particular inclusion relationship between L₁ and L_∞ wavefronts hulls: some times H_wave,L1(X) is included in H_wave,L∞(X), some other times it is the other way around, and in a third class of situations neither hull is included in the other. The union of both hulls seems to yield results closer to our geometric, "round" intuition of what convexity must look like; the question remains whether this operation defines a valid convexity operator.

Children and siblings

Suppose the fertility rate in a given society is R. If one makes a poll among the adult population asking for the number of siblings each person has, including themselves, the estimated number, let us call it S, will certainly not be R: for one, women without children are nobody's mothers, so they are not affecting the poll result, unlike in the calculation of R. The question arises, what is the relationship between R and S? As it turns out, S is not a simple function of the fertility rate, but it depends on the exact fertility distribution.

To simplify things, let us only deal with mother-to-children relationships, i.e. if we say that two persons are siblings we mean that they are born to the same mother. Let r(n) be the probability that an arbitrary woman has n children; the fertility rate R is then the expected value of the fertility distribution r(n), that is, R = ∑ n·r(n). We now define:

s(n) = P(an arbitrary individual has n siblings, including herself)

(P stands for "probability"). Let us calculate s(n). Suppose we have a group of M women who collectively will give birth to N individuals during their lifetimes. We have then:

N = ∑ n·r(n)·M = RM,

with the individuals being distributed as follows:

r(1)·M individuals with 1 sibling (counting themselves),
2·r(2)·M individuals with 2 siblings (counting themselves),
n·r(n)·M individuals with n siblings (counting themselves)...

So, s(n) is simply the number of individuals in the n-th group, divided by N:

s(n) = n·r(n)·M/N = n·r(n)/R.

And S, the expected value of s(n), is

S = ∑ n²·r(n)/R,

which expresses the relationship between r(n) and S that we were looking for. Using Cauchy's Inequality and the fact that ∑ r(n) = 1, we have:

R² = (∑ n·r(n))² = (∑ (n·√r(n)) · √r(n))² ≤
≤ (∑ n²r(n))(∑ r(n)) = ∑ n²r(n),

hence S = ∑ n²·r(n)/R ≥ R for every possible r(n).

A particularly simple case arises when the fertility follows a Poisson distribution with r(n) = Rⁿe^−R/n!. Simple formula manipulations show that in this situation r(n) = s(n + 1); hence S = ∑_{n ≥ 1} n·s(n) = ∑_{n ≥ 1} n·r(n − 1)= ∑_{n ≥ 0} n·r(n) + ∑_{n ≥ 0} r(n) = R + 1. The figure depicts a Poisson-distributed r(n) with R = 2.1, along with its associated s(n).

Origami hummingbird diagrams

These are the folding instructions for the origami sword-billed hummingbird shown in a prior entry (click on the images to enlarge):

You can also download the instructions as a PDF document: hummingbird.pdf.

The model can use some improving: for instance, the corner tucked at step 1 is basically unused, and could be pulled out and employed to enhance the bird tail. This is left as a challenge to the reader.

Almost sure colearning

In a prior entry we defined the act of colearning between agents A and B as a special mode of acquiring knowledge such that when some proposition φ is colearnt by A it follows that the fact "A knows φ" is colearnt by B, and viceversa. If A and B communicate through a reliable channel, i.e. they both know that each message from one to the other is guaranteed to get across, then implementing colearning is simple: when A gets to know φ, she just has to send a message to B informing of this fact.

If the channel is unreliable with probability 0 < P < 1 that each message is succesfully delivered, colearning cannot be achieved, but we can get almost sure colearning, i.e. colearning with probability one, with the only prerequisite that A and B behave in the following manner:

1. Every message is sent over and over (with some arbitrary delay between sends) until an acknowledgement is received.
2. An acknowledgement is always sent to every message received.
3. The fact that A and B follow rules 1 and 2 is coknown by A and B.
   

So, we have turned an unreliable channel into an almost surely reliable channel where each message is delivered with probability one; this is not the same as a reliable channel, though.

Almost sure colearning is directly applicable to the two-army problem previously discussed: we can have the armies reach an agreement on when to make a joint attack with probability one. This is not in contradiction with the proved unsolvability of the original problem. In particular, almost sure colearning cannot be achieved in bounded time.

Convexity in (Zn,L∞)

After having studied our generalized convexity concept for (Zⁿ,L₁), we investigate now the L_∞ metric:

dist((x₁,...,x_n),(y₁,...,y_n)) := max{|y_i−x_i|}.

As we will see, the analysis is entirely analogous as that of (Zⁿ,L₁).

Theorem. (Zⁿ,L_∞) is regular.

Proof. Let X, Y in Zⁿ such that B_rX ≤ B_rY, s ≥ r. Similarly as how we saw in the L₁ case, we can assume without loss of generality that r and s are nonnegative integers. If x belongs to B_sX \ B_rX there exists some x' in X such that r < dist(x',x) = |x_k−x'_k| ≤ s, for some k in {1,...,n}. Let x'' be the point defined by x''_k = x'_k + sign(x_k−x'_k) r, x''_i = x'_i for i ≠ k. Then, dist(x',x'') = r, dist(x'',x) = dist(x',x) − r ≤ s − r, hence x belongs to B_s−rB_rX. Since by hypothesis B_rX ≤ B_rY, we conclude that x also belongs to B_s−rB_rY ≤ B_sY.

The role played in (Zⁿ,L₁) by the set of extreme points of B_rx, V_rx = {x+rδ_i, x−rδ_i: i = 1,...,n}, and by separating half-spaces of the form H = {y in Zⁿ : σy_k ≤ b}, with σ in {+1,−1}, is played in (Zⁿ,L_∞) by correlates of these structures. We state the theorems without proof as they follow the same lines as the equivalent propositions for (Zⁿ,L₁).

Definition. A point of Zⁿ is said to be a ±1-vector if all its coordinates are either +1 or −1.

Definition. Let x be a point of Zⁿ, r ≥ 0. Let V_rx = {x+rv: v is a ±1-vector}. V_rx is the set of extreme points of B_rx.

Lemma. x is in H_wave(X) iff V_mx ≤ B_mX for some nonnegative integer m.

Definition. We say that a point p lies beside a half-space H = {x in Zⁿ : xv ≤ b}, where v is a ±1-vector, if pv ≥ b and (p − v)v < b and , i.e. pv is in [b,b+n).

Note that the points lying beside a half-space H = {x in Zⁿ : xv ≤ b} include, but are not limited to, those with pv = b. The figure shows the situation for Z². The key property of this definition is that any point x in H will intersect one and only one point lying beside H when drawing a ray starting from x along the the normal direction to H, v.

Theorem. Let X be a subset of Zⁿ completely contained in some half-space H = {x in Zⁿ : xv ≤ b}, where v is a ±1-vector, and p a point lying beside H. The points p−iv, 0≤i<dist(p,X), do not belong to H_wave(X).

Theorem. Let X be a bounded subset of Zⁿ and x a point outside H_wave(X). There is then a ±1-vector v such that for any half-space H = {y in Zⁿ : yv ≤ b} enclosing XU{x}, dist(x,p) < dist(p,X) where p lies beside H and is of the form x + kv for some k ≥ 0.

If in the waterfront hull algorithm for (Zⁿ,L₁) we traversed the boundary of an enclosing prism P, here we must work with an enclosing rhombic prism with each of its 2ⁿ faces lying at a hyperplane of the form π = {x in Zⁿ : xv = b}, with v a ±1-vector.

wavefront hull(X)
{determine the minimum X-enclosing rhombic prism P}
P ← ∏H_i, H_i = {x in Zⁿ : xv_i ≤ b_i}, v_i is a ±1-vector, i = 1,...,2ⁿ
for i = 1 to 2ⁿ
····for every p in P with p beside H_i and p in H_j, j ≠ i
········for k = 0 to dist(p,X) − 1
············mark(p−kv_i)
········end for
····end for
end for
{return the points of P that have not been marked}

In a later entry we will provide an implementation of the algorithm for Z² and compare the results with the L₁ case.

Origami hummingbird

I designed this very simple model during the past Easter holidays. The extremely long beak allows us to identify this specimen as a sword-billed hummingbird. When time permits, I will sketch the folding diagrams and publish them here.