Finite Version of the q q -Analogue of de Finetti’s Theorem
Adyan Dordzhiev · 2025
Read Finite Version of the q q -Analogue of de Finetti’s Theorem by Adyan Dordzhiev (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-01176.txt.
Introduction
Adyan Dordzhiev proves a finite form, in a 2025 preprint, of a deformed version of de Finetti's theorem. The classic theorem says an endlessly exchangeable random sequence is a blend of independent, identical draws. A q-analogue replaces plain symmetry with a deformed one, tuned by a parameter q between zero and one. Dordzhiev states an asymptotic version of that analogue. The proof leans on the convex shape of the set of q-exchangeable probability measures.
The main payoff is a sharp speed limit. The gap between a finite q-exchangeable law and its limiting blend shrinks at a rate of exact order q to the n. No better rate is possible in general. Results of this kind matter wherever symmetry arguments justify simple models for complex data. The finite rate tells users how much data the idealization needs before it can be trusted.
Catalog record
| CREATOR | Adyan Dordzhiev |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 22 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-01176
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Finite Version of the q q -Analogue of de Finetti’s Theorem Adyan Dordzhiev Abstract . Let q ∈ ( 0 , 1 ) q\in(0,1) . We formulate an asymptotic version of the q q -analogue of de Finetti’s theorem. Using the convex structure of the space of q q -exchangeable probability measures, we show that the optimal rate of convergence is of order q n q^{n} . 1. Introduction Let S(\infty) denote the group of permutations of the natural numbers that move only finitely many elements. A random sequence X_{1},X_{2},X_{3},\ldots is exchangeable if permuting finitely many indices does not change the law of the sequence. That is, for any finite permutation \sigma\in S(\infty) , (X_{1},X_{2},X_{3},\ldots)\overset{d}{=}(X_{\sigma(1)},X_{\sigma(2)},X_{\sigma(3)},\ldots). The celebrated de Finetti’s theorem states that an infinite random \{0,1\} -valued exchangeable sequence is a mixture of i.i.d. Bernoulli sequences. In other words, the space of exchangeable probability measures on \{0,1\}^{\infty} is isomorphic (as a convex set) to the space of all Borel probability measures on [0,1] . The isomorphism is given by the following formula (1.0.1) \mathbb{P}(X_{1}=1,\ldots,X_{k}=1,X_{k+1}=0,\ldots,X_{n}=0)\coloneqq\int_{0}^{1}p^{k}(1-p)^{n-k}\mu(dp). 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 ] . In [ GO09 ] , [ GO10 ] a deformation of the concept of classical exchangeability was studied. Definition 1.0.2 . For q>0 , a probability measure \mathbb{P} on \{0,1\}^{\infty} is q -exchangeable if for any \varepsilon_{1},\ldots,\varepsilon_{n}\in\{0,1\}^{\infty} and elementary transposition (i,i+1) , (1.0.3) \mathbb{P}(\varepsilon_{1},\ldots,\varepsilon_{i-1},\varepsilon_{i+1},\varepsilon_{i},\varepsilon_{i+2},\ldots,\varepsilon_{n})=q^{\varepsilon_{i}-\varepsilon_{i+1}}\mathbb{P}(\varepsilon_{1},\ldots,\varepsilon_{n}). In other words, each additional inversion introduces an exponential penalty governed by the parameter q . For q\in(0,1) , a q -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 \{0,1\}^{\infty} 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 \{0,1\}^{n} as n\to\infty . It was shown in [ DF80 ] that this convergence occurs at an optimal rate of order 1/n . In this note, we obtain a finite version of the q -analogue of de Finetti’s theorem, in the spirit of [ DF80 ] , with convergence at the sharp rate of order q^{n} . Acknowledgments. I am deeply grateful to Grigori Olshanski for suggesting the problem and for his guidance throughout this work. 2. Preliminaries 2.1. q -Exchangeability Assume q\in(0,1) . We use the standard notation for the q -integer, q -factorial, q -binomial coefficient, and q -Pochhammer symbol, respectively, [n]\coloneqq\frac{1-q^{n}}{1-q},\;\;[n]!\coloneqq[1]\cdot[2],\ldots\cdot[n],\;\;\genfrac{[}{]}{0.0pt}{}{n}{k}\coloneqq\dfrac{[n]!}{[k]![n-k]!}, (x;q)_{n}\coloneqq\prod_{i=0}^{n-1}(1-xq^{i}),\;\;0\leqslant n\leqslant\infty, where (x;q)_{0}\coloneqq 1 . Since q\in(0,1) , the q -Pochhammer symbol is well-defined for n=\infty . For a given finite sequence \omega\in\{0,1\}^{n} , consider the number of inversions in \omega \mathrm{inv}(\omega):=\#\{(i,j):1\leq i<j\leq n\ \text{and}\ \omega_{i}>\omega_{j}\}. Denote by C_{n,k}:=\{\omega\in\{0,1\}^{n}:\sum_{i=1}^{n}\omega_{i}=k\} the set of all binary sequences of length n containing exactly k ones. Consider the sequence s_{n,k}:=(1,1,\ldots,1,0,0,\ldots,0) in C_{n,k} , which has ones in the first k positions and zeros in the remaining n-k positions. This sequence has the largest number of inversions in C_{n,k} . Each q -exchangeable measure \mathbb{P} on \{0,1\}^{n} is defined by the following equation (2.1.1) {\mathbb{P}}(\sigma\cdot\omega)=q^{\text{inv}(\omega)-\text{inv}(\sigma\cdot\omega)}{\mathbb{P}}(\omega),\quad\omega\in\{0,1\}^{n},\sigma\in S(n). In particular, each q -exchangeable measure on \{0,1\}^{n} is determined by its values on the family of sequences \{s_{n,k}\}_{n,k} , since (2.1.2) \mathbb{P}(\omega)=q^{\mathrm{inv}(\omega)}\,\mathbb{P}(s_{n,k}),\quad\omega\in C_{n,k}. Note that equation ( 2.1.1 ) can be extended to the case where \omega\in\{0,1\}^{\infty} and \sigma\in S(\infty) . It is still equivalent to ( 1.0.3 ), since the difference \mathrm{inv}(\omega)-\mathrm{inv}(\sigma\cdot\omega) is finite whenever \sigma\in S(\infty) . We now prove a useful property of the function \text{inv}(\omega) . Proposition 2.1.3 . (2.1.4) \sum_{\omega\in C_{n,k}}q^{\text{inv}(\omega)}=\genfrac{[}{]}{0.0pt}{}{n}{k}. Proof. The q -binomial coefficient is uniquely determined by the following recurrence relation \genfrac{[}{]}{0.0pt}{}{n}{k}=q^{k}\genfrac{[}{]}{0.0pt}{}{n-1}{k}+\genfrac{[}{]}{0.0pt}{}{n-1}{k-1}. By forgetting the last entry in each sequence, we obtain the decomposition C_{n,k}=C_{n-1,k-1}\sqcup C_{n-1,k}, and as a result, we have \sum_{\omega\in C_{n,k}}q^{\mathrm{inv}(\omega)}=q^{k}\sum_{\omega\in C_{n-1,k}}q^{\mathrm{inv}(\omega)}+\sum_{\omega\in C_{n-1,k-1}}q^{\mathrm{inv}(\omega)}. This identity coincides with the recurrence relation defining the q -binomial coefficient. ∎ In [ GO09 ] , a q -analogue of de Finetti’s theorem was established. Consider the q -analogue of the interval [0,1] \Delta_{q}\coloneqq\{1,q,q^{2},\ldots\}\cup\{0\}. For each x\in\Delta_{q} , we define a q -analogue of the Bernoulli measure \nu^{q}_{x} on \{0,1\}^{\infty} and \{0,1\}^{n} as the unique q -exchangeable measure whose values on standard cylinder sets are assigned according to the formula (2.1.5) \nu^{q}_{x}(X_{1}=1,\ldots,X_{k}=1,X_{k+1}=0,\ldots,X_{n}=0)\coloneqq q^{-k(n-k)}x^{n-k}(x;q^{-1})_{k}. Interpreting x\in\Delta_{q} as the probability of a zero, the polynomial defined in ( 2.1.5 ) plays the role of a q -analogue for the binomial term x^{k}(1-x)^{n-k} . Theorem 2.1.6 . (Gnedin-Olshanski) q -exchangeable probability measures on \{0,1\}^{\infty} are in one-to-one correspondence with probability measures on \Delta_{q} . The bijection has the form (2.1.7) \mathbb{P}\coloneqq\int_{\Delta_{q}}\nu^{q}_{x}\,\mu(dx), The classical version corresponds to the limit q\to 1 . As q increases, the set \Delta_{q} becomes denser, and at q=1 , it fills the entire interval [0,1] . 2.2. Finite form of classical version We recall the main result from [ DF80 ] . Given a probability measure \mu on [0,1] , define a probability measure \mathbb{P}_{\mu,n} on \{0,1\}^{n} as (2.2.1) \mathbb{P}_{\mu,n}(A)\coloneqq\int_{0}^{1}\nu_{p}(A)\mu(dp),\quad A\subset\{0,1\}^{n}, where \nu_{p} denotes the Bernoulli measure on \{0,1\}^{n}. Recall that the map \mu\mapsto{\mathbb{P}}_{\mu,n} is not surjective. Let \pi_{k} denote the canonical projection from \{0,1\}^{n} onto its first k coordinates, and let \mathbb{P}_{k} denote the pushforward of \mathbb{P} under \pi_{k} . Clearly, (\mathbb{P}_{\mu,n})_{k}=\mathbb{P}_{\mu,k} . The variational distance between two probability measures \mu and \nu on (\Omega,\mathcal{F}) is defined as \|\mu-\nu\|\coloneqq 2\,\sup\limits_{A\in\mathcal{F}}|\mu(A)-\nu(A)|. Theorem 2.2.2 . (Diaconis-Freedman) Let \mathbb{P} be an exchangeable measure on \{0,1\}^{n} . Then there exists a probability measure \mu on [0,1] such that (2.2.3) \|\mathbb{P}_{k}-\mathbb{P}_{\mu,k}\|\leqslant\frac{4k}{n},\quad\text{for all }k\leqslant n, and this rate of convergence is sharp. 2.3. Extreme measures The spaces of exchangeable and q -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 \Omega=\{0,1\}^{\infty} . The extreme points of the set of exchangeable probability measures on \Omega are precisely the Bernoulli measures \nu_{p} , with p\in[0,1] . For q -exchangeable measures, the extreme ones are parametrized by x\in\Delta_{q} and are given by the measures \nu^{q}_{x} defined in ( 2.1.5 ). (2) Let \Omega=\{0,1\}^{n} . In this case, the sets of extreme exchangeable and q -exchangeable measures are finite. The extreme q -exchangeable measures, denoted by e^{q}_{0},e^{q}_{1},\ldots,e^{q}_{n} , are given by the formula \displaystyle e^{q}_{k}(\omega) \displaystyle=\begin{cases}q^{\text{inv}(\omega)}\dfrac{1}{\genfrac{[}{]}{0.0pt}{}{n}{k}},&\text{if }\omega\text{ contains }k\text{ ones and }n-k\text{ zeros},\\ 0,&\text{otherwise.}\end{cases} Setting q=1 , we obtain the extreme measures in the classical exchangeable case. Proof. Claim (1) follows immediately from the bijections in ( 1.0.1 ) and ( 2.1.7 ). For Claim (2), note that due to q -exchangeability, the probability depends only on the number of ones, up to the scalar factor q^{\operatorname{inv}(\omega)} . This shows that each e^{q}_{k} is extreme. ∎ Fix n_{1}\leqslant n . For the extreme measure e^{q}_{n,n_{1}} and the measure \nu^{q}_{x} with parameter x=q^{n_{1}} , we compute the probabilities in ( 2.3.3 ) and ( 2.3.4 ), corresponding to the