The Ajtai–Komlós–Tusnády theorem (also known as the AKT optimal matching theorem) is a result in probabilistic combinatorics. Given two random, distinct sets of points X = ( X 1 , … , X k ) {\displaystyle X=(X_{1},\dots ,X_{k})} and Y = ( Y 1 , … , Y k ) {\displaystyle Y=(Y_{1},\dots ,Y_{k})} in the unit square [ 0 , 1 ] 2 {\displaystyle [0,1]^{2}} , the theorem gives then upper and lower bounds for the minimal total distance needed to match the points in one set to those in the other. The theorem was proven in 1984 by the Hungarian mathematicians Miklós Ajtai, János Komlós, and Gábor Tusnády.
Statement Let ( X 1 , … , X k ) {\displaystyle (X_{1},\dots ,X_{k})} and ( Y 1 , … , Y k ) {\displaystyle (Y_{1},\dots ,Y_{k})} be two independent random vectors, uniformly distributed over [ 0 , 1 ] 2 {\displaystyle [0,1]^{2}} (i.e., X i ∈ [ 0 , 1 ] 2 {\displaystyle X_{i}\in [0,1]^{2}} ). Let S n {\displaystyle S_{n}} denote the symmetric group, and | ⋅ | {\displaystyle |\cdot |} the Euclidean norm on R 2 {\displaystyle \mathbb {R} ^{2}} . Then,
P ( C 1 n log n < inf σ ∈ S n ∑ k = 1 n | X k − Y σ ( k ) | < C 2 n log n ) = 1 − o ( 1 ) , {\displaystyle \mathbb {P} \left(C_{1}{\sqrt {n\log n}}<\inf \limits _{\sigma \in S_{n}}\sum \limits _{k=1}^{n}|X_{k}-Y_{\sigma (k)}|<C_{2}{\sqrt {n\log n}}\right)=1-o(1),}
where C 1 , C 2 {\displaystyle C_{1},C_{2}} are real constants.
Remarks The notation o ( 1 ) {\displaystyle o(1)} means
f ( n ) ∈ o ( 1 ) ⟺ lim n → ∞ f ( n ) = 0. {\displaystyle f(n)\in o(1)\iff \lim \limits _{n\to \infty }f(n)=0.} see Landau notation. The theorem implies that
inf σ ∈ S n 1 n ∑ k = 1 n | X k − Y σ ( k ) | ∼ log n n {\displaystyle \inf \limits _{\sigma \in S_{n}}{\frac {1}{n}}\sum \limits _{k=1}^{n}|X_{k}-Y_{\sigma (k)}|\sim {\sqrt {\frac {\log n}{n}}}}
with high probability.
Bibliography Bobkov, Sergey; Ledoux, Michel (2019). "A simple Fourier analytic proof of the AKT optimal matching theorem". Annals of Applied Probability. 31 (6). arXiv:1909.06193. doi:10.1214/20-AAP1656. Ajtai, M.; Komlós, János; Tusnády, G. (1984). "On optimal matchings". Combinatorica. 4: 259–264. doi:10.1007/BF02579135. Talagrand, Michel (1994). "Matching theorems and empirical discrepancy computations using majorizing measures". Journal of the American Mathematical Society. 7: 455–537. doi:10.1090/S0894-0347-1994-1227476-X.
References