Sets of medians in the non-geodesic pseudometric space of unsigned genomes with breakpoints

Abstract

Background

The breakpoint median in the set S _n of permutations on n terms is known to have some unusual behavior, especially if the input genomes are maximally different to each other. The mathematical study of the set of medians is complicated by the facts that breakpoint distance is not a metric but a pseudo-metric, and that it does not define a geodesic space.

Results

We introduce the notion of partial geodesic, or geodesic patch between two permutations, and show that if two permutations are medians, then every permutation on a geodesic patch between them is also a median. We also prove the conjecture that the input permutations themselves are medians.

Backgound

Among the common measures of gene order difference between two genomes, the edit distances, such as reversal distance or double-cut-and-join distance, contrast with the breakpoint distance in that the former are defined in a geodesic space while the latter is not. Another characteristic of breakpoint distance that it does not share with most other genomic distances is that it is a pseudometric rather than a metric.

A problem in computational comparative genomics that has been extensively studied under many definitions of genomic distance is the gene order median problem [1], the archetypical instance of the gene order small phylogeny problem. The median genome is meant, in the first instance, to embody the information in common among k ≥ 3 given genomes, and second, to estimate the ancestral genome of these k genomes. We have shown that the second goal becomes unattainable as n → ∞, where n is the length of the genomes, if there are more than 0.5n mutational steps changing the gene order [2]. Moreover, we have conjectured, and demonstrated in simulation studies, that where there is little or nothing in common among the k input genomes, the median tends to reflect only one (actually, any one) of them, with no incorporation of information from the other k − 1 [3].

In the present paper, we investigate this conjecture mathematically in the context of a wider study of medians for the breakpoint distance between unsigned linear unichromosomal genomes, although the methods and results are equally valid for genomes with signed and/or circular chromosomes, as well as those with χ >1 chromosomes, where χ is a fixed parameter. Our approach involves first a rigorous treatment of the pseudometric character of the breakpoint distance. Then, given the non-geodesic nature of the space we are able to define a weaker concept of geodesic patch, that we use later, given two or more medians, to locate further medians. We also prove the conjecture that for k genomes containing no gene order information among them, the normalized (divided by n) median score tends to k − 1, with high probability.

Results

From pseudometric to metric

We denote by S _n the set of all permutations of length n. Each permutation represents a unichromosomal linear genome where the numbers all represent different genes. For a permutation π := π₁ ... π _n we define the set of adjacencies of π to be all the unordered pairs {π _i , π_i+1} = {π _i+1 , π _i } for i = 1, ..., n − 1. For I ⊆ S _n we denote by ${\mathcal{A}}_I:={\mathcal{A}}_I^{\left(n\right)}$ the set of all common adjacencies of the elements of I. Then ${\mathcal{A}}_{S_n}=\varnothing$, and we also write ${\mathcal{A}}_{\varnothing }$ for the set of all pairs {i, j}, i ≠ j. For any I, J ⊆ S _n ${\mathcal{A}}_{I\cup J}={\mathcal{A}}_I\cap {\mathcal{A}}_J$. It will sometimes be convenient to write ${\mathcal{A}}_I$, the set of common adjacencies in I = {x₁, ..., x _k }, as ${\mathcal{A}}_{x_1},...,x_k$. For example A _x,y,z represents the set of adjacencies common to permutations x, y and z.

For x, y ∈ S _n we define the breakpoint distance (bp distance) between x and y by

$$d^{\left(n\right)}\left(x,y\right):=n-1-\left|{\mathcal{A}}_{x,y}\right|.$$

(1)

This distance is not a metric on S _n but rather a pseudometric because of nonreflexiveness: cases where d⁽ⁿ⁾ (x, y) = 0 but x ≠ y, namely x = π₁ ... π _n and y = π _n ... π₁, for any x ∈ S _n . In these cases, the permutations x and y are said to be equivalent, denoted by x ~ y. The equivalence class containing π is represented by [π] and contains exactly two permutations, π₁, ..., π _n and π _n , ..., π₁. The number of classes is thus n!/2. For any π, we denote the other element of [π] by $\bar{\pi }$. The bp distance, a metric on the set of all equivalence classes of S _n , denoted by ${Ŝ}_n:=S_n/~$ is defined by

$$d^{\left(n\right)}\left(\left[x\right],\left[y\right]\right):=d^{\left(n\right)}\left(x,y\right).$$

(2)

Where there is no risk of ambiguity, we can simplify the notation by using x and y instead of [x] and [y], and/or drop the superscript n.

It is clear that the maximum possible bp distance between two permutation classes is n − 1 when they have no common adjacencies. Bp distance is symmetric on S _n and hence on ${Ŝ}_n$. By construction, it is reflexive on ${Ŝ}_n$. To verify the triangle inequality, consider three permutations x, y, z. We have

$${\mathcal{A}}_{x,z}\supseteq {\mathcal{A}}_{x,y,z}={\mathcal{A}}_{x,y}\cap {\mathcal{A}}_{y,z}$$

(3)

Therefore

$$d\left(x,z\right)=n-1-\left|{\mathcal{A}}_{x,z}\right|\le n-1-\left|{\mathcal{A}}_{x,y}\right|-\left|{\mathcal{A}}_{y,z}\right|+|{\mathcal{A}}_{x,y}\cup {\mathcal{A}}_{y,z}|.$$

(4)

But $|{\mathcal{A}}_{x,y}\cup {\mathcal{A}}_{y,z}|=|{\mathcal{A}}_y\cap \left({\mathcal{A}}_x\cup {\mathcal{A}}_z\right)|\le n-1$ and hence the triangle inequality holds.

We say a pseudometric (or a metric) $\tilde{\rho }$ is right invariant on a group G if for any $x,y,z\in G,\tilde{\rho }\left(x,y\right)=\tilde{\rho }\left(xz,yz\right)$. The definition of the left invariance is similar. A pseudometric (metric) which is both right and left invariant is called invariant. Bp distance is an invariant pseudometric on S _n .

Definition 1 Given a set {x₁, . . . , x _k } ⊆ S and a pseudometric space ρ on S, a median for the set is µ ∈ S such that ${\sum }_{i=1}^k\rho \left(\mu ,x_i\right)$is minimal.

Defining the geodesic patch

A discrete metric space (S, ρ) is a geodesic space if for any two points x, y ∈ S there exists a finite subset of S containing x, y that is isometric with the discrete line segment [0, 1, ..., ρ(x, y)]. Any subset of S with this property, and there may be several, is called a geodesic between x and y. For example, all connected graphs are geodesic spaces. In a geodesic space the medians of two points x and y consist of all the points located on geodesics between x and y.

What can we say when the space is not a geodesic space? To answer this, we extend the concept of geodesic by introducing the concept of a geodesic patch. A geodesic patch between x and y is a maximal subset of S containing x, y which is isometric to a subsegment (not necessarily contiguous) of the line segment [0, 1, ..., ρ(x, y)]. For any two points x, y in an arbitrary metric space (S, ρ) there exists at least one geodesic patch between them because x, y is isometric to {0, ρ(x, y)}. In addition, any geodesic is a geodesic patch. Any point z on a geodesic patch between x, y satisfies:

$$\rho \left(x,y\right)=\rho \left(x,z\right)+\rho \left(z,y\right).$$

(5)

Therefore all the medians of two points x and y must lie on a geodesic patch between them. We denote the set of all permutations lying on geodesic patches connecting x, y ∈ S _n by $\overline{\left[x,y\right]}$, as in Figure 1.

Figure 1

Geodesic patch. The open dots are situated beneath distances for which there is no permutation. The filled dots are in $\overline{\left[x,y\right]}$; they represent permutations that can lie on a geodesic patch, and the dots within the outlined area represent a specific geodesic patch.

$\left({Ŝ}_n,d\right)$ is not a geodesic space. For example there is no geodesic connecting the identity permutation id and π := 1 2 x₁ x₂ ... x_n−4 n − 1 n when x₁ x₂ ... x_n−4 is a non-identical permutation on {3, ..., n − 2}. The smallest change to id is to cut one of its adjacencies, say {i, i + 1}, and rejoin the two segments in one of the three possible ways: 1 to n, 1 to i + 1 or n to i. Now if we cut the adjacencies {1, 2} or {n − 1, n} in id the distance of the new permutation to both id and π increases. If on the other hand we cut one of the other adjacencies in id all the ways of rejoining, which increase the distance to id, either increase or leave unchanged the distance to π, since {1, n}, {1, i + 1} and {n, i} are not adjacencies in ${\mathcal{A}}_{\pi }$. Therefore there is no geodesic connecting id to π.

Although ${Ŝ}_n$ is not a geodesic space there may still exist permutations with a geodesic between them. For example

$$\left\{id=123456,213456,312456,421356,531246,\pi =135246\right)$$

(6)

is a geodesic between id and π. Note d(id, π) = 5, the maximum possible distance in ${Ŝ}_6$.

The median value and medians of permutations with maximum pairwise distances

In this section we investigate the bp median problem in the case of k permutations with maximum pairwise distances. As we shall see later, this situation is very similar to the case of k uniformly random permutations. Let (S, ρ) be a pseudometric space.

The total distance of a point x ∈ S to a finite subset ∅ ≠ B ⊆ S is defined to be

$$\rho \left(x,B\right):={\displaystyle \sum _{y\in B}}\rho \left(x,y\right).$$

(7)

The median value of B, $m^{S,\rho }\left(B\right)$, is the infimum of the total distance when the infimum is over all the points x ∈ S, that is

$$m^{S,\rho }\left(B\right):=\underset{x\in S}{\mathsf{\text{inf}}}\rho \left(x,B\right).$$

(8)

We can extend this definition to sets with multiplicities. Let ∅ ≠ B ⊆ S. We define a multiplicity function n _B from B to $\mathbb{N}$ and write n _B (x) = n _x . We call A = (B, n _B ) a set with multiplicities. We define the total distance of a point x ∈ S to A to be

$$\rho \left(x,A\right):={\displaystyle \sum _{y\in B}}{n}_y\rho \left(x,y\right).$$

(9)

The definition of median value in Equation (8) can be extended in an analogous way to the median value of a set with multiplicity A. When S is finite then the total distance function takes its minimum on S and "inf" turns into "min" in the above formulation. The points of the space S that minimize the total distance to A are called the median points or medians of A and the set of all these medians is called the median set of A, denoted by M ^S,ρ(A).

Let B and A = (B, n _B ) be a subset and a subset with multiplicities of S _n . We define [B] to be the set of all permutation classes of S _n that have at least one of their permutations in B. That is

$$\left[B\right]=\left\{\left[x\right]\in {Ŝ}_n\mathsf{\text{such}}\mathsf{\text{that}}\exists y\in B\mathsf{\text{with}}x~y\right\}.$$

(10)

Two nonempty subsets B, B′ ⊆ S _n are said to be equivalent, denoted by B ~ B', if [B] = [B′]. Also we define [n _B ] to be a function from [B] to $\mathbb{N}$ with

$$\left[n_B\right]\left(\left[x\right]\right)=n_{\left[x\right]}:={\displaystyle \sum _{x~y\in B}}{n}_y.$$

(11)

Then the definition of [A] is straightforward:

$$\left[A\right]:=\left(\left[B\right],\left[n_B\right]\right),$$

(12)

and we say two nonempty subsets of S _n with multiplicities, namely A and A′ are equivalent, denoted by A ~ A′, if [A] = [A′]. In fact [A] is the equivalence class containing A. We call [A] a subset of ${Ŝ}_n$ with multiplicities. We use the notations "[ ]" and " ~ " for all the above concepts without restriction.

With these definitions we can readily verify that in the context of bp distance, for A ~ A′ and x ~ x′, we have

$$d\left(x,A\right)=d\left(x^{\prime },A^{\prime }\right)=d\left(\left[x\right],\left[A\right]\right).$$

(13)

Recall that we use d as both a metric on ${Ŝ}_n$ and a pseudometric on S _n . Therefore we can conclude that

$$m^{S_n,d}\left(A\right)=m^{S_n,d}\left(A^{\prime }\right)=m^{{Ŝ}_n,d}\left(\left[A\right]\right)$$

(14)

and similarly

$$\left[M^{S_n,d}\left(A\right)\right]=\left[M^{S_n,d}\left(A^{\prime }\right)\right]=M^{{Ŝ}_n,d}\left(\left[A\right]\right).$$

(15)

Henceforward, we will simplify by replacing the notation $m^{S_n,d}\left(A\right)$ and $M^{S_n,d}\left(A\right)$ by m _n (A) and M _n (A), respectively. Also for a subset [A] of ${Ŝ}_n$ with multiplicities, we will use the notation m _n ([A]) and M _n ([A]) instead of $m^{{Ŝ}_n,d}\left(\left[A\right]\right)$ and $M^{{Ŝ}_n,d}\left(\left[A\right]\right)$ respectively. Where there is no ambiguity we will suppress the subscript n.

Proposition 1 Suppose $X:=\left\{x_1,\dots ,x_k\right\}\subset {Ŝ}_n$ such that d(x _i , x _j ) = n − 1 for any i ≠ j, i ≤ i, j ≤ n. Then the bp median value of × is (k − 1)(n − 1). Moreover, m∗ is a median of X, m∗∈ M (X), if and only if $A_{m*}\subset {\cup }_{i=1}^k{A}_{x_i}$.

Proof Let $\pi \in {Ŝ}_n$ be an arbitrary permutation class. Since $A_{\pi ,x_i}\subset A_{x_i}$ and $A_{\pi ,x_j}\subset A_{x_j}$ for any 1 ≤ i, j ≤ k, we have $A_{\pi ,x_i}\cap A_{\pi ,x_j}=\mathrm{0̸}$. Also

$${\cup }_{i=1}^k{A}_{\pi ,x_i}\subset A_{\pi }$$

(16)

Therefore

$${\displaystyle \sum _{i=1}^k}\left|A_{\pi ,x_i}\right|\le \left|A_{\pi }\right|=n-1$$

(17)

Hence

$${\displaystyle \sum _{i=1}^k}d\left(\pi ,x_i\right)\ge \left(k-1\right)\left(n-1\right)$$

(18)

The equality holds letting π = x _i for any 1 ≤ i ≤ k. This proves the first part of the proposition. For the second part we know that m^∗ ∈ M (X) is equivalent with the fact that the total distance of m^∗ to X is (k − 1)(n − 1), and this is equivalent to ${\sum }_{i=1}^k\left|A_{m^{*},x_i}\right|=n-1$ and ${\cup }_{i=1}^k{A}_{m^{*},x_i}=A_{m^{*}}$ be written as $A_{m^{*}}\cap \left({\cup }_{i=1}^k{A}_{x_i}\right)$. This finishes the proof of the equivalence relation in the proposition.

Lemma 1 Let x, y, z be three permutation classes in ${Ŝ}_n$that are pairwise at a maximum distance n − 1 from each other. Then for any $w\in \overline{\left[x,y\right]}$ we have d (w, z) = n − 1.

Proof Having $w\in \overline{\left[x,y\right]}$ we have A _w ⊂ A _x ∪ A _y . Also we know that $A_z\cap \left(A_x\cup A_y\right)=\mathrm{0̸}$. This concudes the result.

The above lemma simply indicates that for any two points x _i , x _j in the set X in the proposition above $\overline{\left[x_i,x_j\right]}\subset M\left(X\right)$ since the total distance of each point in $\overline{\left[x_i,x_j\right]}$ to X is (k − 1)(n − 1).

Corollary 1 Suppose $X:=\left\{x_{1,\dots ,}{x}_k\right\}\subset {Ŝ}_n$such that d(x _i , x _j ) = n − 1 for any i ≠ j. Then ${\cup }_{i,j}\overline{\left[x_i,x_j\right]}\subset M\left(X\right)$.

What more can we say about the median positions? The notion of "accessibility" will help us to keep track of some other medians of the set X that are not in ${\cup }_{i,j}\overline{\left[x_i,x_j\right]}$. Before defining this concept, we first need more information about the properties of $\overline{\left[x,y\right]}$ for $x,y\in {Ŝ}_n$.

Lemma 2 Let $x,y\in {Ŝ}_n$. Then $z\in \overline{\left[x,y\right]}$if and only if $A_{x,y}\subset A_z\subset A_x\cup A_y$.

Proof We know $z\in \overline{\left[x,y\right]}$ if and only if d(x, z) + d(z, y) = d(x, y). On the other hand we can write A _z as follows

$$A_z=A_{z,x,y}\cup \left(A_{z,x}\backslash A_y\right)\cup \left(A_{z,y}\backslash A_x\right)\cup \left(A_z\backslash \left(A_x\cup A_y\right)\right),$$

(19)

where the pairwise intersection of the sets in the right hand side is empty. We can also write

$$d\left(x,z\right)=\left(n-1\right)-\left|A_{z,x,y}\right|-|A_{z,x}\backslash A_y|$$

(20)

and

$$d\left(z,y\right)=\left(n-1\right)-\left|A_{z,x,y}\right|-|A_{z,y}\backslash A_x|.$$

(21)

Furthermore

$$d\left(x,y\right)\le \left(n-1\right)-\left|A_{z,x,y}\right|$$

(22)

and

$$\left(n-1\right)-\left|A_{z,x,y}\right|-|A_{z,x}\backslash A_y|-|A_{z,y}\backslash A_x|=|A_z\backslash \left(A_x\cup A_y\right)|.$$

(23)

Now for "sufficiency", we have

$$\left(n-1\right)-\left|A_{z,x,y}\right|-|A_{z,x}\backslash A_y|-\left(n-1\right)-\left|A_{z,x,y}\right|-|A_{z,y}\backslash A_x|$$

(24)

$$=\left(n-1\right)-\left|A_{x,y}\right|\le \left(n-1\right)-\left|A_{x,y,z}\right|$$

(25)

Therefore by Equation (23) we have

$$\left(n-1\right)-\left|A_{z,x,y}\right|-|A_{z,x}\backslash A_y|-|A_{z,y}\backslash A_x|=|A_z\backslash \left(A_x\cup A_y\right)|\le 0$$

(26)

This results in |A _x,y | = |A _x,y,z | and hence in A _x,y ⊂ A _z . Otherwise the inequality in (26) will be strict, which is impossible. On the other hand the inequality in (26) shows $A_z\backslash \left(A_x\cup A_y\right)=\mathrm{0̸}$ which concludes at $A_z\subset A_x\cup A_y$.

For "necessity", we have

$$\left(n-1\right)-\left|A_{z,x,y}\right|-|A_{z,x}\backslash A_y|-|A_{z,y}\backslash A_x|+\left(n-1\right)-\left|A_{x,y}\right|=\left(n-1\right)-\left|A_{x,y}\right|$$

(27)

This is true because of A _z ⊂ A _x ∪ A _y and Equation (23). But since A _x,y ⊂ A _z ⊂ A _x ∪ A _y we have |A _x,y | = |A _x,y,z | and we can replace |A _x,y | by |A _x,y,z | in the left hand side of the last equality. This finishes the "necessity" proof.

Definition 2 Let × := {x₁, ..., x _k } be a subset of ${Ŝ}_n$. We say a permutation class $z\in {Ŝ}_n$is 1-accessible from X if there exists an m ∈ $\mathcal{N}$, a finite sequence y₁, ..., y _m where y _i ∈ X and z₁, ..., z _m , where $z_i\in {Ŝ}_n$ such that z₁ = y₁, z _m = z and $z_{i+1}\in \overline{\left[z_i,y_{i+1}\right]}$ for $i=1...m-1$. See Figure 2.

Figure 2

Accessibility. Illustration of how $\bar{Z}$ is constructed.

We denote the set of all 1-accessible points of X by Z(X). We define Z₀(X) := X. Also for r ∈ $\mathcal{N}$ ∪ {0}, by induction, we define Z_r+1(X) to be Z(Z _r (X)) and we call it the set of all r+1-accessible permutation classes. That is Z₁(X) = Z(X), Z₂(X) = Z(Z(X)) and so on. It is clear that Z_r+1(X) includes Z _r (X) and also ${\cup }_{x,y\in Z_r\left(X\right)}\overline{\left[x,y\right]}$. A permutation class z is said to be accessible from × if there exists r ∈ $\mathcal{N}$such that z ∈ Z _r (X). We denote the set of all accessible points by $\overline{Z}\left(X\right)={\cup }_{r\in IN\cup \left\{0\right\}}{Z}_r\left(X\right)$.

Note that $Z\left(\overline{Z}\left(X\right)\right)=\overline{Z}\left(X\right)$. This holds because for any 1-accessible permutation class z from $\overline{Z}\left(X\right)$, there must exist $m\in \mathcal{N},r_0\in \mathcal{N},\cup \left\{0\right\},y_1,...,y_m\in {\overline{Z}}_{r_0}\left(X\right)$, (the y _i 's must be in $\overline{Z}\left(X\right)$, thus there must be such an r₀) and z₁, ..., z _m where $z_i\in {Ŝ}_n$ such that z₁ = y₁, z _m = z and $z_{i+1}\in \overline{\left[z_i,y_{i+1}\right]}$. Therefore $z\in Z_{r_0+1}\left(X\right)\subset \overline{Z}\left(X\right)$. We can then conclude that $\overline{Z}\left(\overline{Z}\left(X\right)\right)=\overline{Z}\left(X\right)$.

Proposition 2 Suppose $X:=\left\{x_1,...,x_k\right\}\subset {Ŝ}_n$ such that d (x _i , x _j ) = n−1 for any i ≠ j. Then for any permutation class $z\in \overline{Z}\left(X\right)$ the total distance d (z, X) between z and × is (k −1)(n−1) and hence $\overline{Z}\left(X\right)\subset M\left(X\right)$ Furthermore if m₁, m₂ ∈ M (X) then $\overline{\left[m_{\mathsf{\text{1}}},m_{\mathsf{\text{2}}}\right]}\subset M\left(X\right)$.

Proof Suppose m₁, m₂ ∈ M (X) and $m^{*}\in \overline{\left[m_1,m_2\right]}$. By Lemma 2 and Proposition 1 we have $A_{m^{*}}\subset A_{m_1}\cup A_{m_2}\subset {\cup }_{i=1}^k{A}_{x_i}$. Applying Proposition 1 again, we have m^∗∈ M (X). Now it suffices to show that for any r ∈ IN ∪ {0}, Z _r (X) ⊂ M (X). We prove this by induction. For r = 0 this follows from Corollary 1. Suppose Z _r (X) ⊂ M (X). By definition we have Z_r+1(X) = Z(Z _r (X)). That is for z ∈ Z_r+1(X) there exists an m ∈ $\mathcal{N}$, y₁, ..., y _m ∈ Z _r (X) and z₁, ..., z _m , where $z_i\in {Ŝ}_n$, such that z₁ = y₁, z _m = z and ${z_i}_{+1}\in \overline{\left[z_i,y_{i+1}\right]}.z_1\in \overline{\left[y_1,y_2\right]}$ and by the fact we proved above z₁ ∈ M (X) since y₁, ..., y _m ∈ Z _r (X) ⊂ M (X). Continuing this we conclude that z₁, z₂, ..., z _m = z ∈ M (X). Hence Z_r+1(X) ⊂ M (X). This finishes the proof.

Conjecture 1 Every median point of X is accessible from X, that is $M\left(X\right)=\overline{Z}\left(X\right)$.

The median value and medians of k random permutations

In this section we study the median value and median points of k independent random permutation classes uniformly chosen from ${Ŝ}_n$. This is equivalent to studying the same problem for k random permutations sampled from S _n . All the results of this section carry over to permutations without any problem.

We make use of the fact that the bp distance of two independent random permutations tends to be close to its maximum value, n − 1. Xu et al. [4] showed that if we fix a reference linear permutation id and pick a random permutation x uniformly, the expected number and variance of $\left|{\mathcal{A}}_{id,x}^{\left(n\right)}\right|$ both are very close to 2 for large enough n. Because of the symmetry of the group S _n and the fact that bp distance is an invariant pseudometric the same results hold for two random permutations x and y. We first summarize the results we need from [4].

Let ${\tilde{\nu }}_n$ be the uniform measure on S_n. Let $\Pi :S_n\to {Ŝ}_n$ be the natural surjective map sending each permutation onto its corresponding permutation class.

Define

$${\nu }_n:=\Pi *{\tilde{\nu }}_n$$

(28)

to be the push-forward measure of ${\tilde{\nu }}_n$ induced by the map Π. It is clear that ${\nu }_n$ is the uniform measure on ${Ŝ}_n$. The following proposition is a reformulation of Theorems 6 and 7 in [4].

Proposition 3 [Xu-Alain-Sankoff ] Let × and y be two independent random permutation classes (irpc) chosen uniformly from ${Ŝ}_n$. Then

$$\mathsf{\text{E}}\left[d\left(x,y\right)\right]=n-3-\frac{2}{n}-o\left(\frac{2}{n}\right)$$

(29)

$$\mathsf{\text{Var}}\left[d\left(x,y\right)\right]=2-\frac{2}{n}-o\left(\frac{2}{n}\right)$$

(30)

Define the error function for the distance of x, y by

$${\epsilon }_n\left(x,y\right):=\left(n-1\right)-d\left(x,y\right)=\left|{\mathcal{A}}_{x,y}\right|.$$

(31)

Corollary 2 Suppose × and y are two irpc's sampled from the uniform measure ${\nu }_n$and $a_n$is an arbitrary sequence of real numbers diverging to +∞. Then $\frac{{\epsilon }_n\left(x,y\right)}{a_n}$converges to zero asymptotically ${\nu }_n^{*2}$-almost surely (a.a.s.), that is

$$\frac{{\epsilon }_n\left(x,y\right)}{a_n}\to 0inprobability.$$

(32)

Proof The proof is straightforward from [4] and Chebyshev's inequality.

Now we are ready to study the median value of k irpc's. Let [A] be a subset of ${Ŝ}_n$ with multiplicities and with k elements. Define

$$e_n\left(\left[A\right]\right):=\left(k-1\right)\left(n-1\right)-m_n\left(\left[A\right]\right).$$

(33)

Theorem 1 Let $X^{\left(n\right)}:=\left\{x_1^{\left(n\right)},x_2^{\left(n\right)},\dots .,x_k^{\left(n\right)}\right\}$be a set of k irpc in ${Ŝ}_n$sampled from the measure ${\nu }_n^{*k}$. Then their breakpoint median value $m_n^{*};=m_n\left(X^{\left(n\right)}\right)$ tends to be close to its maximum after a convenient rescaling with high probability, that is for any arbitrary sequence $a_n$→ ∞ as $n\to \infty ,\infty \frac{e_n^{*}}{a_n}\to 0$in ${\nu }_n^{*k}$-probability where $e_n^{*}:=e_n\left(X^{\left(n\right)}\right)$

Proof Let π be an arbitrary point of S _n . Let ${\mathcal{A}}_{\pi \backslash X}={\mathcal{A}}_{\pi }\backslash {\mathcal{A}}_X$. We have

$${\displaystyle \sum _{i=1}^k}\left|{\mathcal{A}}_{\pi ,x_i}\right|\le \left|{\mathcal{A}}_{\pi \backslash X}\right|+{\displaystyle \sum _{i=1}^k}\left|{\mathcal{A}}_{\pi ,x_i}\right|\le \left(n-1\right)+\left(\begin{array}{c}k\hfill \\ 2\hfill \end{array}\right){\alpha }_n$$

(34)

where ${\alpha }_n$ is max _i,j ε _n (x _i , x _j ). On the other hand m _n (X⁽ⁿ⁾) ≤ (k − 1)(n − 1). The reason is the same as has already been discussed in the proof of Proposition 1. Therefore subtracting (k − 1)(n − 1) we have

$$0\le e_n^{*}\le \left(\begin{array}{c}k\hfill \\ 2\hfill \end{array}\right){\alpha }_n.$$

(35)

Dividing by $a_n$ and letting n go to ∞ the result follows from the last corollary.

Theorem 2 Let $X^{\left(n\right)}:=\left\{x_1^{\left(n\right)},x_2^{\left(n\right)},\dots ,x_k^{\left(n\right)}\right\}$be a set of k irpc's in ${Ŝ}_n$sampled from the measure $v_n^{*k}$. Then for any permutation class $z^{\left(n\right)}\in \overline{Z}\left(X^{\left(n\right)}\right)$the total distance of z⁽ⁿ⁾ to × is close to (k −1)(n−1) with high probability after a convenient rescaling. More explicitly, for any arbitrary sequence of real numbers $a_n$ converging to ∞

$$\frac{\left(k-1\right)\left(n-1\right)-d^{\left(n\right)}\left(z^{\left(n\right)},X^{\left(n\right)}\right)}{a_n}\to 0in{v}_n^{*k}-\mathsf{\text{probability}}.$$

(36)

Therefore

$$\frac{d^{\left(n\right)}\left(z^{\left(n\right)},X^{\left(n\right)}\right)-m_n\left(X^{\left(n\right)}\right)}{a_n}\to 0in{v}_n^{*k}-\mathsf{\text{probability}}\mathsf{\text{.}}$$

(37)

Furthermore if $m_1^{\left(n\right)},m_2^{\left(n\right)}\in M_n\left(X^{\left(n\right)}\right)$ then for any ${\tilde{m}}^{\left(n\right)}\in \overline{\left[m_1^{\left(n\right)},m_2^{\left(n\right)}\right]}$

$$\frac{d^{\left(n\right)}\left({\tilde{m}}^{\left(n\right)},X^{\left(n\right)}\right)-m_n\left(X^{\left(n\right)}\right)}{a_n}\to 0in{v}_n^{*k}-\mathsf{\text{probability}}.$$

(38)

Proof The structure of the proof is similar to the proof of Proposition 1. Suppose $o\in {Ŝ}_n$ with ${\mathcal{A}}_o{\subset }_{i=1}^k\cup {\mathcal{A}}_{x_i}$. Let ${\alpha }_n$ be as defined in the proof of Theorem 1. Then by the same discussion we have

$$n-1\le {\displaystyle \sum _{i=1}^k}\left|{\mathcal{A}}_{o,x_i}\right|\le n-1+\left(\begin{array}{c}k\hfill \\ 2\hfill \end{array}\right){\alpha }_n.$$

(39)

Therefore

$$\left(k-1\right)\left(n-1\right)\ge d\left(o,X\right)\ge \left(k-1\right)\left(n-1\right)-\left(\begin{array}{c}k\hfill \\ 2\hfill \end{array}\right){\alpha }_n$$

(40)

and

$$\frac{\left(k-1\right)\left(n-1\right)-d\left(o,X\right)}{a_n}\to 0inprobability.$$

(41)

From Theorem 1 we have

$$\frac{\left(k-1\right)\left(n-1\right)-m_n\left(X\right)}{a_n}\to 0inprobability.$$

(42)

Hence

$$\frac{d\left(o,X\right)-m_n\left(X\right)}{a_n}\to 0inprobability.$$

(43)

It suffices to show that $z:=Z^{\left(n\right)}\in \overline{Z}\left(X\right)$ has the same property, that is ${\mathcal{A}}_z\in {\cup }_{i=1}^k{\mathcal{A}}_{x_i}$. But this is clear by induction. For the second part of the theorem let $m_{1,n}^{*},m_{2,n}^{*}\in M\left(X\right)$. Suppose $m^{*}\in \left[m_{1,n}^{*},m_{2,n}^{*}\right]$. By Theorem 1 $\frac{\left|A_{m_{in}^{*}\backslash X}\right|}{a_n}\to 0$ in probability for i = 1, 2. On the other hand we have ${\mathcal{A}}_{m^{*}\backslash X}\subset {\mathcal{A}}_{m_{1,n}^{*}\backslash X}\cup {\mathcal{A}}_{m_{2,n}^{*}\backslash X}$.

Therefore

$$\frac{\left|{\mathcal{A}}_{m^{*}\backslash X}\right|}{a_n}\to 0inprobability.$$

(44)

Therefore

$$\left(k-1\right)\left(n-1\right)\le d\left(m^{*},X\right)\le \left(k-1\right)\left(n-1\right)+\left(\begin{array}{c}k\hfill \\ 2\hfill \end{array}\right){\alpha }_n$$

(45)

since

$$\frac{|{\mathcal{A}}_{m^{*},x_i}\cap {\mathcal{A}}_{m^{*},x_j}|}{a_n}\to 0inprobability.$$

(46)

The statement follows from the last inequality.

Conclusions

We have shown that the median value for a set of random permutations tends to be close to its extreme value with high probability. Also it has been shown that every permutation accessible from a set of random permutations can be considered as a median of that set asymptotically almost surely, and conjectured that the converse is true, that every median is accessible from the original set in this way.

Further work is needed to characterize the existence and size of non-trivial geodesic patches, in order to assess how extensive the set of medians is.