On the feasibility of dependency parsing of non-human sequences without a gold standard. Is evaluation possible in other species?

# On the feasibility of dependency parsing of non-human sequences without a gold standard. Is evaluation possible in other species?
Source: [https://arxiv.org/html/2607.06542](https://arxiv.org/html/2607.06542)
\\jvol

vv\\jnumnn\\jyear2025\\docheadShort paper\\pageonefooterAction editor: \{action editor name\}\. Submission received: DD Month YYYY; revised version received: DD Month YYYY; accepted for publication: DD Month YYYY\.

\\affilblock

Catherine Hobaiter2Thore Bergman3Morgan Gustison4Universitat Politècnica de Catalunya, Department of Computer Science University of St Andrews, School of Psychology and Neuroscience University of Michigan, Departments of Psychology and Ecology and Evolutionary Biology Western University, Department of Psychology

###### Abstract

Dependency parsing consists of finding a tree representation for a sequence\. Unsupervised dependency parsing aims to develop parsing methods without a gold standard during model training\. In human languages, an unsupervised parser can be evaluated because some gold standard is usually available or can be created\. For other species, a gold standard is unknown\. Thus one may conclude that it is impossible to determine the accuracy of an unsupervised parser and, consequently, dependency parsing is unfeasible in other species\. However, here we apply recent advances in network science to demonstrate that the proportion of correct edges retrieved by a parser must be high for the sequences of vocalizations or gestures that non\-human primates produce due to the fast decay of the sequence length distribution\. In contrast, human language sequences lack that property\. Therefore, evaluation without a gold standard is feasible in non\-human primates but a hard problem in humans\.

## 1Introduction

The syntactic structure of a sentence \(Figure[1](https://arxiv.org/html/2607.06542#S1.F1)\(a\)\) can be represented by asyntactic dependency structure,namely a rooted tree where vertices are words and arcs indicate syntactic dependencies between words as in Figure[1](https://arxiv.org/html/2607.06542#S1.F1)\(b\)Mel’čuk\([1988](https://arxiv.org/html/2607.06542#bib.bib31)\)\. A syntactic dependency treebank, hereafter atreebank, is a collection of sentences and their dependency structure\. Dependency parsing, hereafterparsing, is finding the tree representation of a sentence automatically, and aparseis the tree representation retrieved by aparserfor a sentenceMarecek\([2012](https://arxiv.org/html/2607.06542#bib.bib26)\);Carroll\([2014](https://arxiv.org/html/2607.06542#bib.bib5)\)\. Supervised parsers learn to parse by means of agold standard,usually a treebank with the correct or desired dependency structure for each sentence \(Figure[1](https://arxiv.org/html/2607.06542#S1.F1)\(b\)\)\. Supervised learning consists of fitting a model by means of a treebank as the gold standard\.Unsupervised parserslearn to parse without a treebank, namely they learn to parse just from a collection of raw sentences, namely just the word sequence \(as in Figure[1](https://arxiv.org/html/2607.06542#S1.F1)\(a\)\) or the word sequence plus part\-of\-speech informationHan et al\.\([2020](https://arxiv.org/html/2607.06542#bib.bib18)\)\.Unsupervised learningconsists of fitting a model without a gold standard\.Evaluationconsists of comparing the parses against a gold standard treebank\. Typical evaluation scores are the proportion of trees correctly retrieved or the proportion of dependencies correctly retrievedCarroll\([2014](https://arxiv.org/html/2607.06542#bib.bib5)\);Han et al\.\([2020](https://arxiv.org/html/2607.06542#bib.bib18)\)\.

![Refer to caption](https://arxiv.org/html/2607.06542v1/x1.png)Figure 1:\(a\) The raw sequence of words making the sentence\. \(b\) The syntactic dependency parse of Article 9 of the Universal Declaration of Human Rights by Stanza 1\.10\.1[http://stanza\.run/](http://stanza.run/)\. \(c\) The same parse as in \(b\) after removing dependency direction\.In many languages, the evaluation of a parser is straightforward because treebanks are already available\. In other languages, evaluation is not possible because treebanks are not forthcoming \(the so\-called “low\-resource” languages\), their development is technically costlyScheinerman\([2012](https://arxiv.org/html/2607.06542#bib.bib38)\)or the language itself poses theoretical challenges in how to define the structure of sentences \(see for instanceVasquez et al\.\([2018](https://arxiv.org/html/2607.06542#bib.bib43)\)orMartín Rodríguez et al\.\([2022](https://arxiv.org/html/2607.06542#bib.bib28)\)\)\. For other species, a gold standard is simply not forthcoming, representing a serious challenge for mainstream linguistics, which is human\-language based\. Although an unsupervised parser can be used to retrieve dependency structures from the sequences that other species produce, the hard problem is the evaluation: the parser will produce dependency structures but how can one know if they are correct? Thus, one may conclude that one cannot evaluate the performance of a parser in other species, which, in turn, may lead one to conclude that accurately parsing the communication of other species is not viable\. Unsupervised parsing could be applied to other species but would only serve to speculate on the range of possible structures that other species may have\.

In spite of the considerations above, other primates produce sequences that are rather shortGustison et al\.\([2016](https://arxiv.org/html/2607.06542#bib.bib17)\);Girard\-Buttoz et al\.\([2022](https://arxiv.org/html/2607.06542#bib.bib13)\);Mielke et al\.\([2024a](https://arxiv.org/html/2607.06542#bib.bib32)\)and the distribution of sequence lengths decays exponentially across species \(e\.g\., geladas:Gustison et al\.\([2016](https://arxiv.org/html/2607.06542#bib.bib17)\); chimpanzees:Girard\-Buttoz et al\.\([2022](https://arxiv.org/html/2607.06542#bib.bib13)\)\)\. Here we apply recent advances in network scienceLondon and Pluhár\([2023](https://arxiv.org/html/2607.06542#bib.bib25)\)to demonstrate that the proportion of correct edges retrieved by a parser must be high for the sequences of vocalizations or gestures that non\-human primates produce due to the fast decay of the sequence length distribution\. In contrast, human language sentences lack that property\. Our core argument is as follows\. First, we neglect dependency direction leaving just edges without direction \(Figure[1](https://arxiv.org/html/2607.06542#S1.F1)\(c\)\), a common practice in the evaluation of unsupervised parsersMarecek\([2012](https://arxiv.org/html/2607.06542#bib.bib26)\);Han et al\.\([2020](https://arxiv.org/html/2607.06542#bib.bib18)\)\. Second, we consider a random parser for a sequence of lengthnnsuch thatn≥2n\\geq 2\. That parser selects the correct tree at random over all possible trees ofnnvertices\. We will show that the expected proportion of edges that are correctly identified by the random parser is2/n2/n\. Ifn=2n=2, the parser has100%100\\%maximum accuracy\. Ifn=3n=3, its expected accuracy is66%66\\%, ifn=4n=4then25%25\\%, … Therefore, if sequence lengths are biased towards low values, the random parser will have high accuracy\. Therefore, any good\-enough unsupervised parser, namely any parser theoretically able to improve over a random parser by exploiting the statistical structure of the sequencesMarecek\([2016](https://arxiv.org/html/2607.06542#bib.bib27)\);Han et al\.\([2020](https://arxiv.org/html/2607.06542#bib.bib18)\), will achieve an accuracy that is superior to that of the random parser\. Indeed, the sequences that non\-human apes produce have some statistical structureGustison et al\.\([2016](https://arxiv.org/html/2607.06542#bib.bib17)\);Gustison\([2017](https://arxiv.org/html/2607.06542#bib.bib16)\);Mielke et al\.\([2024a](https://arxiv.org/html/2607.06542#bib.bib32)\)\. Therefore, even if we do not have a gold standard, we will always be able to provide a lower bound to the accuracy of any good\-enough parser, and if sequence lengths are biased towards low values, we will be able to show that its performance must be high\.

Here we aim to show that the performance of a good\-enough parser on real\-world vocal or gestural sequences produced by non\-human primates is, indeed, expected to be high\. The remainder of the article is organized as follows\. Section[2](https://arxiv.org/html/2607.06542#S2)investigates the theoretical ability of a random parser to find the right tree or to identify edges correctly in a collection of sequences\. In particular, we present the expected value of the proportion of correct trees and the proportion of correct dependencies for three kinds of distribution of sequence lengths: the empirical distribution and two theoretical distributions, i\.e\. the uniform distribution and the geometric distribution\. The latter approximates the distribution of vocal sequence lengths that geladas and chimpanzees produceGustison et al\.\([2016](https://arxiv.org/html/2607.06542#bib.bib17)\);Girard\-Buttoz et al\.\([2022](https://arxiv.org/html/2607.06542#bib.bib13)\)\. Section[2](https://arxiv.org/html/2607.06542#S2)investigates the impact of the parameters of the theoretical distributions above and shows that the performance of the random parser is high when sequences are short but decays as the average length of the sequences decreases\. Section[3](https://arxiv.org/html/2607.06542#S3)presents the datasets from humans and other primates that will be used to obtain the empirical distribution of sequence lengths or key parameters \(e\.g\., the maximum sequence length\) of that distribution\. Such empirical distribution serves two purposes\. First, an accurate estimation of the performance estimation of the random parser\. Second, providing support for the geometric distribution as a theoretical model for the sequences that non\-human primates produce\.

Section[4](https://arxiv.org/html/2607.06542#S4)makes a series of contributions\. First, Section[4](https://arxiv.org/html/2607.06542#S4)compares the shape of the distribution of sequence lengths in chimpanzee vocal and gestural sequences versus sentences in humans\. It shows that only sequence lengths of chimpanzees can be approximated by a geometric distribution\. Second, it estimates a lower bound of the performance of a random parser in 31 species of non\-human primates\. Third, it also provides an accurate estimate of the performance of the random parser in geladas, chimpanzees, and humans\. The average proportion of correct edges retrieved per sequence by the random parser is51%51\\%for geladas and\>79%\>79\\%for chimpanzees\. If the analysis is restricted to sequences of more than two units, the performance drops to41%41\\%for geladas and to\>56%\>56\\%for chimpanzees\. In contrast, the accuracy of the random parser on human languages is about27%27\\%when restricted to sentences of length 10 and about13%13\\%for sentences of any length\. Finally, Section[5](https://arxiv.org/html/2607.06542#S5)concludes that evaluation without a gold standard is feasible in geladas and chimpanzees but hard in humans\. Section[5](https://arxiv.org/html/2607.06542#S5)also suggests that successful training of an unsupervised parser is likely for these species\.

## 2Theory

The performance of a parser can be evaluated in different ways\. First, by considering the direction of edges, as in Figure[1](https://arxiv.org/html/2607.06542#S1.F1)\(b\), or neglecting it as in Figure[1](https://arxiv.org/html/2607.06542#S1.F1)\(c\)Han et al\.\([2020](https://arxiv.org/html/2607.06542#bib.bib18)\)\. Here we disregard edge direction for simplicity and to avoid imposinga prioriany notion of hierarchy or rootness in the dependency structures that other species produceFrank and Christiansen\([2018](https://arxiv.org/html/2607.06542#bib.bib10)\)\. Therefore, our target is the free tree of the sequence\. Figure[1](https://arxiv.org/html/2607.06542#S1.F1)\(c\) shows the free tree of a sentence, that is obtained by removing link direction from the rooted tree \([1](https://arxiv.org/html/2607.06542#S1.F1)\(b\)\)\. Second, considering the number of correct trees retrieved \(hard evaluation\) or by considering the number of correct edges retrieved \(soft evaluation\)McDonald et al\.\([2005](https://arxiv.org/html/2607.06542#bib.bib30)\)\. Here we consider both aspects\.

### 2\.1Elementary definitions

Here we wish to evaluate the performance of a parser on a collection ofSSsequences\. We assume that each sequence has a single correct dependency structure, the default assumption for the syntactic dependency structure of human language sentences\. To simplify the analysis of the performance of the parser, we assume that the parser always retrieves a free tree when supplied a sequence\. The parser may produce directly a free treeYuret\([1998](https://arxiv.org/html/2607.06542#bib.bib44)\)or it may produce a rooted tree that is then transformed to a free treeHan et al\.\([2020](https://arxiv.org/html/2607.06542#bib.bib18)\)\. Certain parsing methods may produce more than one free tree given a sequence\. For instance, parsing methods that consist of extracting an optimal spanning tree from a graphGG, may retrieve more than one free tree when there are tied weights inGGMcDonald et al\.\([2005](https://arxiv.org/html/2607.06542#bib.bib30)\)\. If that happened, we assume that the parser eventually delivers just one of the tied trees chosen at random so as to simplify the theoretical analysis of the performance of that parser\. That way, one does not need to distinguish the precision of the parser from its recall because they become the same\.

We definenin\_\{i\}as the length of theii\-th sequence in a collection ofSSsequences\. In human languages, sequences can be made of words in spoken language or signs in sign languages\. In other species, these sequences can be made of vocalizationsMcCowan, Hanser, and Doyle\([1999](https://arxiv.org/html/2607.06542#bib.bib29)\);Girard\-Buttoz et al\.\([2022](https://arxiv.org/html/2607.06542#bib.bib13)\);Kershenbaum et al\.\([2016](https://arxiv.org/html/2607.06542#bib.bib21)\), gesturesLiebal, Call, and Tomasello\([2004](https://arxiv.org/html/2607.06542#bib.bib24)\);Hobaiter and Byrne\([2011](https://arxiv.org/html/2607.06542#bib.bib20)\);Mielke et al\.\([2024a](https://arxiv.org/html/2607.06542#bib.bib32)\)or other behavioral patternsAltmann\([1965](https://arxiv.org/html/2607.06542#bib.bib2)\);Ferrer\-i\-Cancho and Lusseau\([2006](https://arxiv.org/html/2607.06542#bib.bib8)\)\. Like humans, other species combine modalities when forming sequencesHobaiter, Byrne, and Zuberbühler\([2017](https://arxiv.org/html/2607.06542#bib.bib19)\);Mine et al\.\([2024](https://arxiv.org/html/2607.06542#bib.bib34)\)\.

The total number of tokens making the sequences is

T=∑i=1Sni,T=\\sum\_\{i=1\}^\{S\}n\_\{i\},wherenin\_\{i\}is the length \(number of elements\) of theii\-th sequence\. The sample of sequence lengths, i\.e\.

\{n1,n2,…,ni,…,nS\},\\\{n\_\{1\},n\_\{2\},\.\.\.,n\_\{i\},\.\.\.,n\_\{S\}\\\},\(1\)defines the empirical distribution of sequence lengths, which can be expressed compactly by means off​\(n\)f\(n\), the number of sequences of lengthnn\. Then

S\\displaystyle S=∑n=1nm​a​xf​\(n\)\\displaystyle=\\sum\_\{n=1\}^\{n\_\{max\}\}f\(n\)T\\displaystyle T=∑n=1nm​a​xn​f​\(n\),\\displaystyle=\\sum\_\{n=1\}^\{n\_\{max\}\}nf\(n\),wherenm​a​xn\_\{max\}is the maximum sequence length\.

We defineℱ\{\\cal F\}as the forest formed by the all the free trees that a parser has obtained for each of the sequences\. Such a forest hasTTvertices,m=T−Sm=T\-Sedges andSStrees\.

### 2\.2The evaluation scores

As for hard evaluation, we calculatePctP\_\{c\}^\{t\}, the fraction of correct trees inℱ\{\\cal F\}, that is

Pct=ScS,P\_\{c\}^\{t\}=\\frac\{S\_\{c\}\}\{S\},whereScS\_\{c\}is the number of correct trees inℱ\{\\cal F\}\. The subindexccstands for correct and the subindexttstands for trees\.PctP\_\{c\}^\{t\}is known as the complete metricMcDonald et al\.\([2005](https://arxiv.org/html/2607.06542#bib.bib30)\)\. As for soft evaluation, we calculatePceP\_\{c\}^\{e\}, the fraction of correct edges inℱ\{\\cal F\}, that is

Pce=mcm,P\_\{c\}^\{e\}=\\frac\{m\_\{c\}\}\{m\},wheremcm\_\{c\}is the number of edges inℱ\{\\cal F\}that are correct\. The subindexccstands again for correct and the subindexeestands for edges\.PceP\_\{c\}^\{e\}corresponds to the so\-called undirected dependency accuracyKlein and Manning\([2004](https://arxiv.org/html/2607.06542#bib.bib23)\);Han et al\.\([2020](https://arxiv.org/html/2607.06542#bib.bib18)\)\.PceP\_\{c\}^\{e\}is equivalent to the precision and recall of a parser on retrieving correct dependencies\.

The ability of the parser to find correct edges can also be evaluated by means of the local performance of the parser on individual sequences\. To that aim, we define,Pc,ieP\_\{c,i\}^\{e\}as the proportion of correct edges for theii\-th tree ofℱ\{\\cal F\}\. We assume thatnm​i​n\>1n\_\{min\}\>1so thatPceP\_\{c\}^\{e\}is defined on individual trees\.QQ, the average value ofPc,ieP\_\{c,i\}^\{e\}over all sequences is

Q=1S​\(nm​i​n\)​∑i=1ni≥nm​i​nSPc,ie\.Q=\\frac\{1\}\{S\(n\_\{min\}\)\}\\sum\_\{\\begin\{subarray\}\{c\}i=1\\\\ n\_\{i\}\\geq n\_\{min\}\\end\{subarray\}\}^\{S\}P\_\{c,i\}^\{e\}\.\\\\We adopt the convention thatPce=1P\_\{c\}^\{e\}=1whenn=1n=1andPc,ie=1P\_\{c,i\}^\{e\}=1whenni=1n\_\{i\}=1\.

We usennto refer to the length of a sequence\. Sequences can be of length one or greater but up ton=2n=2if it is impossible for a parser to make a mistake\. Whenn=1n=1the structure is empty and whenn=2n=2the structure must link the only two vertices\. For that reason, the evaluation scores will have a parameternm​i​nn\_\{min\}that defines the minimum sentence length taken into account\. We defineS​\(nm​i​n\)S\(n\_\{min\}\)as the number of sequences of lengthnm​i​nn\_\{min\}or greater \(S=S​\(1\)S=S\(1\)\)\. Accordingly,PctP\_\{c\}^\{t\}is refined as

Pct=Sc​\(nm​i​n\)S​\(nm​i​n\),P\_\{c\}^\{t\}=\\frac\{S\_\{c\}\(n\_\{min\}\)\}\{S\(n\_\{min\}\)\},\(2\)where

Sc​\(nm​i​n\)\\displaystyle S\_\{c\}\(n\_\{min\}\)=∑i=1ni≥nm​i​nSci\\displaystyle=\\sum\_\{\\begin\{subarray\}\{c\}i=1\\\\ n\_\{i\}\\geq n\_\{min\}\\end\{subarray\}\}^\{S\}c\_\{i\}\(3\)andcic\_\{i\}is a binary variable that indicates if the parse for theii\-th sequence is correct \(ci=1c\_\{i\}=1if correct;ci=0c\_\{i\}=0otherwise\)\.

We definemc,im\_\{c,i\}as the number of correct edges retrieved for theii\-th sequence\. ThenPceP\_\{c\}^\{e\}is refined as

Pce=mc​\(nm​i​n\)m​\(nm​i​n\),P\_\{c\}^\{e\}=\\frac\{m\_\{c\}\(n\_\{min\}\)\}\{m\(n\_\{min\}\)\},\(4\)where

mc​\(nm​i​n\)\\displaystyle m\_\{c\}\(n\_\{min\}\)=∑i=1ni≥nm​i​nSmc,i\\displaystyle=\\sum\_\{\\begin\{subarray\}\{c\}i=1\\\\ n\_\{i\}\\geq n\_\{min\}\\end\{subarray\}\}^\{S\}m\_\{c,i\}\(5\)m​\(nm​i​n\)\\displaystyle m\(n\_\{min\}\)=∑i=1ni≥nm​i​nS\(ni−1\)\\displaystyle=\\sum\_\{\\begin\{subarray\}\{c\}i=1\\\\ n\_\{i\}\\geq n\_\{min\}\\end\{subarray\}\}^\{S\}\(n\_\{i\}\-1\)\(6\)=∑n=nm​i​nnm​a​xf​\(n\)​\(n−1\)\.\\displaystyle=\\sum\_\{n=n\_\{min\}\}^\{n\_\{max\}\}f\(n\)\(n\-1\)\.

### 2\.3The expected value of the evaluation scores

In order to be maximally agnostic about what we do not know, we assume all labeled trees of the same size have the same probability of being the correct tree\. We are interested in the expected value of the evaluation scores in two settings: \(a\) given onlyS​\(nm​i​n\)S\(n\_\{min\}\)and the theoretical distribution of sequence lengths, namely their theoretical distribution is given and \(b\) given the empirical distribution of sequences lengths, namely the sample of sequence lengths \(equation[1](https://arxiv.org/html/2607.06542#S2.E1)\), orf​\(n\)f\(n\)\.

As for \(a\), we assume that thenin\_\{i\}’s are identically distributed and definep​\(n\)p\(n\)as the probability that a sequence of the collection has lengthnn\. We are interested in two single\-parameter distributions\. First, a uniform distribution with parameternm​a​xn\_\{max\}, i\.e\.

p​\(n\)=\{1nm​a​xif​1≤n≤nm​a​x\.0otherwise\.p\(n\)=\\left\\\{\\begin\{array\}\[\]\{ll\}\\frac\{1\}\{n\_\{max\}\}&\\mbox\{if \}1\\leq n\\leq n\_\{max\}\.\\\\ 0&\\mbox\{otherwise\}\.\\end\{array\}\\right\.\(7\)Second, a geometric distribution with parameterqq, i\.e\.

p​\(n\)=\{q​\(1−q\)n−1if​n≥10otherwise\.p\(n\)=\\left\\\{\\begin\{array\}\[\]\{ll\}q\(1\-q\)^\{n\-1\}&\\mbox\{if \}n\\geq 1\\\\ 0&\\mbox\{otherwise\}\.\\end\{array\}\\right\.\(8\)The uniform distribution serves as a baseline for any non\-increasing distribution, e\.g\., the geometric distribution withq\>0q\>0, which is specially useful for species where only the maximum sequence length is reportedGirard\-Buttoz et al\.\([2022](https://arxiv.org/html/2607.06542#bib.bib13)\)\. The choice of the geometric distribution is motivated by direct evidence in gelada vocalizationsGustison et al\.\([2016](https://arxiv.org/html/2607.06542#bib.bib17)\)and indirect evidence in chimpanzee vocalizationsGirard\-Buttoz et al\.\([2022](https://arxiv.org/html/2607.06542#bib.bib13)\)\.111Girard\-Buttoz et al\.\([2022](https://arxiv.org/html/2607.06542#bib.bib13)\)does not check explicitly if the distribution is geometric asGustison et al\.\([2016](https://arxiv.org/html/2607.06542#bib.bib17)\)but in Figure 1 of their article they show a linear decay in linear\-log scale that can be approximated by a geometric distribution\.

p​\(n\|n≥nm​i​n\)p\(n\|n\\geq n\_\{min\}\)is the probability that a sequence has lengthnnamong sequences of lengthnm​i​nn\_\{min\}or greater\. For the uniform distribution, one obtains a uniform distribution in the integer interval\[nm​i​n,nm​a​x\]\[n\_\{min\},n\_\{max\}\], i\.e\.

p​\(n\|n≥nm​i​n\)=1nm​a​x−nm​i​n\+1\.p\(n\|n\\geq n\_\{min\}\)=\\frac\{1\}\{n\_\{max\}\-n\_\{min\}\+1\}\.\(9\)For the geometric distribution, one obtains the well\-known displaced geometric distributionPark and Wang\([2023](https://arxiv.org/html/2607.06542#bib.bib36)\)

p​\(n\|n≥nm​i​n\)=\{q​\(1−q\)n−nm​i​nif​n≥nm​i​n0otherwise\.p\(n\|n\\geq n\_\{min\}\)=\\left\\\{\\begin\{array\}\[\]\{ll\}q\(1\-q\)^\{n\-n\_\{min\}\}&\\mbox\{if \}n\\geq n\_\{min\}\\\\ 0&\\mbox\{otherwise\}\.\\end\{array\}\\right\.\(10\)Finally, for the empirical distribution,

p​\(n\|n≥nm​i​n\)=f​\(n\)S​\(nm​i​n\)\.p\(n\|n\\geq n\_\{min\}\)=\\frac\{f\(n\)\}\{S\(n\_\{min\}\)\}\.\(11\)
Suppose a function ofϕ​\(n\)\\phi\(n\)\. We define the expectation ofϕ\\phias

𝔼⁡\[ϕ​\(n\)\]=∑n=nm​i​nνm​a​xp​\(n\|n≥nm​i​n\)​ϕ​\(n\)\.\\operatorname\{\\mathbb\{E\}\}\[\\phi\(n\)\]=\\sum\_\{n=n\_\{min\}\}^\{\\nu\_\{max\}\}p\(n\|n\\geq n\_\{min\}\)\\phi\(n\)\.\(12\)νm​a​x=∞\\nu\_\{max\}=\\inftyfor the geometric distribution andνm​a​x=nm​a​x\\nu\_\{max\}=n\_\{max\}for the uniform or the empirical distribution\.

We analyze the ability of the random parser to find the correct tree by means of𝔼⁡\[Pct\]\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{t\}\], the expected value ofPctP\_\{c\}^\{t\}\. The expected proportion of correct trees produced by the random parser is \(Appendix[5\.3](https://arxiv.org/html/2607.06542#S5.SS3)\)

𝔼⁡\[Pct\]=𝔼⁡\[n2−n\]\.\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{t\}\]=\\operatorname\{\\mathbb\{E\}\}\[n^\{2\-n\}\]\.\(13\)We analyze the ability of the random parser to retrieve correct dependencies by means of𝔼⁡\[Q\]\\operatorname\{\\mathbb\{E\}\}\[Q\]and𝔼⁡\[Pce\]\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{e\}\], the expected value ofPceP\_\{c\}^\{e\}andQQ, respectively\. The expected average proportion of correct edges over sequences of same length produced by the random parser is \(Appendix[5\.3](https://arxiv.org/html/2607.06542#S5.SS3)\)

𝔼⁡\[Q\]=2​𝔼⁡\[1n\]\\operatorname\{\\mathbb\{E\}\}\[Q\]=2\\operatorname\{\\mathbb\{E\}\}\\left\[\\frac\{1\}\{n\}\\right\]\(14\)while the expected overall proportion of correct edges produced by the random parser is \(Appendix[5\.3](https://arxiv.org/html/2607.06542#S5.SS3)\)

𝔼⁡\[Pce\]=2​S​\(nm​i​n\)m​\(nm​i​n\)​𝔼⁡\[1−1n\]\.\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{e\}\]=\\frac\{2S\(n\_\{min\}\)\}\{m\(n\_\{min\}\)\}\\operatorname\{\\mathbb\{E\}\}\\left\[1\-\\frac\{1\}\{n\}\\right\]\.\(15\)
Trivially,

𝔼⁡\[Q\]≥𝔼⁡\[Pct\]\.\\operatorname\{\\mathbb\{E\}\}\[Q\]\\geq\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{t\}\]\.\(16\)Notice𝔼⁡\[Q\]=𝔼⁡\[2/n\]≥𝔼⁡\[Pct\]=𝔼⁡\[n2−n\]\\operatorname\{\\mathbb\{E\}\}\[Q\]=\\operatorname\{\\mathbb\{E\}\}\[2/n\]\\geq\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{t\}\]=\\operatorname\{\\mathbb\{E\}\}\[n^\{2\-n\}\]sincen3−n≤2n^\{3\-n\}\\leq 2forn≥1n\\geq 1\)\. Besides,𝔼⁡\[Pce\]\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{e\}\]and𝔼⁡\[Q\]\\operatorname\{\\mathbb\{E\}\}\[Q\]are directly related, since

𝔼⁡\[Pce\]\\displaystyle\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{e\}\]=S​\(nm​i​n\)m​\(nm​i​n\)​\(2−2​𝔼⁡\[1n\]\)​\(expanding Eq\.[15](https://arxiv.org/html/2607.06542#S2.E15)\)\\displaystyle=\\frac\{S\(n\_\{min\}\)\}\{m\(n\_\{min\}\)\}\\left\(2\-2\\operatorname\{\\mathbb\{E\}\}\\left\[\\frac\{1\}\{n\}\\right\]\\right\)\\mbox\{~~~\(expanding Eq\. \\ref\{eq:expected\_proportion\_of\_intersecting\_edges\_over\_edges\_main\}\)\}=S​\(nm​i​n\)m​\(nm​i​n\)​\(2−𝔼⁡\[Q\]\)\\displaystyle=\\frac\{S\(n\_\{min\}\)\}\{m\(n\_\{min\}\)\}\\left\(2\-\\operatorname\{\\mathbb\{E\}\}\[Q\]\\right\)\(17\)
The condition𝔼⁡\[Q\]≥𝔼⁡\[Pce\]\\operatorname\{\\mathbb\{E\}\}\[Q\]\\geq\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{e\}\]becomes

𝔼⁡\[Q\]\\displaystyle\\operatorname\{\\mathbb\{E\}\}\[Q\]≥2​S​\(nm​i​n\)S​\(nm​i​n\)\+m​\(nm​i​n\)\\displaystyle\\geq\\frac\{2S\(n\_\{min\}\)\}\{S\(n\_\{min\}\)\+m\(n\_\{min\}\)\}=2​S​\(nm​i​n\)S​\(nm​i​n\)\+T​\(nm​i​n\)−S​\(nm​i​n\)\\displaystyle=\\frac\{2S\(n\_\{min\}\)\}\{S\(n\_\{min\}\)\+T\(n\_\{min\}\)\-S\(n\_\{min\}\)\}=2​S​\(nm​i​n\)T​\(nm​i​n\)=𝔼\[Q\]∗\.\\displaystyle=\\frac\{2S\(n\_\{min\}\)\}\{T\(n\_\{min\}\)\}=\\operatorname\{\\mathbb\{E\}\}\[Q\]\_\{\*\}\.\(19\)

### 2\.4A generalization

𝔼⁡\[Pct\]\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{t\}\],𝔼⁡\[Q\]\\operatorname\{\\mathbb\{E\}\}\[Q\],𝔼⁡\[Pce\]\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{e\}\]are particular cases of a general definition of an evaluation score

K=c​𝔼⁡\[ϕ​\(n\)\],K=c\\operatorname\{\\mathbb\{E\}\}\[\\phi\(n\)\],\(20\)where𝔼⁡\[ϕ​\(n\)\]\\operatorname\{\\mathbb\{E\}\}\[\\phi\(n\)\]is defined as in Eq\.[12](https://arxiv.org/html/2607.06542#S2.E12)\.𝔼⁡\[Pct\]\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{t\}\]is obtained with

c\\displaystyle c=1\\displaystyle=1ϕ​\(n\)\\displaystyle\\phi\(n\)=n2−n\.\\displaystyle=n^\{2\-n\}\.𝔼⁡\[Q\]\\operatorname\{\\mathbb\{E\}\}\[Q\]is obtained with

c\\displaystyle c=2\\displaystyle=2ϕ​\(n\)\\displaystyle\\phi\(n\)=1n\.\\displaystyle=\\frac\{1\}\{n\}\.𝔼⁡\[Pce\]\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{e\}\]is obtained with

c\\displaystyle c=2​S​\(nm​i​n\)m​\(nm​i​n\)\\displaystyle=\\frac\{2S\(n\_\{min\}\)\}\{m\(n\_\{min\}\)\}ϕ​\(n\)\\displaystyle\\phi\(n\)=1−1n\.\\displaystyle=1\-\\frac\{1\}\{n\}\.

### 2\.5The calculation of the theoretical performance of the random parser

For simplicity, we calculate𝔼⁡\[Pce\]\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{e\}\]from𝔼⁡\[Q\]\\operatorname\{\\mathbb\{E\}\}\[Q\]applying Eq\.[17](https://arxiv.org/html/2607.06542#S2.E17)\.

To calculate𝔼⁡\[Pct\]\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{t\}\]and𝔼⁡\[Q\]\\operatorname\{\\mathbb\{E\}\}\[Q\], we apply the definition ofKK\(Eq\.[20](https://arxiv.org/html/2607.06542#S2.E20)\)\.KKis easy to compute numerically if the distribution of sequences lengths is the uniform or the empirical distribution because the summation in the definition ofKK\(Eq\.[12](https://arxiv.org/html/2607.06542#S2.E12)\) has a finite number of summands\. It suffices to plug the definition of the uniform distribution \(Eq\.[9](https://arxiv.org/html/2607.06542#S2.E9)\) or that of the empirical distribution \(Eq\.[11](https://arxiv.org/html/2607.06542#S2.E11)\) into Eq\.[12](https://arxiv.org/html/2607.06542#S2.E12)\.

If the distribution is the geometric, the number of summands is infinite, and then two approaches are possible\. First, a high\-quality approximation based onKKthat is explained in Appendix[6](https://arxiv.org/html/2607.06542#A0.F6)\. The method has a parameterϵ\\epsilonthat is the approximation error\. In this article, we useϵ=10−8\\epsilon=10^\{\-8\}\. Second, a specific analytical solution for𝔼⁡\[Q\]=2​𝔼⁡\[1/n\]\\operatorname\{\\mathbb\{E\}\}\[Q\]=2\\operatorname\{\\mathbb\{E\}\}\[1/n\]that consists of replacing𝔼⁡\[1/n\]\\operatorname\{\\mathbb\{E\}\}\[1/n\]by an exact formula in Property[5\.3](https://arxiv.org/html/2607.06542#S5.SS3)\. As a complement, Property[5\.3](https://arxiv.org/html/2607.06542#S5.SS3)also gives an exact formula for the uniform distribution\.

### 2\.6The theoretical performance of the random parser

We wish to explore the performance of the random parser on the theoretical distributions\. To find a common ground for the two distributions, we use⟨n⟩\\left<n\\right\>, the expected sequence length\. For the uniform distribution \(Eq\.[9](https://arxiv.org/html/2607.06542#S2.E9)\),

⟨n⟩=\(1\+nm​a​x\)/2\.\\left<n\\right\>=\(1\+n\_\{max\}\)/2\.For the 1\-parameter geometric distribution \(Eq\.[7](https://arxiv.org/html/2607.06542#S2.E7)\),⟨n⟩=1/q\\left<n\\right\>=1/q\. The performance decreases as the mean sequence length decreases for both distributions \(Fig\.[2](https://arxiv.org/html/2607.06542#S2.F2)and[3](https://arxiv.org/html/2607.06542#S2.F3)\)\. For sufficiently long sequences, the decay is power\-law like given the appearance of a straight line in double logarithmic scale\. That is

𝔼⁡\[Pct\],𝔼⁡\[Q\],𝔼⁡\[Pce\]∼⟨n⟩−α,\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{t\}\],\\operatorname\{\\mathbb\{E\}\}\[Q\],\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{e\}\]\\sim\\left<n\\right\>^\{\-\\alpha\},whereα\\alphais some positive constant\. See Appendix[5\.3](https://arxiv.org/html/2607.06542#S5.SS3)for the performance of the random parser as direct function of the parameter of the uniform and the geometric distribution\.

![Refer to caption](https://arxiv.org/html/2607.06542v1/x2.png)Figure 2:The performance of a random parser as a function of the expected sequence length⟨n⟩\\left<n\\right\>when sequence length follows a uniform distribution in the interval\[1,nm​a​x\]\[1,n\_\{max\}\]\(Eq\.[9](https://arxiv.org/html/2607.06542#S2.E9)\)\. Three performance scores are considered:𝔼⁡\[Pct\]\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{t\}\], the expected proportion of correct trees \(top\),𝔼⁡\[Q\]\\operatorname\{\\mathbb\{E\}\}\[Q\], the average expected proportion of correct edges per sequence \(middle\) and𝔼⁡\[Pce\]\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{e\}\], the expected overall proportion of correct edges \(bottom\)\. On top each subfigure,nm​i​nn\_\{min\}indicates the minimum sequence length considered to measure the performance of the parser\.![Refer to caption](https://arxiv.org/html/2607.06542v1/x3.png)Figure 3:The performance of a random parser as a function of the expected sequence length⟨n⟩\\left<n\\right\>when sequence length follows a 1\-parameter geometric distribution \(Eq\.[8](https://arxiv.org/html/2607.06542#S2.E8)\)\. The format is the same as in Fig\.[2](https://arxiv.org/html/2607.06542#S2.F2)\.

## 3Methods

### 3\.1Non\-human primates sequences

We borrow the maximum sequence length information on 31 species of primates \(Table[2](https://arxiv.org/html/2607.06542#S3.T2)\) fromGirard\-Buttoz et al\.\([2022](https://arxiv.org/html/2607.06542#bib.bib13)\)\. We borrow the empirical sequence length distribution from previous work:

- •Vocal sequences produced by male geladas fromGustison et al\.\([2016](https://arxiv.org/html/2607.06542#bib.bib17), Figure S2\)\.
- •Chimpanzee vocal sequences from the data displayed in Figure 1 ofGirard\-Buttoz et al\.\([2022](https://arxiv.org/html/2607.06542#bib.bib13)\)That data is available as Supplementary Data 2 fromGirard\-Buttoz et al\.\([2022](https://arxiv.org/html/2607.06542#bib.bib13)\)\. For simplicity, we consider all calls, independently of the sex of the vocalizer and we combine the counts for unpanted calls \(calls emitted individually\) and counts for panted calls \(calls interspersed with voiced inhalations\) to obtain a single count for sequences of length 1\.
- •Chimpanzee gestural sequences from the counts displayed in Table 1 ofMielke et al\.\([2024a](https://arxiv.org/html/2607.06542#bib.bib32)\)\. Each gesture action has a clearly defined Minimum Action Unit \(MAU\) based on the minimum information necessary to distinguish between gesture actions, starting from the moment the individual moves the body part \(or articulator\) and finishing when the gesture action is fully in placeGrund et al\.\([2023](https://arxiv.org/html/2607.06542#bib.bib14)\)\. Unlike vocalizations, which are restricted to being produced one at a time, two or more gesture tokens can be overlapped\. ThusMielke et al\.\([2024a](https://arxiv.org/html/2607.06542#bib.bib32)\)employed four criteria to define a sequence \(from broader to more restrictive\): 5 seconds \(gestures that started within 5 seconds after the end of the MAU of the previous unit were considered to be in the same sequence\), rapid\-fire sequences \(gestures that started within 1 second after the end of the MAU of the previous unit considered to be in the same sequence\), overlap \(only gestures that occurred with overlap of their MAU considered to be in the same sequence\) and solitary gestures\-plus waiting \(gestures that were separated by at least one second, but occurred within the same 5 second window considered to be in the same sequence\)\.

The statistical properties of these distributions are summarized in Table[3\.1](https://arxiv.org/html/2607.06542#S3.SS1)\.

Table 1:For each kind of sequence \(modality and criterion\), we show the sequence length \(SS\), the total number of tokens \(TT\), the maximum sequence length \(lm​a​xl\_\{max\}\), the average sequence length \(⟨n⟩\\left<n\\right\>\) and the frequency of sequences of specific length\.f​\(n\)f\(n\)is the number of sequences of lengthnnandf≥​\(n\)f\_\{\\geq\}\(n\)is the number of sequences of lengthnnor greater\.Table 2:The 31 species of primates sorted bynm​a​xn\_\{max\}the maximum sequence length\. Extracted fromGirard\-Buttoz et al\.\([2022](https://arxiv.org/html/2607.06542#bib.bib13), Supplementary Data 2\)\. In the taxa field, A\-E stands for Afro\-Eurasian and A for American \(Afro\-Eurasian and American are modern replacements for the labels Old World and New World\)\. In the ‘Singing’ column, ’yes’ indicates a singing species while ’no’ indicates a non\-singing species followingGirard\-Buttoz et al\.\([2022](https://arxiv.org/html/2607.06542#bib.bib13)\)\.
### 3\.2Human language sequences

The standard for the evaluation of unsupervised parsing in computational linguistics is WSJ10, a subset of the Wall Street Journal \(WSJ\) corpus comprising sentences of at most 10 non\-punctuation wordsHan et al\.\([2020](https://arxiv.org/html/2607.06542#bib.bib18)\);Søgaard\([2011](https://arxiv.org/html/2607.06542#bib.bib40)\)\. However, the language of WSJ is English which is a single a WEIRD language from the Indo\-European familyBlasi et al\.\([2022](https://arxiv.org/html/2607.06542#bib.bib3)\)\. To reach more generalizable conclusions, we need a sample of languages from distinct families that is fully parallel so that we do not need to control for the content of the texts and other characteristics\. For this reason, we use Parallel Universal Dependencies \(PUD\), a parallel collection of syntactic dependency treebanks that is a subset of the Universal Dependencies \(UD\) collectionZeman et al\.\([2020](https://arxiv.org/html/2607.06542#bib.bib45)\)\. We extract PUD from UD 2\.18, which leads to a sample of languages 21 languages from 9 linguistic families \(Table[3](https://arxiv.org/html/2607.06542#S3.T3)\)\. Following the analogy of WSJ10, we define PUD10 as the subset of PUD comprising sentences of at most 10 non\-punctuation words\. To control for the effect of syntactic annotation style, we consider the UD style, i\.e\. the original annotation style of the UD collection, as well as a competing style, i\.e\. Surface\-syntactic Universal Dependencies \(SUD\)Gerdes et al\.\([2018](https://arxiv.org/html/2607.06542#bib.bib12)\)\.

We borrow the preprocessing methods from previous research on parallel dependency treebanksFerrer\-i\-Cancho et al\.\([2022](https://arxiv.org/html/2607.06542#bib.bib7)\);Alemany\-Puig and Ferrer\-i\-Cancho\([2024](https://arxiv.org/html/2607.06542#bib.bib1)\)\. The main features of the processing are that nodes that are punctuation marks are removed and that the corpus remains fully parallel after the removalFerrer\-i\-Cancho et al\.\([2022](https://arxiv.org/html/2607.06542#bib.bib7)\)\. The preprocessed data is freely available the ancillary materials of the Linear Arrangement Library website at[https://cqllab\.upc\.edu/lal/universal\-dependencies/](https://cqllab.upc.edu/lal/universal-dependencies/)as PUD 2\.18 for UD style and PSUD 2\.18 for SUD style\. In these preprocessed treebanks, the minimum sequence length in isn=2n=2because the syntactic dependency structures is empty forn<2n<2and sentences withn<2n<2are discarded\. After preprocessing, the empirical length distribution in UD style is the same as that of SUD style for each language\. For this reason, we discard SUD style\.

Table 3:The languages in the PUD collection grouped by linguistic family\.## 4Results

### 4\.1Empirical sequence length distribution

We examinep​\(n\)p\(n\), the proportion of sequence of lengthnn\. The goal is to further motivate the theoretical assumptions aboutp​\(n\)p\(n\)that we follow in subsequent analyses\. Finding the best model forp​\(n\)p\(n\)is beyond the scope of the current article\.

![Refer to caption](https://arxiv.org/html/2607.06542v1/x4.png)Figure 4:The empirical distribution of sequence lengths \(solid line\) in sequences produced by geladas and chimpanzees\. On top each subfigure, the name of the species, the modality and the criterion that defines the sequences is indicated\. The dotted line shows the best fit of a 2\-parameter geometric distribution \(Eq\.[10](https://arxiv.org/html/2607.06542#S2.E10)\) with parametersnm​i​n=1n\_\{min\}=1andq=\(S−1\)/S⟨n⟩−1/Sq=\\frac\{\(S\-1\)/S\}\{\\left<n\\right\>\-1/S\}whereSSis the number of sequences and⟨n⟩\\left<n\\right\>is the average sequence length \(Appendix[5\.3](https://arxiv.org/html/2607.06542#S5.SS3)\)\.In chimpanzees,p​\(n\)p\(n\)shows a linear decay when logarithmic scale is applied top​\(n\)p\(n\)that is consistent with an exponential function \(Figure[4](https://arxiv.org/html/2607.06542#S4.F4)\)\. In vocal sequences, a 1\-parameter geometric distribution \(Eq\.[8](https://arxiv.org/html/2607.06542#S2.E8)\) gives a visual fit of high quality for the whole range of lengths for geladas and chimpanzees\. In gestural sequences \(chimpanzees\), a 1\-parameter geometric distribution fits only small lengths up to a breakpoint, that is the start of another exponential regime with a slower decay\. That is the hallmark of the two\-regime exponential distribution that has been found in the distance between syntactically related words in sentencesPetrini and Ferrer\-i\-Cancho\([2025](https://arxiv.org/html/2607.06542#bib.bib37)\)and also in the distance traversed by foraging antsCampos et al\.\([2016](https://arxiv.org/html/2607.06542#bib.bib4)\)\. The relevant conclusions of this qualitative analysis are that, in chimpanzees,

1. 1\.Sequence length distributions exhibit a non\-increasing trend\. The mode isn=1n=1andp​\(n\)p\(n\)tends to decrease or remain the same asnnincreases\.
2. 2\.The 1\-parameter geometric distribution yields a good approximation in vocal sequences and a lower bound to the actual decay in gestural sequences\.

These conclusions are in contrast with the distribution of sequence lengths in human languages, where

1. 1\.Sequence length distributions exhibit an inverted\-V shape \(an initial increasing trend is followed by a decreasing trend\)\. The mode is far fromn=1n=1Sigurd, Eeg\-Olofsson, and van Weijer\([2004](https://arxiv.org/html/2607.06542#bib.bib39)\);Furuhashi and Hayakawa\([2012](https://arxiv.org/html/2607.06542#bib.bib11)\)\.
2. 2\.The geometric distribution yields a poor approximation since it is incompatible with an inverted\-V shape\. The log\-normal distribution is often selected as an approximation to the distribution of sentence lengthsFuruhashi and Hayakawa\([2012](https://arxiv.org/html/2607.06542#bib.bib11)\)\.

These characteristics are also found in PUD \(Appendix[6](https://arxiv.org/html/2607.06542#A0.F6)\)\.

### 4\.2Performance on primate sequences

Table[2](https://arxiv.org/html/2607.06542#S3.T2)shows that, among the 31 species of primates reviewed byGirard\-Buttoz et al\.\([2022](https://arxiv.org/html/2607.06542#bib.bib13)\), the number of species for each value ofnm​a​xn\_\{max\}is as follows: 2 \(13 species\), 3 \(12 species\), 4 \(1 species\), 5 \(2 species\), 8 \(1 species\) and 13 \(1 species\)\.

We do not know the actual distribution of sequence lengths in the majority of these species, but if we assume that the distribution is non\-increasing \(recall Section[4\.1](https://arxiv.org/html/2607.06542#S4.SS1)and Figure[4](https://arxiv.org/html/2607.06542#S4.F4)\), we can then use a uniform distribution to get a lower bound of the performance of a random parser \(Table[4\.2](https://arxiv.org/html/2607.06542#S4.SS2)\)\. Whennm​a​x≤2n\_\{max\}\\leq 2the performance of the random parser is trivially100%100\\%\(𝔼⁡\[Pct\]=𝔼⁡\[Q\]=𝔼⁡\[Pce\]=1\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{t\}\]=\\operatorname\{\\mathbb\{E\}\}\[Q\]=\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{e\}\]=1\)\. Whennm​a​x=3n\_\{max\}=3, the proportion of correctly guessed edges is about80%80\\%if the performance is evaluated on sequences of length22or greater \(𝔼⁡\[Q\]=0\.83\\operatorname\{\\mathbb\{E\}\}\[Q\]=0\.83and𝔼⁡\[Pce\]=0\.77\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{e\}\]=0\.77\); the proportion of correctly guessed edges is nearly70%70\\%if the performance is evaluated on sequences of length33or greater \(𝔼⁡\[Q\]=𝔼⁡\[Pce\]=0\.67\\operatorname\{\\mathbb\{E\}\}\[Q\]=\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{e\}\]=0\.67\)\.

Table 4:A lower bound to the performance of the random parser assuming that the distribution of sequence lengths is non\-increasing\.nm​i​nn\_\{min\}is the minimum sequence length considered when measuring the performance of the random parser\.nm​a​xn\_\{max\}is the maximum sequence length\. Only the values ofnm​a​xn\_\{max\}reported byGirard\-Buttoz et al\.\([2022](https://arxiv.org/html/2607.06542#bib.bib13)\)on an ensemble of 31 primate species are shown \(Table[2](https://arxiv.org/html/2607.06542#S3.T2)\)\.Now we examine the performance of the random parser when further information about the distribution of sequence lengths in humans, geladas and chimpanzees\. In all our analyses, we find \(Table[4\.2](https://arxiv.org/html/2607.06542#S4.SS2), Table[4\.2](https://arxiv.org/html/2607.06542#S4.SS2)and Table[5\.3](https://arxiv.org/html/2607.06542#S5.SS3)\)

1. 1\.𝔼⁡\[Q\]≥𝔼⁡\[Pct\]\\operatorname\{\\mathbb\{E\}\}\[Q\]\\geq\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{t\}\]as theoretically expected \(Section[2](https://arxiv.org/html/2607.06542#S2)\)\.
2. 2\.𝔼⁡\[Q\]≥𝔼⁡\[Pce\]\\operatorname\{\\mathbb\{E\}\}\[Q\]\\geq\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{e\}\]for the empirical distribution because the actual𝔼⁡\[Q\]\\operatorname\{\\mathbb\{E\}\}\[Q\]is large enough, namely𝔼\[Q\]∗\\operatorname\{\\mathbb\{E\}\}\[Q\]\_\{\*\}\(Eq\.[19](https://arxiv.org/html/2607.06542#S2.E19)\) never exceeds𝔼⁡\[Q\]\\operatorname\{\\mathbb\{E\}\}\[Q\]\.

In geladas and chimpanzees, the performance of the random parser drops as the minimum sentence length for evaluation increases from 2 to 3 \(TablesLABEL:tab:performance\_by\_scoreand[4\.2](https://arxiv.org/html/2607.06542#S4.SS2)\)\. The values of𝔼⁡\[Pct\]\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{t\}\]are lower than the corresponding values of the other scores \(𝔼⁡\[Q\]\\operatorname\{\\mathbb\{E\}\}\[Q\]as expected theoretically \(Eq\.[16](https://arxiv.org/html/2607.06542#S2.E16)\) but also those of𝔼⁡\[Pce\]\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{e\}\]\)\. These findings are consistent with the intuition that guessing the right tree is more difficult than guessing the right edges \(TableLABEL:tab:performance\_by\_score\)\. As expected from the geometric\-like distribution of sequence lengths in primates \(Section[4\.1](https://arxiv.org/html/2607.06542#S4.SS1)\), the performance of the random parser assuming a 1\-parameter geometric distribution for sentence lengths yields a better estimate of the actual performance of the parser than a uniform distribution \(Table[4\.2](https://arxiv.org/html/2607.06542#S4.SS2)\)\. The average proportion of correct edges per sequence \(𝔼⁡\[Q\]\\operatorname\{\\mathbb\{E\}\}\[Q\]\) in sequences of two or more units is51%51\\%for geladas,79%79\\%for chimpanzee vocalizations and\>84%\>84\\%for chimpanzee gestures\. Settingnm​i​n≥3n\_\{min\}\\geq 3to exclude sequences where no error is possible, the average proportion drops to41%41\\%for geladas,57%57\\%for chimpanzee vocalizations and\>56%\>56\\%for chimpanzee gestures\.

The performance of the random parser on human languages on sentences of up to 10 words is much worse than in geladas and chimpanzees \(Table[4\.2](https://arxiv.org/html/2607.06542#S4.SS2)and Table[4\.2](https://arxiv.org/html/2607.06542#S4.SS2)\. The expected proportion of correct edges per sequence \(𝔼⁡\[Q\]\\operatorname\{\\mathbb\{E\}\}\[Q\]\) in sequences of two or more units in languages is28%28\\%on average fornm​i​n=2n\_\{min\}=2and also fornm​i​n=3n\_\{min\}=3\. Not surprisingly, the performance of the random parser on human languages is even worse if no limit is imposed on sentence length \(Appendix[7](https://arxiv.org/html/2607.06542#A0.F7)\)\. The expected proportion of correct edges per sequence in languages drops to13%13\\%on average fornm​i​n=2n\_\{min\}=2and also fornm​i​n=3n\_\{min\}=3\.

Table 6:The performance scores𝔼⁡\[Pct\]\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{t\}\],𝔼⁡\[Q\]\\operatorname\{\\mathbb\{E\}\}\[Q\],𝔼⁡\[Pce\]\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{e\}\]on geladas and chimpanzees\. Results are sorted by minimum sequence length for evaluation \(nm​i​nn\_\{min\}\), modality, criterion and distribution of sequence lengths i\.e\. uniform distribution \(u\), 1\-parameter geometric distribution \(g\) and the empirical distribution \(e\)\.Table 7:The performance scores𝔼⁡\[Pct\]\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{t\}\],𝔼⁡\[Q\]\\operatorname\{\\mathbb\{E\}\}\[Q\],𝔼⁡\[Pce\]\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{e\}\]on human languages in the PUD10 collection \(sentences of up to length 10 in PUD\)\. Results are sorted by minimum sequence length for evaluation \(nm​i​nn\_\{min\}\), language and evaluation score\. For each evaluation score, the sequence length distributions considered are a uniform distribution \(u\), a11\-parameter geometric distribution \(g\) and the empirical distribution \(e\)\.Table 8:The performance scores𝔼⁡\[Pct\]\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{t\}\],𝔼⁡\[Q\]\\operatorname\{\\mathbb\{E\}\}\[Q\],𝔼⁡\[Pce\]\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{e\}\]on human languages in the PUD10 collection \(sentences of up to length 10 in PUD\)\. Results are sorted by minimum sequence length for evaluation \(nm​i​nn\_\{min\}\), language and distribution of sequence lengths, i\.e\. uniform distribution \(u\), a11\-parameter geometric distribution \(g\) and the empirical distribution \(e\)\.## 5Discussion

### 5\.1The feasibility of evaluation

Assuming a uniform or a geometric distribution of sequence lengths, we have demonstrated theoretically that the performance of a random parser increases as the average sequence length decreases \(Fig\.[2](https://arxiv.org/html/2607.06542#S2.F2)and Fig\.[3](https://arxiv.org/html/2607.06542#S2.F3)\)\.

Although guessing the right tree is a hard task, guessing a large fraction of the correct edges is feasible in non\-human primates but much harder in humans\. In particular, we have shown that the performance of a random parser on non\-human primate sequences can be high\. That happens when the maximum sequence length is small enough in a large ensemble of primates \(Table[4\.2](https://arxiv.org/html/2607.06542#S4.SS2)\) or when the length distribution decays quickly, as in geladas and chimpanzees \(TablesLABEL:tab:performance\_by\_scoreand[4\.2](https://arxiv.org/html/2607.06542#S4.SS2)\)\. In contrast, the random parser has a worse performance in humans \(Table[4\.2](https://arxiv.org/html/2607.06542#S4.SS2), Table[5\.3](https://arxiv.org/html/2607.06542#S5.SS3)and Appendix[7](https://arxiv.org/html/2607.06542#A0.F7)\)\. Therefore, evaluation without gold standard in other species isa priorieasier than in ours\.

At first glance, a reader might conclude that it is not worth parsing non\-human primate vocal and gestural sequences due to the high accuracy of a random parser\. However, there are several reasons why parsing has value for these sequences\. First, it is worth recognizing that a null model is not necessarily true just because it produces some data\. A parser may have the same expected accuracy as the random parser but lower variance\. Similarly, failing to reject the null hypothesis with some statistic does not imply that the null hypothesis is correct\. We expect that a good\-enough parser, namely one that is statistically informedMarecek\([2016](https://arxiv.org/html/2607.06542#bib.bib27)\);Han et al\.\([2020](https://arxiv.org/html/2607.06542#bib.bib18)\), performs better than the random parser\. Second, randomness is a general approach to reality that also encompasses determinism\. A deterministic model is particular case of random model such that the probabilities are binary, namely zero or one\. A random parser is indeed deterministic whenn=1n=1orn=2n=2, where it always produces the same tree structure\. Crucially, the random parser is more deterministic in non\-human primate sequences than in human sentences because of the fast\-decaying distribution of sequence lengths of non\-human primates\. Therefore, the high chance that the random parser yields a correct parse implies that a good\-enough parser is channeled to yield a good parse in non\-human primates\.

### 5\.2The feasibility of training a parser

Here we have focused on the feasibility of evaluation\. However, there is still another critical question for future research, i\.e\. the feasibility of training a parser on the sequences that non\-human primates produce\. A prerequiste is that the sequences are not random in the sense of having some statistical structure\. In gelada vocal sequences and chimpanzee gesture sequences, previous units reduce the uncertainty about subsequent unitsGustison et al\.\([2016](https://arxiv.org/html/2607.06542#bib.bib17)\);Gustison\([2017](https://arxiv.org/html/2607.06542#bib.bib16)\);Mielke et al\.\([2024a](https://arxiv.org/html/2607.06542#bib.bib32)\)\.222For geladas inGustison\([2017](https://arxiv.org/html/2607.06542#bib.bib16)\), see Chapter 6, Figure 6\.S2\.The same applies to a wide range of other speciesFerrer\-i\-Cancho and Lusseau\([2006](https://arxiv.org/html/2607.06542#bib.bib8)\);Ferrer\-i\-Cancho and McCowan\([2012](https://arxiv.org/html/2607.06542#bib.bib9)\);Kershenbaum et al\.\([2014](https://arxiv.org/html/2607.06542#bib.bib22)\)\. Therefore, the primary challenge for training a parser is the low number of sequences available, i\.e\. of the order several thousands \(Table[3\.1](https://arxiv.org/html/2607.06542#S3.SS1)\)\. We speculate that unsupervised learning in non\-human primates should be easier than one may initially expect, partly due to the same reasons why evaluation turns out to be easier than expecteda priori\. A detailed explanation follows below\.

For human languages, several methods have been developed to constrain the learning space\. First, models are often trained with sentences whose tokens are part\-of\-speech tags \(unlexicalized approach\) instead of word tokens \(lexicalized approach\) so that unsupervised learning is easier\(Han et al\.,[2020](https://arxiv.org/html/2607.06542#bib.bib18), Section 5\.3\)\. For instance, the classic Penn Treebank features 36 POS tags333[https://www\.ling\.upenn\.edu/courses/Fall\_2003/ling001/penn\_treebank\_pos\.html](https://www.ling.upenn.edu/courses/Fall_2003/ling001/penn_treebank_pos.html)while Universal Dependencies features 17 POS tags\.444[https://universaldependencies\.org/u/pos/](https://universaldependencies.org/u/pos/)In non\-human primates, the number of types is small, typically just a couple of dozen in vocal repertoires, e\.g\., the number of call types produced by male geladasGustison et al\.\([2016](https://arxiv.org/html/2607.06542#bib.bib17)\)and chimpanzees is 12 in both casesGirard\-Buttoz et al\.\([2022](https://arxiv.org/html/2607.06542#bib.bib13)\), and∼100−150\\sim 100\-150in gestural repertoiresMielke et al\.\([2024b](https://arxiv.org/html/2607.06542#bib.bib33)\);Grund, Robbins, and Hobaiter\([2025](https://arxiv.org/html/2607.06542#bib.bib15)\)\. Therefore, the repertoires of non\-human primates have a similar order to the number of part\-of\-speech tags, which should ease unsupervised learning\. Second, curriculum learning has been used to enhance performance by employing shorter sentences firstSpitkovsky, Alshawi, and Jurafsky\([2010](https://arxiv.org/html/2607.06542#bib.bib41)\)\. The utility of that kind of approach has been analyzed theoreticallyTu and Honavar\([2011](https://arxiv.org/html/2607.06542#bib.bib42)\)\. In non\-human primate sequences, the short ones, are the majority \(Table[2](https://arxiv.org/html/2607.06542#S3.T2)and Figure[4](https://arxiv.org/html/2607.06542#S4.F4)\)\. Most sequences in the training set will be such that they have only one possible tree, as sequences of length 2 are the most frequent \(leaving aside “sequences” of length one\)\. We conclude that non\-human primate sequences have built\-in characteristics that ease unsupervised dependency learning and that those characteristics should compensate for the scarcity of data\.

### 5\.3Conclusion

The arguments above lead to the following unsupervised parsing methodology for sequences produced by a non\-human species

- •Prerequisites for successful training\. Check that there is some statistical structure in the sequences\.
- •Prerequisites for successful training and evaluation\. Check that the sequence length distribution decays fast \(exponentially\)\.
- •Training\. Train an unsupervised parser on the sequences\.
- •Validation of parser\. Check that the parser is a good\-enough parser by checking that it is able to retrieve dependency structures of a quality greater than expected by chance according to some objective function\. For instance, by checking that the mutual information of the dependencies is larger than expected for the same parser when trained on a random shuffling of the sequencesYuret\([1998](https://arxiv.org/html/2607.06542#bib.bib44)\)\.
- •Evaluation of the parser\. Obtain lower bounds of the performance of the good\-enough parser by means ofβ\\beta, the expected value of proportion of correct edges for a random parser\.β\\betacan be𝔼⁡\[Q\]\\operatorname\{\\mathbb\{E\}\}\[Q\]or𝔼⁡\[Pce\]\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{e\}\]\. Letβl\\beta\_\{l\}be the proportion of correct edges retrieved by the random on sequences of lengthllor greater\. We know thatβ2\\beta\_\{2\}can be a large number whileβ3\\beta\_\{3\}will be a smaller number\. Ifβ2\\beta\_\{2\}is large \(say\>84%\>84\\%as for chimpanzee gestures according to𝔼⁡\[Q\]\\operatorname\{\\mathbb\{E\}\}\[Q\]\), we can conclude that the performance of the good\-enough parser will be high and that its performance on sequences of 3 or greater is likely to be higher thanβ3\\beta\_\{3\}\(say higher than56%56\\%as for chimpanzee gestures\) because of the large number of sequences of length 2 reflected inβ2\\beta\_\{2\}, which implies very accurate dependency information for training\.

\\oldappendixsection

Probability distributions, expectations and likelihood

Here we consider the expectation ofϕ​\(n\)\\phi\(n\), a function ofnn, which is,

𝔼⁡\[ϕ​\(n\)\]=∑n=nm​i​n∞p​\(n\|n≥nm​i​n\)​ϕ​\(n\),\\operatorname\{\\mathbb\{E\}\}\[\\phi\(n\)\]=\\sum\_\{n=n\_\{min\}\}^\{\\infty\}p\(n\|n\\geq n\_\{min\}\)\\phi\(n\),assuming thatnnfollows a certain distribution\.

###### Property\\thetheorem\.

If the distribution ofnnis uniform with parametersnm​i​nn\_\{min\}andnm​a​xn\_\{max\}then

𝔼⁡\[n\]=nm​i​n\+nm​a​x2\\operatorname\{\\mathbb\{E\}\}\[n\]=\\frac\{n\_\{min\}\+n\_\{max\}\}\{2\}and

𝔼⁡\[1n\]=1nm​a​x−nm​i​n\+1​\[G​\(nm​a​x\)−G​\(nm​i​n−1\)\]\.\\operatorname\{\\mathbb\{E\}\}\\left\[\\frac\{1\}\{n\}\\right\]=\\frac\{1\}\{n\_\{max\}\-n\_\{min\}\+1\}\\left\[G\(n\_\{max\}\)\-G\(n\_\{min\}\-1\)\\right\]\.\(21\)

###### Proof\.

𝔼⁡\[n\]\\operatorname\{\\mathbb\{E\}\}\[n\]is well\-known\.

𝔼⁡\[1n\]\\displaystyle\\operatorname\{\\mathbb\{E\}\}\\left\[\\frac\{1\}\{n\}\\right\]=1nm​a​x−nm​i​n\+1​∑n=nm​i​nnm​a​x1n​\(Eq\.[9](https://arxiv.org/html/2607.06542#S2.E9)\)\\displaystyle=\\frac\{1\}\{n\_\{max\}\-n\_\{min\}\+1\}\\sum\_\{n=n\_\{min\}\}^\{n\_\{max\}\}\\frac\{1\}\{n\}\\mbox\{~~~\(Eq\. \\ref\{eq:uniform\_distribution\}\)\}=1nm​a​x−nm​i​n\+1​\[G​\(nm​a​x\)−G​\(nm​i​n−1\)\],\\displaystyle=\\frac\{1\}\{n\_\{max\}\-n\_\{min\}\+1\}\\left\[G\(n\_\{max\}\)\-G\(n\_\{min\}\-1\)\\right\],whereG​\(nm​a​x\)G\(n\_\{max\}\)is the harmonic number ofnm​a​xn\_\{max\}, defined as

G​\(nm​a​x\)=∑n=1nm​a​x1n\.G\(n\_\{max\}\)=\\sum\_\{n=1\}^\{n\_\{max\}\}\\frac\{1\}\{n\}\.∎

It is well\-known that

G​\(nm​a​x\)≈log⁡nm​a​x\+γ,G\(n\_\{max\}\)\\approx\\log n\_\{max\}\+\\gamma,whereγ=0\.5772​…\\gamma=0\.5772\.\.\.is the Euler\-Mascheroni constant\. Hence Eq\.[21](https://arxiv.org/html/2607.06542#A0.E21)can be approximated as

𝔼⁡\[1n\]≈1nm​a​x−nm​i​n\+1​\[log⁡\(nm​a​x\)\+γ−G​\(nm​i​n−1\)\]\.\\operatorname\{\\mathbb\{E\}\}\\left\[\\frac\{1\}\{n\}\\right\]\\approx\\frac\{1\}\{n\_\{max\}\-n\_\{min\}\+1\}\\left\[\\log\(n\_\{max\}\)\+\\gamma\-G\(n\_\{min\}\-1\)\\right\]\.for smallnm​i​nn\_\{min\}and sufficiently largenm​a​xn\_\{max\}\.

Recall a useful well\-known property of the geometric series\.

###### Property\\thetheorem\.

Forr∈\(0,1\)r\\in\(0,1\),

A=∑n=nm​i​n∞rn=rnm​i​n1−r\.A=\\sum\_\{n=n\_\{min\}\}^\{\\infty\}r^\{n\}=\\frac\{r^\{n\_\{min\}\}\}\{1\-r\}\.

###### Proof\.

The result follows after some algebra from noting that

r​A=A−rnm​i​n\.rA=A\-r^\{n\_\{min\}\}\.∎

The next property will help us to calculate𝔼⁡\[1/n\]\\operatorname\{\\mathbb\{E\}\}\[1/n\]for the geometric distribution\.

###### Property\\thetheorem\.

Consider0≤r<10\\leq r<1\. Then

∑n=nm​i​n∞rnn=−log⁡\(1−r\)−∑n=1nm​i​n−1rnn\.\\sum\_\{n=n\_\{min\}\}^\{\\infty\}\\frac\{r^\{n\}\}\{n\}=\-\\log\(1\-r\)\-\\sum\_\{n=1\}^\{n\_\{min\}\-1\}\\frac\{r^\{n\}\}\{n\}\.

###### Proof\.

The summation

∑n=nm​i​n∞\\sum\_\{n=n\_\{min\}\}^\{\\infty\}with0≤r<10\\leq r<1converges because

∑n=nm​i​n∞r\\sum\_\{n=n\_\{min\}\}^\{\\infty\}rconverges \(recall Property[5\.3](https://arxiv.org/html/2607.06542#S5.SS3)\)\. Notice that

∑n=nm​i​n∞rnn=∑n=1∞rnn−∑n=1nm​i​n−1rnn\.\\sum\_\{n=n\_\{min\}\}^\{\\infty\}\\frac\{r^\{n\}\}\{n\}=\\sum\_\{n=1\}^\{\\infty\}\\frac\{r^\{n\}\}\{n\}\-\\sum\_\{n=1\}^\{n\_\{min\}\-1\}\\frac\{r^\{n\}\}\{n\}\.In turn,

∑n=1∞rnn\\displaystyle\\sum\_\{n=1\}^\{\\infty\}\\frac\{r^\{n\}\}\{n\}=∑n=1∞∫0rtn−1​𝑑t\\displaystyle=\\sum\_\{n=1\}^\{\\infty\}\\int\_\{0\}^\{r\}t^\{n\-1\}dt=∫0r\(∑n=1∞tn−1\)​𝑑t​\(swapping integration and summation\)\\displaystyle=\\int\_\{0\}^\{r\}\\left\(\\sum\_\{n=1\}^\{\\infty\}t^\{n\-1\}\\right\)dt\\mbox\{~~~\(swapping integration and summation\)\}=∫0r11−t​𝑑t​\(0<t<1\)\(Property[5\.3](https://arxiv.org/html/2607.06542#S5.SS3)withnm​i​n=0\)\\displaystyle=\\int\_\{0\}^\{r\}\\frac\{1\}\{1\-t\}dt\\mbox\{~~~\($0<t<1$\)\}\\mbox\{~~~\(Property \\ref\{prop:useful\_geometric\_series\} with $n\_\{min\}=0$\)\}=−log⁡\(1−r\)\\displaystyle=\-\\log\(1\-r\)Hence Eq\.[23](https://arxiv.org/html/2607.06542#A0.E23)\. The swapping of integration and summation above is justified by the fact that the series∑n=1∞tn−1\\sum\_\{n=1\}^\{\\infty\}t^\{n\-1\}converges uniformly on the interval\[0,t\]\[0,t\]ift<1t<1\.

∎

###### Property\\thetheorem\.

Ifnnfollows a geometric distribution with parametersqqandnm​i​nn\_\{min\}, then

𝔼⁡\[n\]=nm​i​n−1\+1q\\operatorname\{\\mathbb\{E\}\}\[n\]=n\_\{min\}\-1\+\\frac\{1\}\{q\}\(22\)and

𝔼⁡\[1n\]=−q​\(log⁡q\(1−q\)nm​i​n\+∑n=1nm​i​n−1\(1−q\)n−nm​i​nn\)\.\\operatorname\{\\mathbb\{E\}\}\\left\[\\frac\{1\}\{n\}\\right\]=\-q\\left\(\\frac\{\\log q\}\{\(1\-q\)^\{n\_\{min\}\}\}\+\\sum\_\{n=1\}^\{n\_\{min\}\-1\}\\frac\{\(1\-q\)^\{n\-n\_\{min\}\}\}\{n\}\\right\)\.\(23\)

###### Proof\.

nnfollows a geometric distribution defined byp​\(n\|n≥nm​i​n\)p\(n\|n\\geq n\_\{min\}\)with parametersqqandnm​i​nn\_\{min\}\(Eq\.[10](https://arxiv.org/html/2607.06542#S2.E10)\) and hencenntakes integer values on\[nm​i​n,∞\)\[n\_\{min\},\\infty\)\. Eq\.[22](https://arxiv.org/html/2607.06542#A0.E22)is a well\-known resultPark and Wang\([2023](https://arxiv.org/html/2607.06542#bib.bib36)\)\. Besides,

𝔼⁡\[1n\]\\displaystyle\\operatorname\{\\mathbb\{E\}\}\\left\[\\frac\{1\}\{n\}\\right\]=q\(1−q\)nm​i​n​∑n=nm​i​n∞\(1−q\)nn\.\\displaystyle=\\frac\{q\}\{\(1\-q\)^\{n\_\{min\}\}\}\\sum\_\{n=n\_\{min\}\}^\{\\infty\}\\frac\{\(1\-q\)^\{n\}\}\{n\}\.Property[5\.3](https://arxiv.org/html/2607.06542#S5.SS3)withr=1−qr=1\-qgives

𝔼⁡\[1n\]=−q\(1−q\)nm​i​n​\(log⁡q\+∑n=1nm​i​n−1\(1−q\)nn\)\.\\operatorname\{\\mathbb\{E\}\}\\left\[\\frac\{1\}\{n\}\\right\]=\-\\frac\{q\}\{\(1\-q\)^\{n\_\{min\}\}\}\\left\(\\log q\+\\sum\_\{n=1\}^\{n\_\{min\}\-1\}\\frac\{\(1\-q\)^\{n\}\}\{n\}\\right\)\.Hence Eq\.[23](https://arxiv.org/html/2607.06542#A0.E23)\. ∎

Finally, we wish to estimate the parameters of a geometric distribution of sequence lengths by maximizing the likelihood\. Suppose we haveSSsequences of lengthnm​i​nn\_\{min\}or greater\. Then the likelihood of the observed sequence lengths is

L=∏i=1Sp​\(ni\)\.L=\\prod\_\{i=1\}^\{S\}p\(n\_\{i\}\)\.\(24\)
The following property provides well\-known biased parameter estimators\.

###### Property\\thetheorem\.

Suppose a geometric distribution with parametersqqandnm​i​nn\_\{min\}\. Suppose a sample formed bySSsequences of lengthnm​i​nn\_\{min\}or greater andTTtokens in total\. The maximum likelihood estimator fornm​i​nn\_\{min\}is the minimum sequence length in the sample\. The maximum likelihood estimator forqqis

q^\\displaystyle\\hat\{q\}=ST−S\(nm​i​n−1\)\)\\displaystyle=\\frac\{S\}\{T\-S\(n\_\{min\}\-1\)\)\}\(25\)=\(⟨n⟩\+1−nm​i​n\)−1\.\\displaystyle=\(\\left<n\\right\>\+1\-n\_\{min\}\)^\{\-1\}\.\(26\)Hence

q^=\{1/\(⟨n⟩−1\)fornm​i​n=01/⟨n⟩fornm​i​n=11/\(⟨n⟩\+1\)fornm​i​n=2\.\\hat\{q\}=\\left\\\{\\begin\{array\}\[\]\{ll\}1/\(\\left<n\\right\>\-1\)&\\mbox\{~for $n\_\{min\}=0$\}\\\\ 1/\\left<n\\right\>&\\mbox\{~for $n\_\{min\}=1$\}\\\\ 1/\(\\left<n\\right\>\+1\)&\\mbox\{~for $n\_\{min\}=2$\}\.\\end\{array\}\\right\.

###### Proof\.

Eq\.[26](https://arxiv.org/html/2607.06542#A0.E26)is well\-knownPark and Wang\([2023](https://arxiv.org/html/2607.06542#bib.bib36)\)\. From it all other equations follow easily but we wish to be clear on hownm​i​nn\_\{min\}has to visit and that implies revising the whole derivation process\.

Then log\-likelihood is \(Eq\.[24](https://arxiv.org/html/2607.06542#A0.E24)\)

ℒ=log⁡L=∑i=1Slog⁡p​\(ni\)\.\{\\cal L\}=\\log L=\\sum\_\{i=1\}^\{S\}\\log p\(n\_\{i\}\)\.\(27\)Applying Eq\.[10](https://arxiv.org/html/2607.06542#S2.E10)to Eq\.[27](https://arxiv.org/html/2607.06542#A0.E27), we get

ℒ\\displaystyle\{\\cal L\}=∑i=1Slog⁡q\+∑i=1S\(ni−nm​i​n\)​log⁡\(1−q\)\\displaystyle=\\sum\_\{i=1\}^\{S\}\\log q\+\\sum\_\{i=1\}^\{S\}\(n\_\{i\}\-n\_\{min\}\)\\log\(1\-q\)=S​log⁡q\+log⁡\(1−q\)​\(∑i=1S\(ni−nm​i​n\)\)\\displaystyle=S\\log q\+\\log\(1\-q\)\\left\(\\sum\_\{i=1\}^\{S\}\(n\_\{i\}\-n\_\{min\}\)\\right\)=S​log⁡q\+\(T−S​nm​i​n\)​log⁡\(1−q\)\.\\displaystyle=S\\log q\+\(T\-Sn\_\{min\}\)\\log\(1\-q\)\.It is easy to see thatℒ\{\\cal L\}is a decreasing function ofnm​i​nn\_\{min\}\. Therefore,ℒ\{\\cal L\}is maximized whennm​i​nn\_\{min\}is set to the minimum sequence length in the sample\.

Setting∂ℒ/∂q=0\\partial\{\\cal L\}/\\partial q=0, we obtain Eq\.[25](https://arxiv.org/html/2607.06542#A0.E25)after some algebra\. Noting that⟨n⟩=T/S\\left<n\\right\>=T/Swe obtain Eq\.[26](https://arxiv.org/html/2607.06542#A0.E26)\. ∎

q^\\hat\{q\}is a biased estimator ofqqPark and Wang\([2023](https://arxiv.org/html/2607.06542#bib.bib36)\)\. The following estimator fixes the problem\.

###### Property\\thetheorem\(Park and Wang\([2023](https://arxiv.org/html/2607.06542#bib.bib36)\)\)\.

The minimum variance unbiased \(MVU\) estimator forqqis

q^\\displaystyle\\hat\{q\}=S−1T−S​\(nm​i​n−1\)−1\\displaystyle=\\frac\{S\-1\}\{T\-S\(n\_\{min\}\-1\)\-1\}\(28\)=\(S−1\)/S⟨n⟩\+1−nm​i​n−1/S\.\\displaystyle=\\frac\{\(S\-1\)/S\}\{\\left<n\\right\>\+1\-n\_\{min\}\-1/S\}\.\(29\)Hence

q^\\displaystyle\\hat\{q\}=\{\(S−1\)/S⟨n⟩−1−1/S\)fornm​i​n=0\(S−1\)/S⟨n⟩−1/Sfornm​i​n=1\(S−1\)/S⟨n⟩\+1−1/Sfornm​i​n=2\.\\displaystyle=\\left\\\{\\begin\{array\}\[\]\{ll\}\\frac\{\(S\-1\)/S\}\{\\left<n\\right\>\-1\-1/S\)\}&\\mbox\{~for $n\_\{min\}=0$\}\\\\ \\frac\{\(S\-1\)/S\}\{\\left<n\\right\>\-1/S\}&\\mbox\{~for $n\_\{min\}=1$\}\\\\ \\frac\{\(S\-1\)/S\}\{\\left<n\\right\>\+1\-1/S\}&\\mbox\{~for $n\_\{min\}=2$\}\.\\end\{array\}\\right\.

\\oldappendixsection

The expected proportion of correct trees

A sequence of lengthnnhasnn−2n^\{n\-2\}labeled treesCayley\([1889](https://arxiv.org/html/2607.06542#bib.bib6)\)\. The probability of obtaining the correct tree by picking one of them uniformly at random is

p​\(ci=1\|n\)=1/nn−2=n2−n\.p\(c\_\{i\}=1\|n\)=1/n^\{n\-2\}=n^\{2\-n\}\.\(31\)The probability of choosing the correct tree at random in a sequence of three units is1/31/3; in a sequence of four units, this probability is1/161/16\.

The expected value ofPctP\_\{c\}^\{t\}givenS​\(nm​i​n\)S\(n\_\{min\}\)is

𝔼⁡\[Pct\]\\displaystyle\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{t\}\]=1S​\(nm​i​n\)​𝔼⁡\[Sc​\(nm​i​n\)\]​\(Eq\.[2](https://arxiv.org/html/2607.06542#S2.E2)\)\\displaystyle=\\frac\{1\}\{S\(n\_\{min\}\)\}\\operatorname\{\\mathbb\{E\}\}\[S\_\{c\}\(n\_\{min\}\)\]\\mbox\{~~~\(Eq\. \\ref\{eq:proportion\_of\_correct\_trees\}\)\}=1S​\(nm​i​n\)​∑i=1ni≥nm​i​nS𝔼⁡\[ci\]​\(Eq\.[3](https://arxiv.org/html/2607.06542#S2.E3)and linearity of expectation\)\\displaystyle=\\frac\{1\}\{S\(n\_\{min\}\)\}\\sum\_\{\\begin\{subarray\}\{c\}i=1\\\\ n\_\{i\}\\geq n\_\{min\}\\end\{subarray\}\}^\{S\}\\operatorname\{\\mathbb\{E\}\}\\left\[c\_\{i\}\\right\]\\mbox\{~~~\(Eq\. \\ref\{eq:number\_of\_correct\_trees\} and linearity of expectation\)\}=𝔼⁡\[ci\]\.\(identically distributedci’s\)\\displaystyle=\\operatorname\{\\mathbb\{E\}\}\[c\_\{i\}\]\.\\mbox\{~~~\(identically distributed $c\_\{i\}$'s\)\}\(32\)
Ascic\_\{i\}is an indicator variable,𝔼⁡\[ci\]\\operatorname\{\\mathbb\{E\}\}\[c\_\{i\}\]becomes the probability that a uniformly random labeled tree matches the correct tree of an arbitrary sequence of lengthnm​i​nn\_\{min\}or greater, namely

𝔼⁡\[ci\]\\displaystyle\\operatorname\{\\mathbb\{E\}\}\[c\_\{i\}\]=∑n=nm​i​n∞p​\(n\|n≥nm​i​n\)​p​\(ci=1\|n\)​\(law of total expectation\)\\displaystyle=\\sum\_\{n=n\_\{min\}\}^\{\\infty\}p\(n\|n\\geq n\_\{min\}\)p\(c\_\{i\}=1\|n\)\\mbox\{~~~\(law of total expectation\)\}=∑n=nm​i​n∞p​\(n\|n≥nm​i​n\)​n2−n\.\(Eq\.[31](https://arxiv.org/html/2607.06542#A0.E31)\)\\displaystyle=\\sum\_\{n=n\_\{min\}\}^\{\\infty\}p\(n\|n\\geq n\_\{min\}\)n^\{2\-n\}\.\\mbox\{~~~\(Eq\. \\ref\{eq:random\_tree\_probability\}\)\}Then Eq\.[32](https://arxiv.org/html/2607.06542#A0.E32)becomes

𝔼⁡\[Pct\]=∑n=nm​i​n∞p​\(n\|n≥nm​i​n\)​n2−n\.\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{t\}\]=\\sum\_\{n=n\_\{min\}\}^\{\\infty\}p\(n\|n\\geq n\_\{min\}\)n^\{2\-n\}\.\(33\)For the uniform distribution above \(Eq\.[9](https://arxiv.org/html/2607.06542#S2.E9)\),

𝔼⁡\[Pct\]=1nm​a​x−nm​i​n\+1​∑n=nm​i​nnm​a​xn2−n\.\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{t\}\]=\\frac\{1\}\{n\_\{max\}\-n\_\{min\}\+1\}\\sum\_\{n=n\_\{min\}\}^\{n\_\{max\}\}n^\{2\-n\}\.For the 2\-parameter geometric distribution above \(Eq\.[10](https://arxiv.org/html/2607.06542#S2.E10)\)

𝔼⁡\[Pct\]=q​\(1−q\)−nm​i​n​∑n=nm​i​nnm​a​x\(1−q\)n​n2−n\.\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{t\}\]=q\(1\-q\)^\{\-n\_\{min\}\}\\sum\_\{n=n\_\{min\}\}^\{n\_\{max\}\}\(1\-q\)^\{n\}n^\{2\-n\}\.For the empirical distribution , Eq\.[11](https://arxiv.org/html/2607.06542#S2.E11)and Eq\.[33](https://arxiv.org/html/2607.06542#A0.E33)give

𝔼⁡\[Pct\]=1S​\(nm​i​n\)​∑n=nm​i​nnm​a​xf​\(n\)​n2−n\.\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{t\}\]=\\frac\{1\}\{S\(n\_\{min\}\)\}\\sum\_\{n=n\_\{min\}\}^\{n\_\{max\}\}f\(n\)n^\{2\-n\}\.In the last case,𝔼⁡\[Pct\]\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{t\}\]is the expected proportion of correct random trees when the length of each sequence is provided\.

\\oldappendixsection

The expected proportion of correct edges

First, we assume thatℱ\{\\cal F\}consists of a single tree ofnnvertices\. Thenm=n−1m=n\-1andmcm\_\{c\}becomes the number of edges of a tree that are correct and then

Pce=mcn−1P\_\{c\}^\{e\}=\\frac\{m\_\{c\}\}\{n\-1\}and

𝔼⁡\[Pce\|n\]=1n−1​𝔼⁡\[mc\|n\],\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{e\}\|n\]=\\frac\{1\}\{n\-1\}\\operatorname\{\\mathbb\{E\}\}\[m\_\{c\}\|n\],where𝔼⁡\[mc\|n\]\\operatorname\{\\mathbb\{E\}\}\[m\_\{c\}\|n\]is the expected size of the intersection between the correct tree and the tree produced by the parser given their sizenn\. It is easy to see that,𝔼⁡\[mc\|n\]=1\\operatorname\{\\mathbb\{E\}\}\[m\_\{c\}\|n\]=1whenn=2n=2\. Forn\>2n\>2, recall that we have assumed that all trees of same size have equal chance of being the correct tree\. Then, it is easy to see that𝔼⁡\[mc\]=43\\operatorname\{\\mathbb\{E\}\}\[m\_\{c\}\]=\\frac\{4\}\{3\}whenn=3n=3\. The point is that there are three labeled trees\. When selecting a pair of those trees at random: the trees can be the same with probability 1/3, which givesmc=2m\_\{c\}=2or the trees are different with probability 2/3, which givesmc=1m\_\{c\}=1\. Then

𝔼⁡\[mc\]=13​2\+23​1=43\.\\operatorname\{\\mathbb\{E\}\}\[m\_\{c\}\]=\\frac\{1\}\{3\}2\+\\frac\{2\}\{3\}1=\\frac\{4\}\{3\}\.𝔼⁡\[mc\]\\operatorname\{\\mathbb\{E\}\}\[m\_\{c\}\]is known as the value of the tree intersection game, namely the number of edges shared by two random treesLondon and Pluhár\([2023](https://arxiv.org/html/2607.06542#bib.bib25)\)\. If trees are uniformly random labeled trees, one has\(London and Pluhár,[2023](https://arxiv.org/html/2607.06542#bib.bib25), Observation 3\)

𝔼⁡\[mc\|n\]=2​\(n−1\)n\\operatorname\{\\mathbb\{E\}\}\[m\_\{c\}\|n\]=\\frac\{2\(n\-1\)\}\{n\}\(34\)forn≥1n\\geq 1\. Hence

𝔼⁡\[Pce\|n\]=2n\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{e\}\|n\]=\\frac\{2\}\{n\}\(35\)forn\>1n\>1\. Whenn=1n=1,𝔼⁡\[Pce\]\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{e\}\]is undefined\. The expected proportion of correct edges retrieved whenn=2n=2is obviously 1, whenn=3n=3it is2/32/3and whenn=4n=4it is1/21/2\. In the original setting ofLondon and Pluhár\([2023](https://arxiv.org/html/2607.06542#bib.bib25)\), one selects two random spanning trees from a graphGG\. In our application of their framework,GGis a complete graph ofnnvertices and one of the spanning trees has the role of the spanning tree and the other spanning tree has the role of the tree retrieved by the random parser\.

Now we return to the general case, whereℱ\{\\cal F\}may be formed by one or more trees\. The two ways of measuring the performance of the parser above parallel the two ways of measuring the clustering coefficient in network science\(Newman,[2010](https://arxiv.org/html/2607.06542#bib.bib35), Chapter 7\): one is the proportion of paths of lengths two that are closed \(the counterpart ofPceP\_\{c\}^\{e\}\) and the other is the average local proportion over the paths formed by the neighbors of a vertex \(the counterpart ofQQ\)\.

We aim to calculate the expectation ofPceP\_\{c\}^\{e\}and that ofQQ\. We have

𝔼⁡\[mc,i\]\\displaystyle\\operatorname\{\\mathbb\{E\}\}\[m\_\{c,i\}\]=∑n=nm​i​n∞p​\(n\|n≥nm​i​n\)​𝔼⁡\[mc\|n\]​\(law of total expectation\)\\displaystyle=\\sum\_\{n=n\_\{min\}\}^\{\\infty\}p\(n\|n\\geq n\_\{min\}\)\\operatorname\{\\mathbb\{E\}\}\[m\_\{c\}\|n\]\\mbox\{~~~\(law of total expectation\)\}=2​∑n=nm​i​n∞p​\(n\|n≥nm​i​n\)​\(1−1n\)​\(Eq\.[34](https://arxiv.org/html/2607.06542#A0.E34)\)\\displaystyle=2\\sum\_\{n=n\_\{min\}\}^\{\\infty\}p\(n\|n\\geq n\_\{min\}\)\\left\(1\-\\frac\{1\}\{n\}\\right\)\\mbox\{~~~\(Eq\. \\ref\{eq:expected\_number\_of\_intersecting\_edges\_over\_single\_tree\}\)\}\(36\)and

𝔼⁡\[Pc,ie\]\\displaystyle\\operatorname\{\\mathbb\{E\}\}\[P\_\{c,i\}^\{e\}\]=∑n=nm​i​n∞p​\(n\|n≥nm​i​n\)​𝔼⁡\[mc\|n\]​\(law of total expectation\)\\displaystyle=\\sum\_\{n=n\_\{min\}\}^\{\\infty\}p\(n\|n\\geq n\_\{min\}\)\\operatorname\{\\mathbb\{E\}\}\[m\_\{c\}\|n\]\\mbox\{~~~\(law of total expectation\)\}=2​∑n=nm​i​n∞p​\(n\|n≥nm​i​n\)n\.\(Eq\.[35](https://arxiv.org/html/2607.06542#A0.E35)\)\\displaystyle=2\\sum\_\{n=n\_\{min\}\}^\{\\infty\}\\frac\{p\(n\|n\\geq n\_\{min\}\)\}\{n\}\.\\mbox\{~~~\(Eq\. \\ref\{eq:expected\_proportion\_of\_intersecting\_edges\_over\_single\_tree\}\)\}\(37\)Then

𝔼⁡\[Q\]\\displaystyle\\operatorname\{\\mathbb\{E\}\}\[Q\]=1S​\(nm​i​n\)​∑i=1ni≥nm​i​nS𝔼⁡\[Pc,ie\]​\(linearity of expectation\)\\displaystyle=\\frac\{1\}\{S\(n\_\{min\}\)\}\\sum\_\{\\begin\{subarray\}\{c\}i=1\\\\ n\_\{i\}\\geq n\_\{min\}\\end\{subarray\}\}^\{S\}\\operatorname\{\\mathbb\{E\}\}\[P\_\{c,i\}^\{e\}\]\\mbox\{~~~\(linearity of expectation\)\}=𝔼⁡\[Pc,ie\]\\displaystyle=\\operatorname\{\\mathbb\{E\}\}\[P\_\{c,i\}^\{e\}\]=2​∑n=nm​i​n∞p​\(n\|n≥nm​i​n\)n\.\(Eq\.[37](https://arxiv.org/html/2607.06542#A0.E37)\)\\displaystyle=2\\sum\_\{n=n\_\{min\}\}^\{\\infty\}\\frac\{p\(n\|n\\geq n\_\{min\}\)\}\{n\}\.\\mbox\{~~~\(Eq\. \\ref\{eq:expected\_proportion\_of\_intersecting\_edges\_over\_single\_tree\_unknown\_tree\_size\}\)\}\(38\)
For the empirical distribution, Eq\.[11](https://arxiv.org/html/2607.06542#S2.E11)and[38](https://arxiv.org/html/2607.06542#A0.E38)yield

𝔼⁡\[Q\]=2H​\(nm​i​n\),\\operatorname\{\\mathbb\{E\}\}\[Q\]=\\frac\{2\}\{H\(n\_\{min\}\)\},whereH​\(nm​i​n\)H\(n\_\{min\}\)is the harmonic mean of sentence lengths that arenm​i​nn\_\{min\}or larger, that is

H​\(nm​i​n\)\\displaystyle H\(n\_\{min\}\)=1S​\(nm​i​n\)​∑n=nm​i​nnm​a​xf​\(n\)n\\displaystyle=\\frac\{1\}\{S\(n\_\{min\}\)\}\\sum\_\{n=n\_\{min\}\}^\{n\_\{max\}\}\\frac\{f\(n\)\}\{n\}=1S​\(nm​i​n\)​∑i=1ni≥nm​i​nS1ni\.\\displaystyle=\\frac\{1\}\{S\(n\_\{min\}\)\}\\sum\_\{\\begin\{subarray\}\{c\}i=1\\\\ n\_\{i\}\\geq n\_\{min\}\\end\{subarray\}\}^\{S\}\\frac\{1\}\{n\_\{i\}\}\.\(39\)
Besides, we have

𝔼⁡\[Pce\]\\displaystyle\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{e\}\]=1m​\(nm​i​n\)​𝔼⁡\[mc​\(nm​i​n\)\]​\(Eq\.[4](https://arxiv.org/html/2607.06542#S2.E4)andm​\(nm​i​n\)is constant\)\\displaystyle=\\frac\{1\}\{m\(n\_\{min\}\)\}\\operatorname\{\\mathbb\{E\}\}\\left\[m\_\{c\}\(n\_\{min\}\)\\right\]\\mbox\{~~~\(Eq\. \\ref\{eq:proportion\_of\_correct\_edges\} and $m\(n\_\{min\}\)$ is constant\)\}=1m​\(nm​i​n\)​∑i=1ni≥nm​i​nS𝔼⁡\[mc,i\]​\(Eq\.[5](https://arxiv.org/html/2607.06542#S2.E5)and linearity of expectation\)\\displaystyle=\\frac\{1\}\{m\(n\_\{min\}\)\}\\sum\_\{\\begin\{subarray\}\{c\}i=1\\\\ n\_\{i\}\\geq n\_\{min\}\\end\{subarray\}\}^\{S\}\\operatorname\{\\mathbb\{E\}\}\[m\_\{c,i\}\]\\mbox\{~~~\(Eq\. \\ref\{eq:total\_number\_of\_edges\} and linearity of expectation\)\}=2​S​\(nm​i​n\)m​\(nm​i​n\)​∑n=nm​i​n∞p​\(n\|n≥nm​i​n\)​\(1−1n\)​\(Eq\.[36](https://arxiv.org/html/2607.06542#A0.E36)\)\\displaystyle=\\frac\{2S\(n\_\{min\}\)\}\{m\(n\_\{min\}\)\}\\sum\_\{n=n\_\{min\}\}^\{\\infty\}p\(n\|n\\geq n\_\{min\}\)\\left\(1\-\\frac\{1\}\{n\}\\right\)\\mbox\{~~~\(Eq\. \\ref\{eq:expected\_number\_of\_intersecting\_edges\_over\_single\_tree\_unknown\_tree\_size\}\)\}\(40\)
For the empirical distribution, Eq\.[11](https://arxiv.org/html/2607.06542#S2.E11)and Eq\.[40](https://arxiv.org/html/2607.06542#A0.E40)yield

𝔼⁡\[Pce\]\\displaystyle\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{e\}\]=2m​\(nm​i​n\)​∑n=nm​i​nnm​a​xf​\(n\)​\(1−1n\)​\(Eq\.[34](https://arxiv.org/html/2607.06542#A0.E34)\)\\displaystyle=\\frac\{2\}\{m\(n\_\{min\}\)\}\\sum\_\{n=n\_\{min\}\}^\{n\_\{max\}\}f\(n\)\\left\(1\-\\frac\{1\}\{n\}\\right\)\\mbox\{~~~\(Eq\. \\ref\{eq:expected\_number\_of\_intersecting\_edges\_over\_single\_tree\}\)\}=2m​\(nm​i​n\)​\[S​\(nm​i​n\)−H​\(nm​i​n\)\]\.\(Eq\.[39](https://arxiv.org/html/2607.06542#A0.E39)\)\\displaystyle=\\frac\{2\}\{m\(n\_\{min\}\)\}\[S\(n\_\{min\}\)\-H\(n\_\{min\}\)\]\.\\mbox\{~~~\(Eq\. \\ref\{eq:harmonic\_mean\}\)\}
\\oldappendixsection

The theoretical performance of the random parser

We examine the performance of the random parser as a direct function of the parameters of the distribution\. In increase ofnm​a​xn\_\{max\}\(in the uniform distribution\) or a reduction ofqq\(in the geometric distribution\) leads to leads to longer sequences\.

As expected from the Section[2\.6](https://arxiv.org/html/2607.06542#S2.SS6), performance decreases as the parametersnm​a​xn\_\{max\}of the uniform distribution increases \(Fig\.[5](https://arxiv.org/html/2607.06542#A0.F5)\) while it increases as the parameterqqof the geometric distribution increases \(Fig\.[6](https://arxiv.org/html/2607.06542#A0.F6)\)\.

![Refer to caption](https://arxiv.org/html/2607.06542v1/x5.png)Figure 5:The performance of a random parser as a function of the parameternm​a​xn\_\{max\}of a uniform distribution in the interval\[1,nm​a​x\]\[1,n\_\{max\}\]\(Eq\.[9](https://arxiv.org/html/2607.06542#S2.E9)\)\. Three performance scores are considered:𝔼⁡\[Pct\]\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{t\}\], the expected proportion of correct trees \(top\),𝔼⁡\[Q\]\\operatorname\{\\mathbb\{E\}\}\[Q\], the average expected proportion of correct edges per sequence \(middle\) and𝔼⁡\[Pce\]\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{e\}\], the expected overall proportion of correct edges \(bottom\)\. On top each subfigure,nm​i​nn\_\{min\}indicates the minimum sequence length considered to measure the performance of the parser\.![Refer to caption](https://arxiv.org/html/2607.06542v1/x6.png)Figure 6:The performance of a random parser as a function of the parameterqqof a geometric distribution on\[1,∞\)\[1,\\infty\)\(Eq\.[10](https://arxiv.org/html/2607.06542#S2.E10)\)\. The format is the same as in Fig\.[5](https://arxiv.org/html/2607.06542#A0.F5)\.\\oldappendixsection

Computation of the expected performance of the random parser for the geometric distribution

We aim to calculateKK\(Eq\.[20](https://arxiv.org/html/2607.06542#S2.E20)\) with high numerical precision for the geometric distribution\. ConsiderK~\\widetilde\{K\}as an approximation ofKKup ton∗n\_\{\*\}, that is

K~=c​∑n=nm​i​nn∗p​\(n\|n≥nm​i​n\)​ϕ​\(n\)\.\(Eq\.[12](https://arxiv.org/html/2607.06542#S2.E12)and Eq\.[20](https://arxiv.org/html/2607.06542#S2.E20)\)\\widetilde\{K\}=c\\sum\_\{n=n\_\{min\}\}^\{n\_\{\*\}\}p\(n\|n\\geq n\_\{min\}\)\\phi\(n\)\.\\mbox\{~~~\(Eq\. \\ref\{eq:generic\_expectation\} and Eq\. \\ref\{eq:generic\_K\_score\}\)\}We define the approximation error ofK~\\widetilde\{K\}asϵ=K−K~\\epsilon=K\-\\widetilde\{K\}\. Notice thatϵ≥0\\epsilon\\geq 0sinceK~≤K\\widetilde\{K\}\\leq K\. We have

ϵ\\displaystyle\\epsilon=c​∑n=n∗\+1∞p​\(n\|n≥nm​i​n\)​ϕ​\(n\)​\(Eq\.[12](https://arxiv.org/html/2607.06542#S2.E12)and Eq\.[20](https://arxiv.org/html/2607.06542#S2.E20)\)\\displaystyle=c\\sum\_\{n=n\_\{\*\}\+1\}^\{\\infty\}p\(n\|n\\geq n\_\{min\}\)\\phi\(n\)\\mbox\{~~~\(Eq\. \\ref\{eq:generic\_expectation\} and Eq\. \\ref\{eq:generic\_K\_score\}\)\}=c​q​\(1−q\)−nm​i​n​∑n=n∗\+1∞\(1−q\)n​ϕ​\(n\)\.\\displaystyle=cq\(1\-q\)^\{\-n\_\{min\}\}\\sum\_\{n=n\_\{\*\}\+1\}^\{\\infty\}\(1\-q\)^\{n\}\\phi\(n\)\.
We defineϕm​a​x\\phi\_\{max\}as an upper bound ofϕ​\(n\)\\phi\(n\)in the interval\[n∗\+1,∞\)\[n\_\{\*\}\+1,\\infty\)\. We also defineϵm​a​x\\epsilon\_\{max\}, an upper bound ofϵ\\epsilon, that is obtained by settingϕ​\(n\)\\phi\(n\)toϕm​a​x\\phi\_\{max\}and noting that \(Property[5\.3](https://arxiv.org/html/2607.06542#S5.SS3)\)

∑n=n∗\+1∞\(1−q\)n=\(1−q\)n∗\+1q,\\sum\_\{n=n\_\{\*\}\+1\}^\{\\infty\}\(1\-q\)^\{n\}=\\frac\{\(1\-q\)^\{n\_\{\*\}\+1\}\}\{q\},which yields

ϵm​a​x=c​ϕm​a​x​\(1−q\)n∗\+1−nm​i​n\\epsilon\_\{max\}=c\\phi\_\{max\}\(1\-q\)^\{n\_\{\*\}\+1\-n\_\{min\}\}Rearranging terms one gets

ϵ​\(1−q\)nm​i​n−1c​ϕm​a​x=\(1−q\)n∗\.\\frac\{\\epsilon\(1\-q\)^\{n\_\{min\}\-1\}\}\{c\\phi\_\{max\}\}=\(1\-q\)^\{n\_\{\*\}\}\.Taking logarithms on both sides, we get

n∗=log⁡ϵc​ϕm​a​xlog⁡\(1−q\)\+nm​i​n−1\.n^\{\*\}=\\frac\{\\log\\frac\{\\epsilon\}\{c\\phi\_\{max\}\}\}\{\\log\(1\-q\)\}\+n\_\{min\}\-1\.Changing the base of the logarithm to1−q1\-qand truncating \(ceiling\) to ensure thatϵ≤ϵm​a​x\\epsilon\\leq\\epsilon\_\{max\}, one eventually gets

n∗=⌈log1−q⁡ϵc​ϕm​a​x\+nm​i​n−1⌉\.n\_\{\*\}=\\left\\lceil\\log\_\{1\-q\}\\frac\{\\epsilon\}\{c\\phi\_\{max\}\}\+n\_\{min\}\-1\\right\\rceil\.\(41\)The value ofccandϕm​a​x\\phi\_\{max\}depend on the score that one wishes to compute fromKK\. Howeverc≤2c\\leq 2andϕ​\(n\)≤1\\phi\(n\)\\leq 1independently of the score\. Therefore, a simple upper bound ofn∗n\_\{\*\},n∗′n\_\{\*\}^\{\\prime\}is obtained by settingc=2c=2andϕm​a​x=1\\phi\_\{max\}=1in Eq\.[41](https://arxiv.org/html/2607.06542#A0.E41), which yields

n∗′=⌈log1−q⁡ϵ2\+nm​i​n−1⌉\.n\_\{\*\}^\{\\prime\}=\\left\\lceil\\log\_\{1\-q\}\\frac\{\\epsilon\}\{2\}\+n\_\{min\}\-1\\right\\rceil\.
\\oldappendixsection

The distribution of sentence length in PUD

The distribution of sentence length in PUD is shown in Figure[7](https://arxiv.org/html/2607.06542#A0.F7)\.

![Refer to caption](https://arxiv.org/html/2607.06542v1/x7.png)Figure 7:The empirical distribution of sentence lengths for selected human languages in the PUD collection\. On top of each subfigure the languages is shown\. Each language corresponds to a distinct linguistic family \(Table[3](https://arxiv.org/html/2607.06542#S3.T3)\)\. The dotted line shows the best fit of a 2\-parameter geometric distribution \(Eq\.[10](https://arxiv.org/html/2607.06542#S2.E10)\) with parametersnm​i​n=2n\_\{min\}=2andq=\(S−1\)/S⟨n⟩\+1−1/Sq=\\frac\{\(S\-1\)/S\}\{\\left<n\\right\>\+1\-1/S\}whereSSis the number of sequences and⟨n⟩\\left<n\\right\>is the average sequence length \(Appendix[5\.3](https://arxiv.org/html/2607.06542#S5.SS3)\)\.\\oldappendixsection

Performance in PUD without sentence length limit

Table 9:The performance scores𝔼⁡\[Pct\]\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{t\}\],𝔼⁡\[Q\]\\operatorname\{\\mathbb\{E\}\}\[Q\],𝔼⁡\[Pce\]\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{e\}\]on human languages in the PUD collection with no limit on sentence length\. Format is the same as in Table[4\.2](https://arxiv.org/html/2607.06542#S4.SS2)\.Table 10:The performance scores𝔼⁡\[Pct\]\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{t\}\],𝔼⁡\[Q\]\\operatorname\{\\mathbb\{E\}\}\[Q\],𝔼⁡\[Pce\]\\operatorname\{\\mathbb\{E\}\}\[P\_\{c\}^\{e\}\]on human languages in the PUD collection with no limit on sentence length\. Format is the same as in Table[4\.2](https://arxiv.org/html/2607.06542#S4.SS2)\.###### Acknowledgements\.

We are grateful to L\. Màrquez and L\. Padró for helpful discussions\. We are also grateful to M\. Mora for advice on mathematical calculations and to L\. Alemany\-Puig for assistance in the generation of the preprocessed PUD treebanks\. RFC is supported by the grant PID2024\-155946NB\-I00 funded by Ministerio de Ciencia, Innovación y Universidades \(MICIU\), Agencia Estatal de Investigación \(AEI/10\.13039/501100011033\) and the European Social Fund Plus \(ESF\+\)\. CH is supported by the grant 802719 funded by the European Union’s 8th Framework Programme \(Horizon 2020\) and by the gran TWCF\-2024\-33965 from the Templeton World Charity Foundation\.

## References

- Alemany\-Puig and Ferrer\-i\-Cancho \(2024\)Alemany\-Puig, Luís and Ramon Ferrer\-i\-Cancho\. 2024\.The expected sum of edge lengths in planar linearizations of trees\.*Journal of Language Modelling*, 12\(1\):1–42\.
- Altmann \(1965\)Altmann, Stuart A\. 1965\.Sociobiology of rhesus monkeys\. II: Stochastics of social communication\.*J\. Theor\. Biol\.*, 8:490–522\.
- Blasi et al\. \(2022\)Blasi, Damián E\., Joseph Henrich, Evangelia Adamou, David Kemmerer, and Asifa Majid\. 2022\.Over\-reliance on English hinders cognitive science\.*Trends in Cognitive Sciences*, 26\(12\):1153–1170\.
- Campos et al\. \(2016\)Campos, Daniel, Frederic Bartumeus, Vicenç Méndez, José S\. Andrade, and Xavier Espadaler\. 2016\.Variability in individual activity bursts improves ant foraging success\.*Journal of The Royal Society Interface*, 13\(125\):20160856\.
- Carroll \(2014\)Carroll, John\. 2014\.Parsing\.In*The Oxford Handbook of Computational Linguistics*\. Oxford University Press\.
- Cayley \(1889\)Cayley, Arthur\. 1889\.A theorem on trees\.*Quart\. J\. Math*, 23:376–378\.
- Ferrer\-i\-Cancho et al\. \(2022\)Ferrer\-i\-Cancho, Ramon, Carlos Gómez\-Rodríguez, Juan Luis Esteban, and Lluís Alemany\-Puig\. 2022\.Optimality of syntactic dependency distances\.*Physical Review E*, 105\(1\):014308\.
- Ferrer\-i\-Cancho and Lusseau \(2006\)Ferrer\-i\-Cancho, Ramon and David Lusseau\. 2006\.Long\-term correlations in the surface behavior of dolphins\.*Europhysics Letters*, 74\(6\):1095–1101\.
- Ferrer\-i\-Cancho and McCowan \(2012\)Ferrer\-i\-Cancho, Ramon and B\. McCowan\. 2012\.The span of dependencies in dolphin whistle sequences\.*Journal of Statistical Mechanics*, page P06002\.
- Frank and Christiansen \(2018\)Frank, Stefan L\. and Morten H\. Christiansen\. 2018\.Hierarchical and sequential processing of language\.*Language, Cognition and Neuroscience*, 33\(9\):1213–1218\.
- Furuhashi and Hayakawa \(2012\)Furuhashi, Sho and Yoshinori Hayakawa\. 2012\.Lognormality of the distribution of Japanese sentence lengths\.*Journal of the Physical Society of Japan*, 81\(3\):034004\.
- Gerdes et al\. \(2018\)Gerdes, Kim, Bruno Guillaume, Sylvain Kahane, and Guy Perrier\. 2018\.SUD or surface\-syntactic universal dependencies: An annotation scheme near\-isomorphic to UD\.In*Proceedings of the Second Workshop on Universal Dependencies \(UDW 2018\)*, pages 66–74, Association for Computational Linguistics, Brussels, Belgium\.
- Girard\-Buttoz et al\. \(2022\)Girard\-Buttoz, Cédric, Emiliano Zaccarella, Tatiana Bortolato, Angela D\. Friederici, Roman M\. Wittig, and Catherine Crockford\. 2022\.Chimpanzees produce diverse vocal sequences with ordered and recombinatorial properties\.*Communications Biology*, 5\(1\)\.
- Grund et al\. \(2023\)Grund, Charlotte, Gal Badihi, Kirsty E\. Graham, Alexandra Safryghin, and Catherine Hobaiter\. 2023\.Gesturalorigins: A bottom\-up framework for establishing systematic gesture data across ape species\.*Behavior Research Methods*\.
- Grund, Robbins, and Hobaiter \(2025\)Grund, Charlotte, Martha M\. Robbins, and Catherine Hobaiter\. 2025\.The gestural repertoire of Bwindi mountain gorillas \(Gorilla beringei beringei\): gesture form and frequency of use\.*Animal Cognition*, 28\(1\)\.
- Gustison \(2017\)Gustison, Morgan\. 2017\.*The phylogeny and function of vocal complexity in geladas*\.Phd thesis, University of Michigan, Michigan, USA\.
- Gustison et al\. \(2016\)Gustison, Morgan L\., Stuart Semple, Ramon Ferrer\-i\-Cancho, and Thore Bergman\. 2016\.Gelada vocal sequences follow Menzerath’s linguistic law\.*Proceedings of the National Academy of Sciences USA*, 13\(19\):E2750–E2758\.
- Han et al\. \(2020\)Han, Wenjuan, Yong Jiang, Hwee Tou Ng, and Kewei Tu\. 2020\.A survey of unsupervised dependency parsing\.In*Proceedings of the 28th International Conference on Computational Linguistics*, pages 2522–2533, International Committee on Computational Linguistics, Barcelona, Spain \(Online\)\.
- Hobaiter, Byrne, and Zuberbühler \(2017\)Hobaiter, C\., R\. W\. Byrne, and K\. Zuberbühler\. 2017\.Wild chimpanzees’ use of single and combined vocal and gestural signals\.*Behavioral Ecology and Sociobiology*, 71\(6\)\.
- Hobaiter and Byrne \(2011\)Hobaiter, Catherine and Richard W\. Byrne\. 2011\.Serial gesturing by wild chimpanzees: its nature and function for communication\.*Animal Cognition*, 14\(6\):827–838\.
- Kershenbaum et al\. \(2016\)Kershenbaum, Arik, Daniel T\. Blumstein, Marie A\. Roch, Çağlar Akçay, Gregory Backus, Mark A\. Bee, Kirsten Bohn, Yan Cao, Gerald Carter, Cristiane Cäsar, Michael Coen, Stacy L\. DeRuiter, Laurance Doyle, Shimon Edelman, Ramon Ferrer\-i Cancho, Todd M\. Freeberg, Ellen C\. Garland, Morgan Gustison, Heidi E\. Harley, Chloé Huetz, Melissa Hughes, Julia Hyland Bruno, Amiyaal Ilany, Dezhe Z\. Jin, Michael Johnson, Chenghui Ju, Jeremy Karnowski, Bernard Lohr, Marta B\. Manser, Brenda McCowan, Eduardo Mercado, Peter M\. Narins, Alex Piel, Megan Rice, Roberta Salmi, Kazutoshi Sasahara, Laela Sayigh, Yu Shiu, Charles Taylor, Edgar E\. Vallejo, Sara Waller, and Veronica Zamora\-Gutierrez\. 2016\.Acoustic sequences in non\-human animals: a tutorial review and prospectus\.*Biological Reviews*, 91\(1\):13–52\.
- Kershenbaum et al\. \(2014\)Kershenbaum, Arik, Ann E\. Bowles, Todd M\. Freeberg, Dezhe Z\. Jin, Adriano R\. Lameira, and Kirsten Bohn\. 2014\.Animal vocal sequences: not the markov chains we thought they were\.*Proceedings of the Royal Society B: Biological Sciences*, 281\(1792\):20141370\.
- Klein and Manning \(2004\)Klein, Dan and Christopher Manning\. 2004\.Corpus\-based induction of syntactic structure: Models of dependency and constituency\.In*Proceedings of the 42nd Annual Meeting of the Association for Computational Linguistics \(ACL\-04\)*, pages 478–485, Barcelona, Spain\.
- Liebal, Call, and Tomasello \(2004\)Liebal, Katja, Josep Call, and Michael Tomasello\. 2004\.Use of gesture sequences in chimpanzees\.*American Journal of Primatology*, 64\(4\):377–396\.
- London and Pluhár \(2023\)London, András and András Pluhár\. 2023\.Intersection of random spanning trees in complex networks\.*Applied Network Science*, 8\(1\)\.
- Marecek \(2012\)Marecek, David\. 2012\.*Unsupervised Dependency Parsing*\.Ph\.D\. thesis, Charles University in Prague\.
- Marecek \(2016\)Marecek, David\. 2016\.Twelve years of unsupervised dependency parsing\.In*Proceedings of the 16th ITAT Conference Information Technologies \- Applications and Theory, Tatranské Matliare, Slovakia, September 15\-19, 2016*, volume 1649 of*CEUR Workshop Proceedings*, pages 56–62, CEUR\-WS\.org\.
- Martín Rodríguez et al\. \(2022\)Martín Rodríguez, Lorena, Tatiana Merzhevich, Wellington Silva, Tiago Tresoldi, Carolina Aragon, and Fabrício F\. Gerardi\. 2022\.Tupían language ressources: Data, tools, analyses\.In*Proceedings of the 1st Annual Meeting of the ELRA/ISCA Special Interest Group on Under\-Resourced Languages*, pages 48–58, European Language Resources Association, Marseille, France\.
- McCowan, Hanser, and Doyle \(1999\)McCowan, Brenda, Sean F\. Hanser, and Laurance R\. Doyle\. 1999\.Quantitative tools for comparing animal communication systems: information theory applied to bottlenose dolphin whistle repertoires\.*Animal Behaviour*, 57:409–419\.
- McDonald et al\. \(2005\)McDonald, Ryan, Fernando Pereira, Kiril Ribarov, and Jan Hajič\. 2005\.Non\-projective dependency parsing using spanning tree algorithms\.In*Proceedings of the Conference on Human Language Technology and Empirical Methods in Natural Language Processing*, HLT ’05, pages 523–530, Association for Computational Linguistics, Stroudsburg, PA, USA\.
- Mel’čuk \(1988\)Mel’čuk, Igor\. 1988\.*Dependency syntax: theory and practice*\.State of New York University Press, Albany\.
- Mielke et al\. \(2024a\)Mielke, Alexander, Gal Badihi, Ed Donnellan, Kirsty E\. Graham, Chie Hashimoto, Joseph G\. Mine, Alex K\. Piel, Alexandra Safryghin, Katie E\. Slocombe, Adrian Soldati, Fiona A\. Stewart, Simon W\. Townsend, Claudia Wilke, Klaus Zuberbühler, Chiara Zulberti, and Catherine Hobaiter\. 2024a\.Predictability of next elements in chimpanzee gesture sequences\.*bioRxiv*\.
- Mielke et al\. \(2024b\)Mielke, Alexander, Gal Badihi, Kirsty E\. Graham, Charlotte Grund, Chie Hashimoto, Alex K\. Piel, Alexandra Safryghin, Katie E\. Slocombe, Fiona Stewart, Claudia Wilke, Klaus Zuberbühler, and Catherine Hobaiter\. 2024b\.Many morphs: Parsing gesture signals from the noise\.*Behavior Research Methods*, 56\(7\):6520–6537\.
- Mine et al\. \(2024\)Mine, Joseph G\., Claudia Wilke, Chiara Zulberti, Melika Behjati, Alexandra B\. Bosshard, Sabine Stoll, Zarin P\. Machanda, Andri Manser, Katie E\. Slocombe, and Simon W\. Townsend\. 2024\.Vocal\-visual combinations in wild chimpanzees\.*Behavioral Ecology and Sociobiology*, 78\(10\)\.
- Newman \(2010\)Newman, Mark E\. J\. 2010\.*Networks\. An introduction*\.Oxford University Press, Oxford\.
- Park and Wang \(2023\)Park, Chanseok and Min Wang\. 2023\.A study on the g and h control charts\.*Communications in Statistics \- Theory and Methods*, 52\(20\):7334–7349\.
- Petrini and Ferrer\-i\-Cancho \(2025\)Petrini, Sonia and Ramon Ferrer\-i\-Cancho\. 2025\.The distribution of syntactic dependency distances\.*Glottometrics*, 58:35–94\.
- Scheinerman \(2012\)Scheinerman, Edward R\. 2012\.*Mathematics: A Discrete Introduction*, 3rd ed\. edition\.Cengage Learning\.
- Sigurd, Eeg\-Olofsson, and van Weijer \(2004\)Sigurd, Bengt, Mats Eeg\-Olofsson, and Joost van Weijer\. 2004\.Word length, sentence length and frequency \- Zipf revisited\.*Studia Linguistica*, 58\(1\):37–52\.
- Søgaard \(2011\)Søgaard, Anders\. 2011\.From ranked words to dependency trees: two\-stage unsupervised non\-projective dependency parsing\.In*Proceedings of TextGraphs\-6: Graph\-based Methods for Natural Language Processing*, pages 60–68, Association for Computational Linguistics, Portland, Oregon\.
- Spitkovsky, Alshawi, and Jurafsky \(2010\)Spitkovsky, Valentin I\., Hiyan Alshawi, and Daniel Jurafsky\. 2010\.From baby steps to leapfrog: How “less is more” in unsupervised dependency parsing\.In*Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics*, pages 751–759, Association for Computational Linguistics, Los Angeles, California\.
- Tu and Honavar \(2011\)Tu, Kewei and Vasant Honavar\. 2011\.On the utility of curricula in unsupervised learning of probabilistic grammars\.In*Proceedings of the Twenty\-Second International Joint Conference on Artificial Intelligence \- Volume Volume Two*, IJCAI’11, page 1523–1528, AAAI Press\.
- Vasquez et al\. \(2018\)Vasquez, Alonso, Renzo Ego Aguirre, Candy Angulo, John Miller, Claudia Villanueva, Željko Agić, Roberto Zariquiey, and Arturo Oncevay\. 2018\.Toward Universal Dependencies for Shipibo\-konibo\.In*Proceedings of the Second Workshop on Universal Dependencies \(UDW 2018\)*, pages 151–161, Association for Computational Linguistics, Brussels, Belgium\.
- Yuret \(1998\)Yuret, D\. 1998\.*Discovery of linguistic relations using lexical attraction*\.Ph\.D\. thesis, Massachusets Institute of Technology, USA\.
- Zeman et al\. \(2020\)Zeman, Daniel, Joakim Nivre, Mitchell Abrams, Elia Ackermann, Noëmi Aepli, Željko Agić, Lars Ahrenberg, Chika Kennedy Ajede, Gabrielė Aleksandravičiūtė, Lene Antonsen, et al\. 2020\.Universal dependencies 2\.6\.LINDAT/CLARIAH\-CZ digital library at the Institute of Formal and Applied Linguistics \(ÚFAL\), Faculty of Mathematics and Physics, Charles University\.