The syntactic structure of a sentence is often represented using syntactic
dependency trees. The sum of the distances between syntactically related words
has been in the limelight for the past decades. Research on dependency
distances led to the formulation of the principle of dependency distance
minimization whereby words in sentences are ordered so as to minimize that sum.
Numerous random baselines have been defined to carry out related quantitative
studies on languages. The simplest random baseline is the expected value of the
sum in unconstrained random permutations of the words in the sentence, namely
when all the shufflings of the words of a sentence are allowed and equally
likely. Here we focus on a popular baseline: random projective permutations of
the words of the sentence, that is, permutations where the syntactic dependency
structure is projective, a formal constraint that sentences satisfy often in
languages. Thus far, the expectation of the sum of dependency distances in
random projective shufflings of a sentence has been estimated approximately
with a Monte Carlo procedure whose cost is of the order of $Rn$, where $n$ is
the number of words of the sentence and $R$ is the number of samples; it is
well known that the larger $R$, the lower the error of the estimation but the
larger the time cost. Here we present formulae to compute that expectation
without error in time of the order of $n$. Furthermore, we show that star trees
maximize it, and give an algorithm to retrieve the trees that minimize it.

本文提供一种新的算法来计算句子的依存距离期望值，在统计上足够准确，时间复杂度为 $n$。此外，文章还发现了星形树（star tree）在该算法中具有最大化作用，提出了一种可以找到最小化依存距离期望值的树的算法。