Finite Version of the -Analogue of de Finettiβs Theorem
Abstract.
Let . We formulate an asymptotic version of the -analogue of de Finettiβs theorem. Using the convex structure of the space of -exchangeable probability measures, we show that the optimal rate of convergence is of order .
1. Introduction
Let denote the group of permutations of the natural numbers that move only finitely many elements. A random sequence is exchangeable if permuting finitely many indices does not change the law of the sequence. That is, for any finite permutation ,
The celebrated de Finettiβs theorem states that an infinite random -valued exchangeable sequence is a mixture of i.i.d. Bernoulli sequences. In other words, the space of exchangeable probability measures on is isomorphic (as a convex set) to the space of all Borel probability measures on . The isomorphism is given by the following formula
(1.0.1) |
De Finettiβs theorem can be extended to more general settings [HS55]. The theorem can be proved by establishing a connection with the Hausdorff moment problem [Fel71]. Another proof can be obtained by the moment method [Kir18]. There is also an alternative approach based on harmonic functions on the Pascal graph [BO16].
Definition 1.0.2.
For , a probability measure on is -exchangeable if for any and elementary transposition ,
(1.0.3) |
In other words, each additional inversion introduces an exponential penalty governed by the parameter . For , a -analogue of de Finettiβs theorem for this type of probability measures has been established in [GO09]. See section (2.1) for a detailed discussion.
The infinite nature of the phase space plays a crucial role in both formulations, see the introduction of [DF80] for a counterexample. However, de Finettiβs theorem can also be obtained as a limit of the finite version as . It was shown in [DF80] that this convergence occurs at an optimal rate of order . In this note, we obtain a finite version of the -analogue of de Finettiβs theorem, in the spirit of [DF80], with convergence at the sharp rate of order .
Acknowledgments. I am deeply grateful to Grigori Olshanski for suggesting the problem and for his guidance throughout this work.
2. Preliminaries
2.1. -Exchangeability
Assume . We use the standard notation for the -integer, -factorial, -binomial coefficient, and -Pochhammer symbol, respectively,
where . Since , the -Pochhammer symbol is well-defined for .
For a given finite sequence , consider the number of inversions in
Denote by the set of all binary sequences of length containing exactly ones. Consider the sequence in , which has ones in the first positions and zeros in the remaining positions. This sequence has the largest number of inversions in . Each -exchangeable measure on is defined by the following equation
(2.1.1) |
In particular, each -exchangeable measure on is determined by its values on the family of sequences , since
(2.1.2) |
Note that equation (2.1.1) can be extended to the case where and . It is still equivalent to (1.0.3), since the difference is finite whenever .
We now prove a useful property of the function .
Proposition 2.1.3.
(2.1.4) |
Proof.
The -binomial coefficient is uniquely determined by the following recurrence relation
By forgetting the last entry in each sequence, we obtain the decomposition
and as a result, we have
This identity coincides with the recurrence relation defining the -binomial coefficient.
β
In [GO09], a -analogue of de Finettiβs theorem was established. Consider the -analogue of the interval
For each , we define a -analogue of the Bernoulli measure on and as the unique -exchangeable measure whose values on standard cylinder sets are assigned according to the formula
(2.1.5) |
Interpreting as the probability of a zero, the polynomial defined in (2.1.5) plays the role of a -analogue for the binomial term .
Theorem 2.1.6.
(Gnedin-Olshanski) -exchangeable probability measures on are in one-to-one correspondence with probability measures on . The bijection has the form
(2.1.7) |
The classical version corresponds to the limit . As increases, the set becomes denser, and at , it fills the entire interval .
2.2. Finite form of classical version
We recall the main result from [DF80]. Given a probability measure on , define a probability measure on as
(2.2.1) |
where denotes the Bernoulli measure on Recall that the map is not surjective.
Let denote the canonical projection from onto its first coordinates, and let denote the pushforward of under . Clearly, . The variational distance between two probability measures and on is defined as
Theorem 2.2.2.
(Diaconis-Freedman) Let be an exchangeable measure on . Then there exists a probability measure on such that
(2.2.3) |
and this rate of convergence is sharp.
2.3. Extreme measures
The spaces of exchangeable and -exchangeable probability measures are convex and compact; hence, by Choquetβs theorem, they are the closed convex hulls of their extreme points.
Proposition 2.3.1.
-
(1)
Let . The extreme points of the set of exchangeable probability measures on are precisely the Bernoulli measures , with . For -exchangeable measures, the extreme ones are parametrized by and are given by the measures defined in (2.1.5).
-
(2)
Let . In this case, the sets of extreme exchangeable and -exchangeable measures are finite. The extreme -exchangeable measures, denoted by , are given by the formula
Setting , we obtain the extreme measures in the classical exchangeable case.
Fix . For the extreme measure and the measure with parameter , we compute the probabilities in (2.3.3) and (2.3.4), corresponding to the event that the first entries of the sequence begin with exactly ones.
Proposition 2.3.2.
(2.3.3) |
(2.3.4) |
Proof.
3. Finite Form
3.1. Main result
In this section, we formulate an asymptotic version of Theorem (2.1.6) in the sense of Theorem (2.2.2). Abusing notation, for a probability measure on , we denote by the probability measure given by
where denotes a probability measure on defined by (2.1.5).
Theorem 3.1.1.
Let be an -exchangeable probability measure on . Then there exists a probability measure on such that
(3.1.2) |
where is a constant depending only on .
The convergence rate of order is sharp, as will be shown in Section 3.4. For convenience, we do not write the constant explicitly, only its existence is relevant for our purposes. Using the convex structure of the space of -exchangeable measures, we reduce the proof of Theorem (3.1.1) to the case of an extreme measure.
Lemma 3.1.3.
Fix . In the notation of Theorem (3.1.1), consider the extreme measure and the probability measure . Then
(3.1.4) |
where is a constant depending only on .
3.2. Extreme case
In this section, we prove Lemma (3.1.3).
Proof.
The variational distance (3.1.4) between the corresponding pushforward measures can be computed as follows
where the second identity follows from the -exchangeability property, the third from Proposition (2.1.4), and the fourth from Proposition (2.3.3). It follows that it suffices to analyse the expression
(3.2.1) |
We consider two cases: and .
Case 1: . In this case, (3.2.1) reduces to
(3.2.2) | ||||
since and , we obtain the estimate
(3.2.3) |
applying the inequality for , we get
(3.2.4) |
Hence, the upper bound for (3.2.2) is proportional to , with the constant depending only on .
Case 2: . In this case, expression (3.2.1) can be rewritten as
(3.2.5) |
The expression (3.2.5) depends on the sign of the difference in the numerator
(3.2.6) |
If , then we have
(3.2.7) |
since , the upper bound for (3.2.7) is
applying the same inequalities as in Case 1, we estimate the entire expression by (3.2.4)
In the case when , we write
(3.2.8) |
since , the upper bound becomes
(3.2.9) |
applying the same inequalities as in Case 1, we estimate the entire expression by
(3.2.10) |
since , we obtain a uniform bound with respect to the parameter
(3.2.11) |
In each of the two cases, the upper bound is of order , with the constant depending only on and .
Combining the two cases, we conclude that the overall bound is of the form , where is a constant depending only on . This completes the proof of the lemma.
β
3.3. From finite to infinite
Since the set is compact, the probability measures on are uniquely determined by sequences of their moments. Therefore, injectivity of the map (2.1.7) is automatic. Using Theorem (3.1.1), we prove the surjectivity of the map (2.1.7), thereby rederiving the result of GnedinβOlshanski (2.1.7).
Corollary 3.3.1.
The map (2.1.7) is surjective.
Proof.
Let be a -exchangeable probability measure on . Consider the natural projections onto . From Theorem (3.1.1) we obtain a family of measures . By compactness of the space of probability measures on , we can extract subsequence that converges weakly to a probability measure . Consequently, we obtain the weak convergence Since , we have for all . We conclude that .
β
3.4. The rate is sharp
We provide an example in which the lower bound for the variational distance in Theorem (3.1.1) is of order , confirming that this rate is optimal. The example is given by the extreme measure and the measure with parameter . We begin by proving a technical lemma.
Lemma 3.4.1.
(3.4.2) |
Proof.
Since for , we have
(3.4.3) |
therefore,
(3.4.4) |
Since for , it follows that
(3.4.5) |
β
Proposition 3.4.6.
For , we have
(3.4.7) |
where is a constant depending only on .
Proof.
As we have already shown, the variational distance between and can be computed using the following formula
Since , we have . To obtain a lower bound, we consider only the term corresponding to in the sum.
Using the inequality and Lemma (3.4.1), we obtain
(3.4.8) |
Thus, we see that the lower bound is of order . β
References
- [BO16] Alexei Borodin and Grigori Olshanski. Representations of the Infinite Symmetric Group. Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2016.
- [DF80] P. Diaconis and D. Freedman. Finite Exchangeable Sequences. The Annals of Probability, 8(4):745 β 764, 1980.
- [Fel71] W. Feller. An Introduction to Probability Theory and Its Application Vol II. John Wiley and Sons, 1971.
- [GO09] Alexander Gnedin and Grigori Olshanski. A q-analogue of de Finettiβs theorem. The Electronic Journal of Combinatorics, Volume 16, Issue 1 (2009).
- [GO10] Alexander Gnedin and Grigori Olshanski. q-exchangeability via quasi-invariance. The Annals of Probability, 38(6), November 2010.
- [HS55] Edwin Hewitt and Leonard J. Savage. Symmetric Measures on Cartesian Products. Transactions of the American Mathematical Society, 80(2):470β501, 1955.
- [Kir18] Werner Kirsch. An elementary proof of de Finettiβs Theorem, 2018.