How to measure the optimality of word or gesture order with respect to the principle of swap distance minimization

This paper introduces a novel mathematical framework based on the quadratic assignment problem to measure the optimality of word and gesture orders via swap distance minimization, demonstrating that crosslinguistic gestures achieve at least 77% optimality and proposing a general principle of optimal assignment that unifies various linguistic optimization phenomena.

The Gist

Imagine you are trying to organize a messy bookshelf. You have a specific order in mind (maybe alphabetical), but sometimes you put books in a slightly different order. The question this paper asks is: Do humans naturally arrange things in a way that requires the least amount of "shuffling" to get back to the original order?

The author, Ramon Ferrer-i-Cancho, uses a mix of math, linguistics, and even hand gestures to prove that our brains are secretly obsessed with efficiency. Here is the breakdown of the paper in simple terms.

1. The "Permutahedron": A 3D Map of Chaos

Imagine all the possible ways you can arrange three items (let's say a Subject, a Verb, and an Object, like "The boy kicks the ball"). There are only six ways to say this:

• The boy kicks the ball (SVO)
• The ball kicks the boy (OVS)
• Kicks the boy the ball (VSO)
• ...and so on.

The author draws a map called a Permutahedron. Think of this as a 3D puzzle or a hexagon where every corner is one of those six sentence orders.

• If you can turn one sentence into another by swapping just two neighboring words (like swapping "boy" and "kicks"), those two corners are connected by a line.
• If you have to swap words far apart, you have to walk a longer path across the map.

The Rule: The paper suggests that nature prefers the "shortest path." If you start with a standard order, the variations we use should be the ones closest to it on this map.

2. The "Swap Distance" Game

The paper introduces a concept called Swap Distance.

• Analogy: Imagine you are playing a game of "Hot and Cold."
  • Hot (Distance 0): You are using the exact standard order.
  • Warm (Distance 1): You swapped two neighbors.
  • Cold (Distance 3): You completely reversed the sentence.

The Principle of Swap Distance Minimization says: The further you get from the standard order, the "colder" (less likely) it is to be used. We naturally avoid the "cold" extremes because they are harder for our brains to process.

3. How Do We Measure "Optimality"?

The author creates a new "scorecard" (called Ω) to measure how well a language or a gesture follows this rule.

• Score of 1.0 (Perfect): The arrangement is perfectly optimized. The most common order is right next to the second most common, and the probabilities drop off smoothly as you move away.
• Score of 0.0 (Random): The arrangement is no better than rolling dice.
• Negative Score: The arrangement is actually worse than random chance (it's chaotic).

4. The Experiment: Hand Gestures vs. Spoken Language

To test this, the author didn't just look at spoken languages (which are influenced by thousands of years of history and grammar rules). Instead, they looked at unconventional gestures.

The Setup:
People from different language backgrounds (English, Russian, Irish, Tagalog) were asked to act out scenes using only their hands.

• Reversible scenes: "The boy kicks the girl" (Either could kick the other).
• Non-reversible scenes: "The boy kicks the ball" (Only the boy can kick).

The Result:
Even though these people spoke different languages and were just using their hands, their gestures were highly optimized.

• Their gesture orders scored at least 77% optimal.
• In many cases, they hit 100% optimality.
• This means that when humans communicate without words, they instinctively arrange their movements to minimize the mental "shuffling" required to understand them.

5. The "Radiation" Effect

The paper discovered a beautiful pattern in how these optimal arrangements look.

• Analogy: Imagine a campfire.
  • The fire is the most likely order (e.g., Subject-Verb-Object).
  • The heat (probability) radiates outward.
  • The people sitting right next to the fire (distance 1) are very warm (very likely).
  • The people two steps away are cooler (less likely).
  • The people at the edge of the clearing (distance 3) are freezing (very unlikely).

The data showed that in both spoken languages and gestures, the "heat" (probability) always drops off as you move away from the most common order. This is a "side effect" (or epiphenomenon) of the brain trying to save energy.

6. The Big Picture: The "Optimal Assignment" Principle

Finally, the author suggests that this isn't just about words or gestures. It's a universal law of efficiency.

• The Umbrella Theory: He calls this the Optimal Assignment Principle.
• The Metaphor: Imagine a taxi company. You have drivers (words/gestures) and customers (meanings). To save gas (cognitive effort), you want to assign the closest drivers to the closest customers.
• This same math explains why:
  • Words are shorter when they are used more often (Zipf's Law).
  • Sentences avoid crossing dependencies (like "The dog that the cat chased bit the man").
  • Hand gestures follow a specific order.

Summary

This paper proves that efficiency is the universal language. Whether we are speaking English, Russian, or just using our hands to mime a story, our brains are constantly trying to minimize the "distance" between ideas. We naturally organize our communication to be as close to the "center" as possible, saving mental energy and making it easier for others to understand us.

The fact that strangers from different cultures, using only hand gestures, independently arrived at a 77%+ optimal arrangement suggests that this isn't just a cultural habit—it's a fundamental rule of how the human mind works.

Technical Summary

1. Problem Statement

The paper addresses the challenge of quantifying the degree to which word orders (or gesture orders) in communication systems adhere to the Principle of Swap Distance Minimization.

• Context: In linguistics, it is hypothesized that languages evolve to minimize the cognitive or communicative cost of word order. This cost is modeled as the "swap distance" (the number of adjacent swaps required to transform one permutation into another).
• The Gap: While previous research established that average swap distance ($\langle d \rangle$) is often lower than expected by chance, there was no standardized, normalized metric to measure the degree of optimality (how close a system is to the theoretical minimum) across different languages or experimental conditions.
• Goal: To develop a mathematical framework to normalize $\langle d \rangle$, creating an optimality score ($\Omega$) that ranges from 0 to 1 (where 1 is perfect optimality), and to apply this to cross-linguistic gesture data.

2. Methodology

A. Theoretical Framework: The Permutohedron

The authors model the space of all possible permutations of $n$ constituents (e.g., Subject, Object, Verb) as a permutohedron, a graph where:

• Vertices represent permutations.
• Edges connect permutations that differ by a single adjacent swap.
• The distance between vertices is the swap distance.

B. Defining the Optimality Score ($\Omega$)

The paper proposes a normalized score $\Omega$ based on the template used in previous linguistic optimization studies (e.g., for dependency distances):
$$\Omega = \frac{\langle d \rangle_r - \langle d \rangle}{\langle d \rangle_r - \langle d \rangle_{min}}$$
Where:

• $\langle d \rangle$: The observed average swap distance.
• $\langle d \rangle_r$: The expected average swap distance under a null hypothesis (random permutation of probabilities).
• $\langle d \rangle_{min}$: The minimum possible average swap distance achievable by rearranging the probabilities on the permutohedron.

Key Theoretical Derivations:

1. Null Hypothesis ($\langle d \rangle_r$): Instead of assuming a uniform distribution, the authors use a "random permutation" null hypothesis. This preserves the empirical distribution of probabilities (e.g., the dominance of a specific order) but shuffles them randomly across the permutohedron vertices.
   • Formula: $\langle d \rangle_r = \frac{\bar{S}}{N-1} \langle d \rangle_{max}$, where $\bar{S}$ is the dominance index ($1 - S$, with $S$ being the Simpson index) and $N = n!$.
2. Minimum Value ($\langle d \rangle_{min}$): Calculating $\langle d \rangle_{min}$ is identified as a specific case of the Quadratic Assignment Problem (QAP).
   • For $n=3$ (the case of S, O, V), the authors derive a closed-form solution (Equation 15) and a constructive algorithm: sort probabilities descendingly and assign them to vertices following a specific "breadth-first" traversal of the permutohedron (radiating from the most probable order).
3. Epiphenomena: The theory predicts that optimal arrangements must exhibit:
   • Radiation: Probability decreases as distance from the most likely order increases.
   • Adjacency: The two most likely orders must be adjacent in the permutohedron.
   • Contiguity: All orders with non-zero probability must form a contiguous path on the graph.

C. Data and Statistical Analysis

• Data Source: Frequency data of Subject-Object-Verb (SOV) permutations from unconventional gesture experiments involving speakers of English, Russian (SVO), Irish, and Tagalog (VSO).
• Conditions: Experiments were conducted under reversible (agent/patient can swap roles) and non-reversible conditions.
• Statistical Tests:
  • Wilcoxon signed-rank test: To compare observed $\langle d \rangle$ vs. expected $\langle d \rangle_r$.
  • Poisson Binomial Test: To calculate the probability ($P_o$) that the observed number of optimal cases ($\Omega=1$) occurred by chance.
  • Contiguity Test: To calculate the probability ($P_c$) that non-zero probability orders form a contiguous path by chance.

3. Key Contributions

1. Mathematical Formalization of Optimality: The paper introduces a rigorous, normalized metric ($\Omega$) for swap distance minimization, moving beyond simple "significance" testing to a measure of "degree of optimality."
2. Integration of QAP: It formally links linguistic word order optimization to the Quadratic Assignment Problem (QAP), unifying swap distance minimization with other linguistic principles like dependency distance minimization and compression (Zipf's Law) under a general "Principle of Optimal Assignment."
3. Derivation of Structural Constraints: The authors mathematically prove that minimizing swap distance necessitates specific structural properties (radiation, adjacency, contiguity), explaining why these patterns appear in natural languages without needing separate postulates for each.
4. Application to Gestures: The framework is successfully applied to non-verbal communication (gestures), demonstrating that the optimization principles are modality-independent.

4. Results

• High Degree of Optimality: Cross-linguistic gestures were found to be at least 77% optimal ($\Omega \ge 0.77$) across all languages and conditions.
• Frequency of Perfect Optimality: In half of the experimental conditions (e.g., Irish in both conditions, Tagalog in reversible), the gesture orders were fully optimal ($\Omega = 1$).
• Statistical Significance:
  • The observed $\langle d \rangle$ was significantly lower than the random baseline ($\langle d \rangle_r$) ($p < 0.004$).
  • The number of times the system hit perfect optimality ($\Omega=1$) was highly unlikely to be due to chance ($P_o \approx 3 \times 10^{-4}$ when combining conditions).
  • The contiguity of non-zero probability orders was also highly unlikely to be random ($P_c \approx 9.2 \times 10^{-4}$).
• Epiphenomena Confirmation: The data confirmed the theoretical predictions: dominant orders were adjacent, probabilities radiated outward from the dominant order, and all active orders formed contiguous paths on the permutohedron.

5. Significance

• Unified Theory of Linguistic Structure: By framing word order, dependency distance, and compression as special cases of the QAP, the paper proposes a General Principle of Optimal Assignment. This suggests that diverse linguistic phenomena arise from a single underlying optimization mechanism: minimizing the cost of assignment between elements and positions.
• Beyond Inductive Typology: The framework moves beyond traditional typology (which classifies languages by their dominant order, e.g., "SOV languages") to a token-based typology. It explains why certain orders are dominant and how the entire distribution of orders is constrained by the geometry of the permutation space.
• Cognitive Implications: The results suggest that the human cognitive system (even in the absence of a learned language, as seen in gestures) inherently seeks to minimize the "swap distance" or cognitive load required to process sequences.
• Methodological Advancement: The paper provides a robust toolkit for future research to test optimization principles in other communication systems (e.g., animal signaling, code-switching) and to distinguish between true optimization and random variation.

In conclusion, the paper establishes that the structure of word and gesture orders is not random but is heavily constrained by a principle of minimizing swap distance, a phenomenon that can be precisely measured, normalized, and mathematically predicted using the proposed $\Omega$ metric and QAP framework.