Introduction
Longest increasing subsequences of permutations
For n ∈ N n \in\mathbb{N} n ∈ N σ ∈ S n \sigma\in\mathfrak{S}_n σ ∈ S n n n n k ≤ n k \le n k ≤ n k k k σ \sigma σ { ( i 1 , σ ( i 1 ) ) , … , ( i k , σ ( i k ) ) } \{(i_1,\sigma(i_1)),\ldots,(i_k,\sigma(i_k))\} {( i 1 , σ ( i 1 )) , … , ( i k , σ ( i k ))} i 1 < … < i k i_1 < \ldots< i_k i 1 < … < i k σ ( i 1 ) < … < σ ( i k ) \sigma(i_1) < \ldots< \sigma(i_k) σ ( i 1 ) < … < σ ( i k ) longest increasing subsequence in σ \sigma σ σ \sigma σ k k k σ \sigma σ k k k LIS ( σ ) \operatorname{LIS}(\sigma) LIS ( σ )
The LIS, for instance, provides a natural way to compare rankings through the Ulam distance ; see [13 Chapter 6, Section B, pp. 118–119] or [3 ] . Viewing permutations σ , τ ∈ S n \sigma,\tau\in\mathfrak{S}_n σ , τ ∈ S n
d U ( σ , τ ) : = n − LIS ( σ ∘ τ − 1 ) . d_U(\sigma,\tau) := n-\operatorname{LIS}\left(\sigma\circ\tau^{-1}\right). d U ( σ , τ ) := n − LIS ( σ ∘ τ − 1 ) . It is the minimum number of moves needed to transform one ranked list into the other, where a move removes a single item and reinserts it elsewhere. In particular, d U ( σ , id ) = n − LIS ( σ ) d_U(\sigma,\operatorname{id})=n-\operatorname{LIS}(\sigma) d U ( σ , id ) = n − LIS ( σ )
The study of longest increasing subsequences in random permutations was initiated by Ulam, who asked in [33 ] about the asymptotic behavior of ℓ n : = E [ LIS ( σ n ) ] \ell_n := \mathbb{E}[\operatorname{LIS}(\sigma_n)] ℓ n := E [ LIS ( σ n )] σ n \sigma_n σ n S n \mathfrak{S}_n S n [24 , 34 , 2 ] , this question has been solved at the first order:
Theorem 1.1. For each n ∈ N n \in\mathbb{N} n ∈ N σ n ∼ Unif ( S n ) \sigma_n \sim\operatorname{Unif}(\mathfrak{S}_n) σ n ∼ Unif ( S n ) 1 n LIS ( σ n ) ⟶ 2 \frac{1}{\sqrt{n}}\operatorname{LIS}(\sigma_n) \longrightarrow2 n 1 LIS ( σ n ) ⟶ 2 n → ∞ n \to\infty n → ∞ ℓ n : = E [ LIS ( σ n ) ] \ell_n := \mathbb{E}[\operatorname{LIS}(\sigma_n)] ℓ n := E [ LIS ( σ n )] ℓ n / n ⟶ 2 \ell_n/\sqrt{n} \longrightarrow2 ℓ n / n ⟶ 2 n → ∞ n \to\infty n → ∞
The next major breakthrough was brought by Baik–Deift–Johansson, who proved in [7 ] that the fluctuations of LIS ( σ n ) \operatorname{LIS}(\sigma_n) LIS ( σ n ) [17 ] related the shape of the longest increasing subsequence to the so-called directed geodesic of the directed landscape.
In recent years, a lot of work has been done to analyze the LIS of random permutations with non-uniform distributions. These encompass, e.g., the Mallows distribution [27 , 11 , 4 ] , the Ewens distribution and other conjugacy-invariant models [23 , 16 ] , permutations sampled from a density on the unit square [18 , 14 ] , Baxter permutations [10 ] , or permutations sampled from the Brownian separable permutons [BDSG24, ABB+25]. In this paper, we contribute to this line of research by considering the Luce distribution .
The Luce distribution
The Luce distribution describes a basic sampling procedure: draw balls from a weighted urn, one at a time and without replacement, choosing each remaining ball with probability proportional to its weight. The order of the draws produces a random ranking.
More precisely, let θ = ( θ 1 , … , θ n ) \theta=(\theta_1,\ldots,\theta_n) θ = ( θ 1 , … , θ n ) w n : = θ 1 + ⋯ + θ n w_n := \theta_1+\cdots+\theta_n w n := θ 1 + ⋯ + θ n τ n \tau_n τ n θ \theta θ τ n ∼ Luce ( θ ) \tau_n \sim\operatorname{Luce}(\theta) τ n ∼ Luce ( θ )
for each σ ∈ S n , P ( τ n = σ ) = θ σ − 1 ( 1 ) w n × θ σ − 1 ( 2 ) w n − θ σ − 1 ( 1 ) × θ σ − 1 ( 3 ) w n − θ σ − 1 ( 1 ) − θ σ − 1 ( 2 ) × ⋯ × θ σ − 1 ( n ) θ σ − 1 ( n ) . \text{for each }\sigma\in\mathfrak{S}_n,\qquad\mathbb{P}(\tau_n=\sigma)=\frac{\theta_{\sigma^{-1}(1)}}{w_n}\times\frac{\theta_{\sigma^{-1}(2)}}{w_n-\theta_{\sigma^{-1}(1)}}\times\frac{\theta_{\sigma^{-1}(3)}}{w_n-\theta_{\sigma^{-1}(1)}-\theta_{\sigma^{-1}(2)}}\times\cdots\times\frac{\theta_{\sigma^{-1}(n)}}{\theta_{\sigma^{-1}(n)}}. for each σ ∈ S n , P ( τ n = σ ) = w n θ σ − 1 ( 1 ) × w n − θ σ − 1 ( 1 ) θ σ − 1 ( 2 ) × w n − θ σ − 1 ( 1 ) − θ σ − 1 ( 2 ) θ σ − 1 ( 3 ) × ⋯ × θ σ − 1 ( n ) θ σ − 1 ( n ) . In terms of the urn construction, ball i i i θ i \theta_i θ i τ n ( i ) \tau_n(i) τ n ( i ) τ n − 1 ( 1 ) , … , τ n − 1 ( n ) \tau_n^{-1}(1),\ldots,\tau_n^{-1}(n) τ n − 1 ( 1 ) , … , τ n − 1 ( n ) Luce ( θ 1 , … , θ n ) = Luce ( α θ 1 , … , α θ n ) \operatorname{Luce}(\theta_1,\ldots,\theta_n)=\operatorname{Luce}(\alpha\theta_1,\ldots,\alpha\theta_n) Luce ( θ 1 , … , θ n ) = Luce ( α θ 1 , … , α θ n ) α > 0 \alpha>0 α > 0
The “Sukhatme” weights θ k = n − k + 1 \theta_k=n-k+1 θ k = n − k + 1
The “polynomial Sukhatme” weights θ k = ( n − k + 1 ) α \theta_k=(n-k+1)^\alpha θ k = ( n − k + 1 ) α α > 0 \alpha>0 α > 0
The “exponential Sukhatme” weights θ k = α k \theta_k=\alpha^k θ k = α k α > 0 \alpha>0 α > 0
The “expoly-Sukhatme” weights θ k = exp [ − ( n − k + 1 n ) − α ] \theta_k=\exp\left[-\left(\frac{n-k+1}{n}\right)^{-\alpha}\right] θ k = exp [ − ( n n − k + 1 ) − α ] α > 0 \alpha>0 α > 0
The “Mallows-like” weights θ k = q n k \theta_k=q_n^k θ k = q n k q n q_n q n q n = e − β / n q_n=e^{-\beta/n} q n = e − β / n β ∈ R \beta\in\mathbb{R} β ∈ R § 1.6 ).
An important case that will accompany us throughout the paper is when θ k = f ( ( k − 1 ) / n ) \theta_k=f((k-1)/n) θ k = f (( k − 1 ) / n ) f f f [ 0 , 1 ) [0,1) [ 0 , 1 ) q n = e − β / n q_n=e^{-\beta/n} q n = e − β / n
The above distribution was introduced by Luce (see, e.g., [25 ] ) to model rankings of data given to subjects in psychophysics experiments. This elementary sampling scheme, known as successive sampling , is a standard model in survey sampling [19 ] . It also underlies models used in horse-race betting to predict finishing orders from winning probabilities [20 ] . Another important occurrence is the stationary distribution of the Tsetlin library : at each step, book i i i θ i / w n \theta_i/w_n θ i / w n τ n − 1 \tau_n^{-1} τ n − 1 [12 Section 2.2.3] .
As basic as this sampling mechanism is, many natural features of the resulting rankings remain to be understood. We hope that our approach to studying the LIS, and hence Ulam distance, will also help in the study of other statistics of applied interest. Recently, Chatterjee–Diaconis–Kim analyzed in [12 ] the distributions of ( τ n − 1 ( 1 ) , … , τ n − 1 ( k ) ) (\tau_n^{-1}(1),\ldots,\tau_n^{-1}(k)) ( τ n − 1 ( 1 ) , … , τ n − 1 ( k )) k k k ( τ n − 1 ( n ) , … , τ n − 1 ( n − k + 1 ) ) (\tau_n^{-1}(n),\ldots,\tau_n^{-1}(n-k+1)) ( τ n − 1 ( n ) , … , τ n − 1 ( n − k + 1 )) k k k k ∈ N k\in\mathbb{N} k ∈ N τ n \tau_n τ n permuton limit of τ n \tau_n τ n τ n \tau_n τ n
Remark 1.2. Regarding the definition of the Luce distribution, we adopt here the same convention as in [BCD25], which is the inverse of the convention in [12 ] . Nevertheless, this choice does not affect our results since the LIS is invariant under the inverse map. ▲
Throughout our proofs, we will heavily rely on an alternative construction of τ n \tau_n τ n ( y 1 , … , y n ) (y_1,\ldots,y_n) ( y 1 , … , y n ) σ = ( σ 1 , … , σ n ) \sigma=(\sigma_1,\ldots,\sigma_n) σ = ( σ 1 , … , σ n ) S n \mathfrak{S}_n S n σ i = ∑ 1 ≤ j ≤ n 1 y j ≤ y i \sigma_i=\sum_{1\le j\le n}\mathbf{1}_{y_j\le y_i} σ i = ∑ 1 ≤ j ≤ n 1 y j ≤ y i i ∈ { 1 , … , n } i\in\{1,\ldots,n\} i ∈ { 1 , … , n } Perm ( y 1 , … , y n ) \operatorname{Perm}(y_1,\ldots,y_n) Perm ( y 1 , … , y n ) permutation induced by ( y 1 , … , y n ) (y_1,\ldots,y_n) ( y 1 , … , y n ) [12 Theorem 2.1] .
Lemma 1.3 (Exponential representation). Let ( θ i ) 1 ≤ i ≤ n (\theta_i)_{1\le i\le n} ( θ i ) 1 ≤ i ≤ n ( E i ) 1 ≤ i ≤ n (E_i)_{1\le i\le n} ( E i ) 1 ≤ i ≤ n ( θ i ) 1 ≤ i ≤ n (\theta_i)_{1\le i\le n} ( θ i ) 1 ≤ i ≤ n ( θ i − 1 ) 1 ≤ i ≤ n (\theta_i^{-1})_{1\le i\le n} ( θ i − 1 ) 1 ≤ i ≤ n Perm ( E 1 , … , E n ) \operatorname{Perm}(E_1,\ldots,E_n) Perm ( E 1 , … , E n ) ( θ 1 , … , θ n ) (\theta_1,\ldots,\theta_n) ( θ 1 , … , θ n )
Permuton limits and samples
Permutations were formally introduced in [21 ] as scaling limits for sequences of permutations. A probability measure μ \mu μ [ 0 , 1 ] 2 [0,1]^2 [ 0 , 1 ] 2 μ ( [ 0 , t ] × [ 0 , 1 ] ) = μ ( [ 0 , 1 ] × [ 0 , t ] ) = t \mu([0,t]\times[0,1])=\mu([0,1]\times[0,t])=t μ ([ 0 , t ] × [ 0 , 1 ]) = μ ([ 0 , 1 ] × [ 0 , t ]) = t t ∈ [ 0 , 1 ] t\in[0,1] t ∈ [ 0 , 1 ] σ ∈ S n \sigma\in\mathfrak{S}_n σ ∈ S n μ σ \mu_\sigma μ σ
d μ σ d L e b : = n ∑ 1 ≤ i ≤ n 1 [ i − 1 n , i n ] × [ σ − 1 ( i ) − 1 n , σ − 1 ( i ) n ] . \frac{\mathrm{d}\mu_\sigma}{\mathrm{dLeb}}:=n\sum_{1\le i\le n}\mathbf{1}_{\left[\frac{i-1}{n},\frac{i}{n}\right]\times\left[\frac{\sigma^{-1}(i)-1}{n},\frac{\sigma^{-1}(i)}{n}\right]}. dLeb d μ σ := n 1 ≤ i ≤ n ∑ 1 [ n i − 1 , n i ] × [ n σ − 1 ( i ) − 1 , n σ − 1 ( i ) ] . and we say that a sequence of permutations ( σ n ) n ∈ N (\sigma_n)_{n\in\mathbb{N}} ( σ n ) n ∈ N μ \mu μ ( μ σ n ) n ∈ N (\mu_{\sigma_n})_{n\in\mathbb{N}} ( μ σ n ) n ∈ N μ \mu μ [9 ] for an overview.
Any given permuton μ \mu μ μ \mu μ ( ( U i , V i ) ) 1 ≤ i ≤ n ((U_i,V_i))_{1\le i\le n} (( U i , V i ) ) 1 ≤ i ≤ n μ \mu μ ( ( U ( i ) , V ( i ) ) ) 1 ≤ i ≤ n ((U_{(i)},V_{(i)}))_{1\le i\le n} (( U ( i ) , V ( i ) ) ) 1 ≤ i ≤ n U ( 1 ) < ⋯ < U ( n ) U_{(1)<\cdots<U_{(n)}} U ( 1 ) < ⋯ < U ( n ) Perm ( V ( 1 ) , … , V ( n ) ) \operatorname{Perm}(V_{(1)},\ldots,V_{(n)}) Perm ( V ( 1 ) , … , V ( n ) ) μ \mu μ Sample n ( μ ) \operatorname{Sample}_n(\mu) Sample n ( μ ) σ n , μ \sigma_{n,\mu} σ n , μ n n n μ \mu μ [21 ] that, for any given permuton μ \mu μ ( σ n , μ ) n ∈ N (\sigma_{n,\mu})_{n\in\mathbb{N}} ( σ n , μ ) n ∈ N μ \mu μ P ( σ n , μ = σ ) \mathbb{P}(\sigma_{n,\mu}=\sigma) P ( σ n , μ = σ ) n ∈ N n\in\mathbb{N} n ∈ N σ ∈ S n \sigma\in\mathfrak{S}_n σ ∈ S n μ \mu μ
The permuton limits of Luce random permutations were computed in [BCD25]. The context is the following: for each n ∈ N n\in\mathbb{N} n ∈ N θ ( n ) = ( θ 1 ( n ) , … , θ n ( n ) ) \theta^{(n)}=(\theta^{(n)}_1,\ldots,\theta^{(n)}_n) θ ( n ) = ( θ 1 ( n ) , … , θ n ( n ) ) f n ( y ) : = θ ⌊ y n ⌋ + 1 ( n ) f_n(y):=\theta^{(n)}_{\lfloor yn\rfloor+1} f n ( y ) := θ ⌊ y n ⌋ + 1 ( n ) y ∈ [ 0 , 1 ) y\in[0,1) y ∈ [ 0 , 1 )
Theorem 1.4 ([BCD25]). For each n ∈ N n\in\mathbb{N} n ∈ N τ n \tau_n τ n Luce ( θ ( n ) ) \operatorname{Luce}(\theta^{(n)}) Luce ( θ ( n ) ) ( f n ) n ∈ N (f_n)_{n\in\mathbb{N}} ( f n ) n ∈ N f f f [ 0 , 1 ) [0,1) [ 0 , 1 ) ( τ n ) n ∈ N (\tau_n)_{n\in\mathbb{N}} ( τ n ) n ∈ N μ f \mu_f μ f ( U , F ( E / f ( U ) ) ) (U,F(E/f(U))) ( U , F ( E / f ( U ))) U U U E E E Unif ( [ 0 , 1 ] ) \operatorname{Unif}([0,1]) Unif ([ 0 , 1 ]) Exp ( 1 ) \operatorname{Exp}(1) Exp ( 1 )
F ( x ) : = 1 − ∫ 0 1 e − x f ( t ) d t for x ∈ [ 0 , ∞ ) . (1) F(x):=1-\int_0^1 e^{-xf(t)}\,\mathrm{d}t \qquad\text{for }x\in[0,\infty). \tag*{(1)} F ( x ) := 1 − ∫ 0 1 e − x f ( t ) d t for x ∈ [ 0 , ∞ ) . (1) This permuton μ f \mu_f μ f
P ( σ k , μ f = σ ) = k ! ∫ 0 < u 1 < ⋯ < u k < 1 P ( τ k ( u 1 , … , u k ) = σ ) d u 1 ⋯ d u k for k ∈ N and σ ∈ S k , (2) \mathbb{P}(\sigma_{k,\mu_f}=\sigma)=k!\int_{0<u_1<\cdots<u_k<1}\mathbb{P}\left(\tau_k^{(u_1,\ldots,u_k)}=\sigma\right)\,\mathrm{d}u_1\cdots\mathrm{d}u_k \qquad\text{for }k\in\mathbb{N}\text{ and }\sigma\in\mathfrak{S}_k, \tag*{(2)} P ( σ k , μ f = σ ) = k ! ∫ 0 < u 1 < ⋯ < u k < 1 P ( τ k ( u 1 , … , u k ) = σ ) d u 1 ⋯ d u k for k ∈ N and σ ∈ S k , (2) where we let τ k ( u 1 , … , u k ) \tau_k^{(u_1,\ldots,u_k)} τ k ( u 1 , … , u k ) f ( u 1 ) , … , f ( u k ) f(u_1),\ldots,f(u_k) f ( u 1 ) , … , f ( u k ) μ f \mu_f μ f ρ f \rho_f ρ f Leb [ 0 , 1 ] 2 \operatorname{Leb}_{[0,1]^2} Leb [ 0 , 1 ] 2
ρ f ( x , y ) = f ( x ) e − f ( x ) F − 1 ( y ) ∫ 0 1 f ( t ) e − f ( t ) F − 1 ( y ) d t for ( x , y ) ∈ ( 0 , 1 ) 2 . (3) \rho_f(x,y)=\frac{f(x)e^{-f(x)F^{-1}(y)}}{\int_0^1 f(t)e^{-f(t)F^{-1}(y)}\,\mathrm{d}t}
\qquad\text{for }(x,y)\in(0,1)^2. \tag*{(3)} ρ f ( x , y ) = ∫ 0 1 f ( t ) e − f ( t ) F − 1 ( y ) d t f ( x ) e − f ( x ) F − 1 ( y ) for ( x , y ) ∈ ( 0 , 1 ) 2 . (3) Example 1.5. Take f : t ↦ 1 − t f:t\mapsto1-t f : t ↦ 1 − t μ f \mu_f μ f θ i ( n ) : = n − i + 1 \theta_i^{(n)}:=n-i+1 θ i ( n ) := n − i + 1 φ : [ 0 , 1 ) → [ 0 , ∞ ) \varphi:[0,1)\to[0,\infty) φ : [ 0 , 1 ) → [ 0 , ∞ ) F : x ∈ [ 0 , ∞ ) ↦ x − 1 + e − x x F:x\in[0,\infty)\mapsto\frac{x-1+e^{-x}}{x} F : x ∈ [ 0 , ∞ ) ↦ x x − 1 + e − x
ρ f ( x , y ) = ( 1 − x ) φ ( y ) 2 e x φ ( y ) e φ ( y ) − φ ( y ) − 1 for all ( x , y ) ∈ [ 0 , 1 ) 2 . (4) \rho_f(x,y)=\frac{(1-x)\varphi(y)^2e^{x\varphi(y)}}{e^{\varphi(y)}-\varphi(y)-1}
\qquad\text{for all }(x,y)\in[0,1)^2. \tag*{(4)} ρ f ( x , y ) = e φ ( y ) − φ ( y ) − 1 ( 1 − x ) φ ( y ) 2 e x φ ( y ) for all ( x , y ) ∈ [ 0 , 1 ) 2 . (4) See Figure 1 for an illustration. As a comparison, see Figure 2 (right) for the “Mallows-like” function f ( t ) = e − β t f(t)=e^{-\beta t} f ( t ) = e − β t β = 6 \beta=6 β = 6
Figure 1. Left: the diagram of a Luce permutation τ n \tau_n τ n θ i ( n ) = n − i + 1 \theta_i^{(n)}=n-i+1 θ i ( n ) = n − i + 1 n = 16000 n=16000 n = 16000 ρ f \rho_f ρ f μ f \mu_f μ f f ( t ) = 1 − t f(t)=1-t f ( t ) = 1 − t (4) .
Figure 2. The 3D plots of two Mallows-related permutons with β = 6 \beta= 6 β = 6 μ β M \mu^{\mathrm{M}}_{\beta} μ β M μ f β \mu_{f_{\beta}} μ f β
It should be noted that permuton convergence, in itself, is rather “weak”. Indeed, the convergence of a sequence ( σ n ) n ∈ N (\sigma_n)_{n\in\mathbb{N}} ( σ n ) n ∈ N μ \mu μ φ ( σ n ) \varphi(\sigma_n) φ ( σ n ) φ : S → R \varphi:\mathfrak{S}\to\mathbb{R} φ : S → R φ ( σ n ) \varphi(\sigma_n) φ ( σ n ) φ ( σ n , μ ) \varphi(\sigma_{n,\mu}) φ ( σ n , μ ) φ \varphi φ [28 ] , which implies the convergence of small cycle counts. A similar philosophy can be perceived in the papers [27 ] , which relates the LIS of Mallows permutations to their limit permuton, and [16 ] , which analyzes conjugacy-invariant permutations through a geometric construction akin to that of permuton samples.
The present work can be seen in the continuity of this line of research, as we rely on the “regularity properties” of Lemmas 3.1 and 3.6 to relate the LIS of Luce permutations to their limit permuton (Theorem 3.13 ). Hence, this also contributes to the following problem raised in [BCD25]: “a natural question is to study how a sequence of exactly distributed Luce permutations behaves differently than the permutations sampled for their limiting permuton”.
Statements of the main results and organization of the paper
In this section we present our main results, with their precise statements for the reader’s convenience.
Our first main result concerns the growth rate of the LIS of Luce permutations. We restrict our attention to sequences of non-increasing weights, which form an important class of weights for the Luce model (see, e.g., the discussions in [12 BCD25] ).
In what follows, if ( a n ) n ∈ N (a_n)_{n\in\mathbb{N}} ( a n ) n ∈ N ( b n ) n ∈ N (b_n)_{n\in\mathbb{N}} ( b n ) n ∈ N a n ≍ b n a_n \asymp b_n a n ≍ b n a n / b n a_n/b_n a n / b n b n / a n b_n/a_n b n / a n ( A n ) n ∈ N (A_n)_{n\in\mathbb{N}} ( A n ) n ∈ N ( B n ) n ∈ N (B_n)_{n\in\mathbb{N}} ( B n ) n ∈ N A n ≍ P B n A_n \asymp_{\mathbb{P}} B_n A n ≍ P B n A n / B n A_n/B_n A n / B n
lim ε → 0 lim inf n → ∞ P ( A n / B n ∈ [ ε , 1 / ε ] ) = 1. \lim_{\varepsilon\to0}\liminf_{n\to\infty}\mathbb{P}\left(A_n/B_n\in[\varepsilon,1/\varepsilon]\right)=1. ε → 0 lim n → ∞ lim inf P ( A n / B n ∈ [ ε , 1/ ε ] ) = 1. Theorem 1.6 (Summary of Theorem 2.1 and Corollary 2.18). For each n ∈ N n\in\mathbb{N} n ∈ N θ ( n ) = ( θ 1 ( n ) ≥ … ≥ θ n ( n ) ) \theta^{(n)}=(\theta^{(n)}_1\ge\ldots\ge\theta^{(n)}_n) θ ( n ) = ( θ 1 ( n ) ≥ … ≥ θ n ( n ) ) k ∈ Z k\in\mathbb{Z} k ∈ Z
B k ( n ) : = { i ∈ [ n ] : k ≤ − log θ i ( n ) < k + 1 } and m k ( n ) : = # B k ( n ) . B_k^{(n)}:=\left\{i\in[n]: k\le-\log\theta_i^{(n)}<k+1\right\}
\qquad\text{and}\qquad
m_k^{(n)}:=\#B_k^{(n)}. B k ( n ) := { i ∈ [ n ] : k ≤ − log θ i ( n ) < k + 1 } and m k ( n ) := # B k ( n ) . Then, for τ n \tau_n τ n ( θ ( n ) ) (\theta^{(n)}) ( θ ( n ) )
E [ LIS ( τ n ) ] ≍ ∑ k ∈ Z m k ( n ) and LIS ( τ n ) ≍ P ∑ k ∈ Z m k ( n ) . \mathbb{E}[\operatorname{LIS}(\tau_n)]\asymp\sum_{k\in\mathbb{Z}}\sqrt{m_k^{(n)}}
\qquad\text{and}\qquad
\operatorname{LIS}(\tau_n)\asymp_{\mathbb{P}}\sum_{k\in\mathbb{Z}}\sqrt{m_k^{(n)}}. E [ LIS ( τ n )] ≍ k ∈ Z ∑ m k ( n ) and LIS ( τ n ) ≍ P k ∈ Z ∑ m k ( n ) . Section 2 is dedicated to this result, along with applications and examples. In Section 2.1, we provide several methods to compute the quantity ∑ k ∈ Z m k ( n ) \sum_{k\in\mathbb{Z}}\sqrt{m_k^{(n)}} ∑ k ∈ Z m k ( n ) θ i ( n ) = f ( i − 1 n ) \theta_i^{(n)}=f\left(\frac{i-1}{n}\right) θ i ( n ) = f ( n i − 1 ) f f f n \sqrt{n} n n β n^\beta n β β ∈ [ 1 / 2 , 1 ) \beta\in[1/2,1) β ∈ [ 1/2 , 1 )
For the exponential Sukhatme weights θ k = α k \theta_k=\alpha^k θ k = α k α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) n n n
For the Mallows-like weights θ k = q n k \theta_k=q_n^k θ k = q n k 0 < q n ≤ 1 0<q_n\le1 0 < q n ≤ 1 q n → 1 q_n\to1 q n → 1 max ( n 1 − q n , n ) \max\left(n\sqrt{1-q_n},\sqrt{n}\right) max ( n 1 − q n , n )
The proof of Theorem 2.1 is conducted in Section 2.3. It partly relies on a “superuniformity” property (Proposition 2.13 ) proven in Section 2.2. The latter essentially states that the LIS of any given subpermutation in τ n \tau_n τ n LIS ( τ n ) \operatorname{LIS}(\tau_n) LIS ( τ n )
Our second main result states a law of large numbers in the n \sqrt{n} n θ ( n ) ( f ) : = ( f ( i − 1 n ) ) 1 ≤ i < n \theta^{(n)}(f):=\left(f\left(\frac{i-1}{n}\right)\right)_{1\le i<n} θ ( n ) ( f ) := ( f ( n i − 1 ) ) 1 ≤ i < n f : [ 0 , 1 ) → R + ∗ f:[0,1)\to\mathbb{R}_+^* f : [ 0 , 1 ) → R + ∗ canonically associated with the function f f f τ n \tau_n τ n σ n , μ f \sigma_{n,\mu_f} σ n , μ f ( θ ( n ) ( f ) ) (\theta^{(n)}(f)) ( θ ( n ) ( f )) n ( μ f ) _n(\mu_f) n ( μ f ) σ n , μ f \sigma_{n,\mu_f} σ n , μ f τ n \tau_n τ n LIS ( τ n ) \operatorname{LIS}(\tau_n) LIS ( τ n ) LIS ( σ n , μ f ) \operatorname{LIS}(\sigma_{n,\mu_f}) LIS ( σ n , μ f ) E [ LIS ( τ n ) ] ≍ n \mathbb{E}[\operatorname{LIS}(\tau_n)] \asymp\sqrt{n} E [ LIS ( τ n )] ≍ n 2 K ( f ) n 2K(f)\sqrt{n} 2 K ( f ) n K ( f ) K(f) K ( f ) μ f \mu_f μ f Theorem 3.13 ), while the second one is a more direct reformulation in terms of f f f Lemma 3.14 ). Note that the condition E [ LIS ( τ n ) ] ≍ n \mathbb{E}[\operatorname{LIS}(\tau_n)] \asymp\sqrt{n} E [ LIS ( τ n )] ≍ n Theorem 2.1 , and specifically, Lemma 2.8 .
Theorem 1.7 (Summary of Theorem 3.13 and Lemma 3.14). Let f f f C 1 C^1 C 1 [ 0 , 1 ) [0,1) [ 0 , 1 ) μ f \mu_f μ f Theorem 1.4 with density ρ f \rho_f ρ f n ∈ N n \in\mathbb{N} n ∈ N θ ( n ) ( f ) : = ( f ( i − 1 n ) ) 1 ≤ i ≤ n \theta^{(n)}(f) := \left(f\left(\frac{i-1}{n}\right)\right)_{1 \le i \le n} θ ( n ) ( f ) := ( f ( n i − 1 ) ) 1 ≤ i ≤ n τ n \tau_n τ n ( θ ( n ) ( f ) ) (\theta^{(n)}(f)) ( θ ( n ) ( f )) σ n , μ f \sigma_{n,\mu_f} σ n , μ f μ f \mu_f μ f − log f -\log f − log f E [ LIS ( τ n ) ] ≍ n \mathbb{E}[\operatorname{LIS}(\tau_n)] \asymp\sqrt{n} E [ LIS ( τ n )] ≍ n
lim n → ∞ 1 n LIS ( τ n ) = lim n → ∞ 1 n LIS ( σ n , μ f ) = 2 K ( f ) with K ( f ) = sup u : [ 0 , 1 ) ↗ [ 0 , ∞ ) ∫ 0 1 f ( t ) u ′ ( t ) e − f ( t ) u ( t ) d t \lim_{n\to\infty}\frac{1}{\sqrt{n}}\operatorname{LIS}(\tau_n)
=
\lim_{n\to\infty}\frac{1}{\sqrt{n}}\operatorname{LIS}(\sigma_{n,\mu_f})
=
2K(f)
\quad\text{with}\quad
K(f)=\sup_{u:[0,1)\nearrow[0,\infty)}\int_0^1\sqrt{f(t)u'(t)e^{-f(t)u(t)}}\,\mathrm{d}t n → ∞ lim n 1 LIS ( τ n ) = n → ∞ lim n 1 LIS ( σ n , μ f ) = 2 K ( f ) with K ( f ) = u : [ 0 , 1 ) ↗ [ 0 , ∞ ) sup ∫ 0 1 f ( t ) u ′ ( t ) e − f ( t ) u ( t ) d t where the limits hold in probability and in expectation, and the supremum ranges over all non-decreasing, right-continuous curves u : [ 0 , 1 ) → [ 0 , ∞ ) u:[0,1)\to[0,\infty) u : [ 0 , 1 ) → [ 0 , ∞ )
Section 3 is dedicated to this result, and spans ideas that we believe to be more meaningful. We start by showing in Section 3.1 that the choice of weights θ i ( n ) = f ( i − 1 n ) \theta_i^{(n)}=f\left(\frac{i-1}{n}\right) θ i ( n ) = f ( n i − 1 ) Lemmas 3.1 and 3.6 . These two lemmas are formally equivalent, but dual in their interpretation: Lemma 3.1 states that Luce permuton samples σ n , μ f \sigma_{n,\mu_f} σ n , μ f Lemma 3.6 states that Luce permutations τ n \tau_n τ n
From there, the general philosophy is to compare the Luce permutation τ n \tau_n τ n θ ( n ) ( f ) \theta^{(n)}(f) θ ( n ) ( f ) σ n , μ f \sigma_{n,\mu_f} σ n , μ f Lemma 3.3 that both models share the same LIS growth rate. In order to refine this comparison, we construct in Section 3.2 a coupling of τ n \tau_n τ n σ n , μ f \sigma_{n,\mu_f} σ n , μ f Proposition 3.7 . This later allows us to show that LIS ( τ n ) / LIS ( σ n , μ f ) \operatorname{LIS}(\tau_n)/\operatorname{LIS}(\sigma_{n,\mu_f}) LIS ( τ n ) / LIS ( σ n , μ f ) Theorem 3.13 for σ n , μ f \sigma_{n,\mu_f} σ n , μ f Theorem 3.13 for details.
Finally, Section 3.3 contains the remaining ingredients to prove Theorem 3.13 . The main input is the famous law of large numbers obtained by Deuschel and Zeitouni in [18 ] for the LIS of permuton samples; after settling some technical issues, we apply their result to the continuous model σ n , μ f \sigma_{n,\mu_f} σ n , μ f τ n \tau_n τ n K ( f ) K(f) K ( f ) Lemma 3.14 ), and present some bounds.
Notation
Throughout, we let N : = { 1 , 2 , … } \mathbb{N}:=\{1,2,\ldots\} N := { 1 , 2 , … } N 0 : = { 0 , 1 , 2 , … } \mathbb{N}_0:=\{0,1,2,\ldots\} N 0 := { 0 , 1 , 2 , … } n ∈ N 0 n\in\mathbb{N}_0 n ∈ N 0 [ n ] : = { 1 , … , n } [n]:=\{1,\ldots,n\} [ n ] := { 1 , … , n } [ 0 ] = ∅ [0]=\varnothing [ 0 ] = ∅ [ x ] : = ⌊ x ⌋ [x]:=\lfloor x\rfloor [ x ] := ⌊ x ⌋ x ≥ 0 x\ge0 x ≥ 0 ( u n ) n ∈ N (u_n)_{n\in\mathbb{N}} ( u n ) n ∈ N ( v n ) n ∈ N (v_n)_{n\in\mathbb{N}} ( v n ) n ∈ N u n = O ( v n ) u_n=O(v_n) u n = O ( v n ) ( u n / v n ) n ∈ N (u_n/v_n)_{n\in\mathbb{N}} ( u n / v n ) n ∈ N u n = o ( v n ) u_n=o(v_n) u n = o ( v n ) u n / v n → 0 u_n/v_n\to0 u n / v n → 0 n → ∞ n\to\infty n → ∞ u n = O ( v n ) u_n=O(v_n) u n = O ( v n ) v n = O ( u n ) v_n=O(u_n) v n = O ( u n ) u n = Θ ( v n ) u_n=\Theta(v_n) u n = Θ ( v n )
If I I I ( u α ) α ∈ I (u_\alpha)_{\alpha\in I} ( u α ) α ∈ I ( v α ) α ∈ I (v_\alpha)_{\alpha\in I} ( v α ) α ∈ I u α ≍ v α u_\alpha\asymp v_\alpha u α ≍ v α C > 0 C>0 C > 0 C − 1 ≤ u α / v α ≤ C C^{-1}\le u_\alpha/v_\alpha\le C C − 1 ≤ u α / v α ≤ C α ∈ I \alpha\in I α ∈ I f : [ 0 , 1 ) → ( 0 , ∞ ) f:[0,1)\to(0,\infty) f : [ 0 , 1 ) → ( 0 , ∞ ) C C C f f f
For n ∈ N n\in\mathbb{N} n ∈ N S n \mathfrak{S}_n S n [ n ] [n] [ n ] S : = ⨆ n ∈ N S n \mathfrak{S}:=\bigsqcup_{n\in\mathbb{N}}\mathfrak{S}_n S := ⨆ n ∈ N S n σ ∈ S n \sigma\in\mathfrak{S}_n σ ∈ S n i ∈ [ n ] i\in[n] i ∈ [ n ] σ ( i ) \sigma(i) σ ( i ) σ i \sigma_i σ i σ n \sigma_n σ n n n n σ = σ 1 ∘ σ 2 ∘ ⋯ ∘ σ n \sigma=\sigma_1\circ\sigma_2\circ\cdots\circ\sigma_n σ = σ 1 ∘ σ 2 ∘ ⋯ ∘ σ n
If y 1 , … , y n y_1,\ldots,y_n y 1 , … , y n LIS ( y 1 , … , y n ) \operatorname{LIS}(y_1,\ldots,y_n) LIS ( y 1 , … , y n ) σ ∈ S n \sigma\in\mathfrak{S}_n σ ∈ S n LIS ( σ ) = LIS ( σ 1 , … , σ n ) \operatorname{LIS}(\sigma)=\operatorname{LIS}(\sigma_1,\ldots,\sigma_n) LIS ( σ ) = LIS ( σ 1 , … , σ n ) P \mathcal{P} P R 2 \mathbb{R}^2 R 2 x x x y y y Perm ( P ) \operatorname{Perm}(\mathcal{P}) Perm ( P ) Perm ( P ) : = Perm ( Y ( 1 ) , … , Y ( n ) ) \operatorname{Perm}(\mathcal{P}):=\operatorname{Perm}(Y_{(1)},\ldots,Y_{(n)}) Perm ( P ) := Perm ( Y ( 1 ) , … , Y ( n ) ) ( X ( i ) , Y ( i ) ) i ≥ 1 (X_{(i)},Y_{(i)})_{i\ge1} ( X ( i ) , Y ( i ) ) i ≥ 1 P \mathcal{P} P x x x LIS ( P ) : = LIS ( Perm ( P ) ) = LIS ( Y ( 1 ) , … , Y ( n ) ) \operatorname{LIS}(\mathcal{P}):=\operatorname{LIS}(\operatorname{Perm}(\mathcal{P}))=\operatorname{LIS}(Y_{(1)},\ldots,Y_{(n)}) LIS ( P ) := LIS ( Perm ( P )) = LIS ( Y ( 1 ) , … , Y ( n ) )
If X , Y X,Y X , Y X X X Y Y Y t ∈ R t\in\mathbb{R} t ∈ R P ( X ≥ t ) ≥ P ( Y ≥ t ) \mathbb{P}(X\ge t)\ge\mathbb{P}(Y\ge t) P ( X ≥ t ) ≥ P ( Y ≥ t ) X X X Y Y Y ( X ~ , Y ~ ) (\widetilde{X},\widetilde{Y}) ( X , Y ) X ~ ≥ Y ~ \widetilde{X}\ge\widetilde{Y} X ≥ Y ( X n ) n ∈ N (X_n)_{n\in\mathbb{N}} ( X n ) n ∈ N x ∈ R x\in\mathbb{R} x ∈ R lim sup X n ≤ x \limsup X_n\le x lim sup X n ≤ x δ > 0 \delta>0 δ > 0 P ( X n ≥ x + δ ) → 0 \mathbb{P}(X_n\ge x+\delta)\to0 P ( X n ≥ x + δ ) → 0 n → ∞ n\to\infty n → ∞ lim inf X n ≥ x \liminf X_n\ge x lim inf X n ≥ x δ > 0 \delta>0 δ > 0 P ( X n ≤ x − δ ) → 0 \mathbb{P}(X_n\le x-\delta)\to0 P ( X n ≤ x − δ ) → 0
Discussion and open questions
A comparison with the Mallows model. Let τ \tau τ ( θ 1 , … , θ n ) (\theta_1,\ldots,\theta_n) ( θ 1 , … , θ n ) τ − 1 ( 1 ) , … , τ − 1 ( n ) \tau^{-1}(1),\ldots,\tau^{-1}(n) τ − 1 ( 1 ) , … , τ − 1 ( n ) τ − 1 ( 1 ) \tau^{-1}(1) τ − 1 ( 1 ) [ n ] [n] [ n ] k k k θ k \theta_k θ k τ − 1 ( 1 ) = ℓ \tau^{-1}(1)=\ell τ − 1 ( 1 ) = ℓ τ − 1 ( 2 ) \tau^{-1}(2) τ − 1 ( 2 ) [ n ] ∖ { ℓ } [n]\setminus\{\ell\} [ n ] ∖ { ℓ } k k k θ k \theta_k θ k p p p p k : = θ k p_k := \theta_k p k := θ k [30 ] .
In comparison, the Mallows distribution on S n \mathfrak{S}_n S n q ≥ 0 q\geq0 q ≥ 0 π ( 1 ) \pi(1) π ( 1 ) [ n ] [n] [ n ] k k k q k q^k q k π ( 1 ) = ℓ \pi(1)=\ell π ( 1 ) = ℓ π ( 2 ) \pi(2) π ( 2 ) [ n ] ∖ { ℓ } [n]\setminus\{\ell\} [ n ] ∖ { ℓ } k k k q rk ( k ) q^{\operatorname{rk}(k)} q rk ( k ) rk \operatorname{rk} rk [ n ] ∖ { ℓ } [n]\setminus\{\ell\} [ n ] ∖ { ℓ } [ n − 1 ] [n-1] [ n − 1 ] π \pi π π − 1 \pi^{-1} π − 1 p p p p k : = q k p_k := q^k p k := q k [30 ] .
Therefore, one might wish to compare the Mallows model with parameter q n > 0 q_n>0 q n > 0 θ k ( n ) : = q n k \theta_k^{(n)} := q_n^k θ k ( n ) := q n k [29 ] , in the context of the secretary problem. For our purposes, write q n = e − u n q_n=e^{-u_n} q n = e − u n u n > 0 u_n>0 u n > 0 π n \pi_n π n q n q_n q n [27 , 11 , 4 ] : if n u n → 0 nu_n\to0 n u n → 0 E [ LIS ( π n ) ] ≍ n \mathbb{E}[\operatorname{LIS}(\pi_n)]\asymp\sqrt{n} E [ LIS ( π n )] ≍ n u n → 0 u_n\to0 u n → 0 lim inf n u n > 0 \liminf nu_n>0 lim inf n u n > 0 E [ LIS ( π n ) ] ≍ n u n \mathbb{E}[\operatorname{LIS}(\pi_n)]\asymp n\sqrt{u_n} E [ LIS ( π n )] ≍ n u n lim inf u n > 0 \liminf u_n>0 lim inf u n > 0 E [ LIS ( π n ) ] ≍ n \mathbb{E}[\operatorname{LIS}(\pi_n)]\asymp n E [ LIS ( π n )] ≍ n Theorem 2.1 , we compute in Example 2.3 the LIS growth rate for the Luce model with weights θ k ( n ) : = q n k = e − k u n \theta_k^{(n)} := q_n^k=e^{-ku_n} θ k ( n ) := q n k = e − k u n
Going further, ( π n ) n ∈ N (\pi_n)_{n\in\mathbb{N}} ( π n ) n ∈ N n u n → β nu_n\to\beta n u n → β β ∈ [ 0 , ∞ ) \beta\in[0,\infty) β ∈ [ 0 , ∞ ) μ β M \mu^{\mathrm{M}}_{\beta} μ β M [31 ] . Likewise, Theorem 1.4 applies for ( τ n ) n ∈ N (\tau_n)_{n\in\mathbb{N}} ( τ n ) n ∈ N μ f β \mu_{f_{\beta}} μ f β f β : t ↦ e − β t f_{\beta}:t\mapsto e^{-\beta t} f β : t ↦ e − β t Figure 2 for an illustration: although the two densities are clearly different, they share some similarities. On the one hand, it was shown in [27 ] that LIS ( π n ) \operatorname{LIS}(\pi_n) LIS ( π n ) 2 L β n 2\mathcal{L}_{\beta}\sqrt{n} 2 L β n
L β = β − 1 / 2 arsinh ( e β − 1 ) . \mathcal{L}_{\beta}=\beta^{-1/2}\operatorname{arsinh}\left(\sqrt{e^{\beta}-1}\right). L β = β − 1/2 arsinh ( e β − 1 ) . On the other hand, if θ k ( n ) : = e − k β / n \theta_k^{(n)}:=e^{-k\beta/n} θ k ( n ) := e − k β / n LIS ( τ n ) \operatorname{LIS}(\tau_n) LIS ( τ n ) 2 K ( f β ) n 2K(f_{\beta})\sqrt{n} 2 K ( f β ) n K ( f β ) K(f_{\beta}) K ( f β ) Theorem 3.13 and Lemma 3.14 . We discuss the computation of K ( f β ) K(f_{\beta}) K ( f β ) § 3.6 , and show that K ( f β ) ≠ L β K(f_{\beta})\ne\mathcal{L}_{\beta} K ( f β ) = L β
Assumptions of the weights. Our main results concerning the LIS focus on non-increasing sequences of weights ( θ i ) 1 ≤ i ≤ n (\theta_i)_{1\leq i\leq n} ( θ i ) 1 ≤ i ≤ n θ i = f ( ( i − 1 ) / n ) \theta_i=f((i-1)/n) θ i = f (( i − 1 ) / n ) f f f § 3.1 .
Non-monotone weights seem difficult to study, but one might wish to consider non-decreasing sequences of weights. Studying the LIS of Luce permutations with non-decreasing weights is then equivalent to studying the LDS (longest decreasing subsequence ) of Luce permutations with non-increasing weights. The “superuniformity” property of Proposition 2.13 is easily adapted to show that the LDS of Luce permutations with such weights are stochastically dominated by that of uniform permutations, and thus, at most 2 n 2\sqrt{n} 2 n θ ( n ) ( f ) \theta^{(n)}(f) θ ( n ) ( f ) LDS ( τ n ) \operatorname{LDS}(\tau_n) LDS ( τ n ) K ∗ ( f ) n K^*(f)\sqrt{n} K ∗ ( f ) n K ∗ ( f ) K^*(f) K ∗ ( f )
Future prospects. A burning question is that of the fluctuations of LIS ( τ n ) \operatorname{LIS}(\tau_n) LIS ( τ n )
On another note, we believe that our coupling approach (cf Sections 3.1 and 3.2) can be fruitful in the study of statistics other than the LIS. For example, can we use a similar approach to study the number of fixed points of τ n \tau_n τ n
The growth rate of the LIS
Statement and examples
This Section 2 is dedicated to the growth rate of the LIS of Luce random permutations. We will focus on non-increasing weights and prove the following:
Theorem 2.1. Let n ∈ N n \in\mathbb{N} n ∈ N θ ( n ) = ( θ 1 ( n ) ≥ ⋯ ≥ θ n ( n ) ) \theta^{(n)} = \left(\theta_1^{(n)} \ge\cdots\ge\theta_n^{(n)}\right) θ ( n ) = ( θ 1 ( n ) ≥ ⋯ ≥ θ n ( n ) ) k ∈ Z k \in\mathbb{Z} k ∈ Z
B k ( n ) : = { i ∈ [ n ] : k ≤ − log θ i ( n ) < k + 1 } and m k ( n ) : = # B k ( n ) . B_k^{(n)} := \left\{i \in[n] : k \le-\log\theta_i^{(n)} < k+1\right\} \qquad\text{and}\qquad m_k^{(n)} := \# B_k^{(n)}. B k ( n ) := { i ∈ [ n ] : k ≤ − log θ i ( n ) < k + 1 } and m k ( n ) := # B k ( n ) . Then, for τ n \tau_n τ n Luce ( θ ( n ) ) \operatorname{Luce}(\theta^{(n)}) Luce ( θ ( n ) )
E [ LIS ( τ n ) ] ≳ ∑ k ∈ Z m k ( n ) . \mathbb{E}[\operatorname{LIS}(\tau_n)] \gtrsim\sum_{k \in\mathbb{Z}} \sqrt{m_k^{(n)}}. E [ LIS ( τ n )] ≳ k ∈ Z ∑ m k ( n ) . The proof crucially relies on the exponential representation of Luce permutations (Lemma 1.3 ). Then, the upper bound is quite simple. It uses an elementary partitioning technique, along with Lemma 2.15, which provides an upper bound for the LIS of random variables that are independent but not necessarily identically distributed. The lower bound requires more work, and a finer partitioning. On each subset of our partitioning, we use a “superuniformity” property of the Luce model: under the assumption that the weights are non-increasing, if I I I J J J [ n ] [n] [ n ] { τ n ( i ) : i ∈ I , τ n ( i ) ∈ J } \{\tau_n(i) : i \in I, \tau_n(i) \in J\} { τ n ( i ) : i ∈ I , τ n ( i ) ∈ J }
Before moving on with the proofs, let us present some applications of Theorem 2.1. We start with the computation of the LIS growth rate for Mallows-like weights.
Example 2.3. Consider the Mallows-like weights θ k ( n ) = e − k u n \theta_k^{(n)} = e^{-ku_n} θ k ( n ) = e − k u n u n > 0 u_n > 0 u n > 0 0 ≤ k ≤ n u n 0 \le k \le nu_n 0 ≤ k ≤ n u n m k ( n ) m_k^{(n)} m k ( n ) n n n [ k / u n , ( k + 1 ) / u n ) [k/u_n, (k+1)/u_n) [ k / u n , ( k + 1 ) / u n ) 1 / u n 1/u_n 1/ u n
Assume lim inf u n > 0 \liminf u_n > 0 lim inf u n > 0 m k ( n ) m_k^{(n)} m k ( n ) ∑ k ≥ 0 m k ( n ) = n \sum_{k \ge0} m_k^{(n)} = n ∑ k ≥ 0 m k ( n ) = n ∑ m k ( n ) ≲ n \sum\sqrt{m_k^{(n)}} \lesssim n ∑ m k ( n ) ≲ n
Assume n u n → 0 nu_n \to0 n u n → 0 n n n m 0 ( n ) = n m_0^{(n)} = n m 0 ( n ) = n ∑ m k ( n ) ≲ n \sum\sqrt{m_k^{(n)}} \lesssim\sqrt{n} ∑ m k ( n ) ≲ n
Assume u n → 0 u_n \to0 u n → 0 lim inf n u n > 0 \liminf nu_n > 0 lim inf n u n > 0 k ≥ 0 k \ge0 k ≥ 0 m k ( n ) ≤ 1 / u n + 1 m_k^{(n)} \le1/u_n + 1 m k ( n ) ≤ 1/ u n + 1 ⌊ n u n ⌋ + 1 \lfloor nu_n \rfloor+ 1 ⌊ n u n ⌋ + 1
n 1 / u n + 1 ≤ ∑ k ≥ 0 m k ( n ) ≤ n ( ⌊ n u n ⌋ + 1 ) . \frac{n}{\sqrt{1/u_n+1}} \le\sum_{k\ge0}\sqrt{m_k^{(n)}} \le\sqrt{n(\lfloor nu_n\rfloor+1)}. 1/ u n + 1 n ≤ k ≥ 0 ∑ m k ( n ) ≤ n (⌊ n u n ⌋ + 1 ) . Indeed, the lower bound follows by summing m k ( n ) ≤ 1 / u n + 1 m k ( n ) m_k^{(n)} \le\sqrt{1/u_n+1}\sqrt{m_k^{(n)}} m k ( n ) ≤ 1/ u n + 1 m k ( n ) ∑ k ≥ 0 m k ( n ) = n \sum_{k\ge0}m_k^{(n)}=n ∑ k ≥ 0 m k ( n ) = n ∑ k ≥ 0 m k ( n ) ≍ n u n \sum_{k\ge0}\sqrt{m_k^{(n)}}\asymp n\sqrt{u_n} ∑ k ≥ 0 m k ( n ) ≍ n u n
Now, we focus on the following important class of weights: we are given a positive, finite, non-increasing function f f f [ 0 , 1 ) [0,1) [ 0 , 1 ) f ( 0 ) = 1 f(0)=1 f ( 0 ) = 1 θ ( n ) ( f ) : = ( f ( i − 1 n ) ) 1 ≤ i ≤ n \theta^{(n)}(f):=\left(f\left(\frac{i-1}{n}\right)\right)_{1\le i\le n} θ ( n ) ( f ) := ( f ( n i − 1 ) ) 1 ≤ i ≤ n ≍ \asymp ≍ f f f
Proposition 2.4. Consider the weights θ ( n ) ( f ) \theta^{(n)}(f) θ ( n ) ( f ) m k ( n ) m_k^{(n)} m k ( n ) Theorem 2.1 . For each k ∈ N 0 k\in\mathbb{N}_0 k ∈ N 0
A k : = { x ∈ ( 0 , 1 ) : k ≤ − log f ( x ) < k + 1 } and p k : = Leb ( A k ) . A_k:=\{x\in(0,1): k\le-\log f(x)<k+1\}\quad\text{and}\quad p_k:=\operatorname{Leb}(A_k). A k := { x ∈ ( 0 , 1 ) : k ≤ − log f ( x ) < k + 1 } and p k := Leb ( A k ) . Assume that the sequence ( p k ) k ≥ 0 (p_k)_{k\ge0} ( p k ) k ≥ 0 − log f -\log f − log f
∑ k ∈ N 0 m k ( n ) ≍ ∑ k ∈ N 0 min { n p k , n p k } = : ψ f ( n ) . \sum_{k\in\mathbb{N}_0}\sqrt{m_k^{(n)}}\asymp\sum_{k\in\mathbb{N}_0}\min\{np_k,\sqrt{np_k}\}=:\psi_f(n). k ∈ N 0 ∑ m k ( n ) ≍ k ∈ N 0 ∑ min { n p k , n p k } =: ψ f ( n ) . Proof. With our definition, m k ( n ) m_k^{(n)} m k ( n ) i ∈ [ 0 , n − 1 ] i\in[0,n-1] i ∈ [ 0 , n − 1 ] i / n i/n i / n A k A_k A k p k p_k p k
n p k − 1 ≤ m k ( n ) ≤ n p k + 1. (5) np_k-1\le m_k^{(n)}\le np_k+1. \tag*{(5)} n p k − 1 ≤ m k ( n ) ≤ n p k + 1. (5) Let K n ∈ N 0 K_n\in\mathbb{N}_0 K n ∈ N 0 p k ≥ 2 / n p_k\ge2/n p k ≥ 2/ n k ≤ K n k\le K_n k ≤ K n p k < 2 / n p_k<2/n p k < 2/ n k > K n k>K_n k > K n k ≤ K n k\le K_n k ≤ K n 1 2 n p k ≤ m k ( n ) ≤ 2 n p k \frac{1}{2}np_k\le m_k^{(n)}\le2np_k 2 1 n p k ≤ m k ( n ) ≤ 2 n p k
1 2 ∑ 0 ≤ k ≤ K n min { n p k , n p k } ≤ ∑ 0 ≤ k ≤ K n m k ( n ) ≤ 2 ∑ 0 ≤ k ≤ K n min { n p k , n p k } . (6) \frac{1}{2}\sum_{0\le k\le K_n}\min\{np_k,\sqrt{np_k}\}\le\sum_{0\le k\le K_n}\sqrt{m_k^{(n)}}\le2\sum_{0\le k\le K_n}\min\{np_k,\sqrt{np_k}\}. \tag*{(6)} 2 1 0 ≤ k ≤ K n ∑ min { n p k , n p k } ≤ 0 ≤ k ≤ K n ∑ m k ( n ) ≤ 2 0 ≤ k ≤ K n ∑ min { n p k , n p k } . (6) On the other hand, for k > K n k>K_n k > K n n p k < 2 np_k<2 n p k < 2 m k ( n ) ≤ 3 m_k^{(n)}\le3 m k ( n ) ≤ 3
1 2 n p k ≤ min { n p k , n p k } ≤ n p k and 1 2 m k ( n ) ≤ m k ( n ) ≤ m k ( n ) . (7) \frac{1}{2}np_k\le\min\{np_k,\sqrt{np_k}\}\le np_k
\quad\text{and}\quad
\frac{1}{2}m_k^{(n)}\le\sqrt{m_k^{(n)}}\le m_k^{(n)}. \tag*{(7)} 2 1 n p k ≤ min { n p k , n p k } ≤ n p k and 2 1 m k ( n ) ≤ m k ( n ) ≤ m k ( n ) . (7) Hence, it remains only to argue that
∑ k > K n m k ( n ) ≍ ∑ k > K n n p k \sum_{k>K_n}m_k^{(n)}\asymp\sum_{k>K_n}np_k k > K n ∑ m k ( n ) ≍ k > K n ∑ n p k in the right sense. However, observe that the above quantities are equal to
# { i ∈ [ n ] : − log f ( i − 1 n ) ≥ K n + 1 } , resp. n Leb { x ∈ ( 0 , 1 ) : − log f ( x ) ≥ K n + 1 } . \#\left\{i\in[n]:-\log f\left(\frac{i-1}{n}\right)\ge K_n+1\right\},\quad\text{resp.}\quad n\operatorname{Leb}\{x\in(0,1):-\log f(x)\ge K_n+1\}. # { i ∈ [ n ] : − log f ( n i − 1 ) ≥ K n + 1 } , resp. n Leb { x ∈ ( 0 , 1 ) : − log f ( x ) ≥ K n + 1 } . Thanks to the monotony of f f f { x ∈ ( 0 , 1 ) : − log f ( x ) ≥ K n + 1 } \{x\in(0,1):-\log f(x)\ge K_n+1\} { x ∈ ( 0 , 1 ) : − log f ( x ) ≥ K n + 1 } ( 1 − ε n , 1 ) (1-\varepsilon_n,1) ( 1 − ε n , 1 ) ( i − 1 ) / n (i-1)/n ( i − 1 ) / n
∣ ∑ k > K n m k ( n ) − ∑ k > K n n p k ∣ ≤ 2. (8) \left|\sum_{k>K_n}m_k^{(n)}-\sum_{k>K_n}np_k\right|\le2. \tag*{(8)} k > K n ∑ m k ( n ) − k > K n ∑ n p k ≤ 2. (8) Using eqs. (6) to (8), it is easy to conclude the proof.
Remark 2.5. One could wish to consider functions f f f ( 0 , 1 ) (0,1) ( 0 , 1 ) 0 0 0 θ i : = f ( i n + 1 ) \theta_i:=f\left(\frac{i}{n+1}\right) θ i := f ( n + 1 i ) f f f k k k Z \mathbb{Z} Z ( p − k ) k ≥ 0 (p_{-k})_{k\ge0} ( p − k ) k ≥ 0 k k k A − k ( f ) A_{-k}^{(f)} A − k ( f ) f f f A k − 1 ( 1 / f ) A_{k-1}^{(1/f)} A k − 1 ( 1/ f ) 1 / f 1/f 1/ f x ↦ f ( x ) x \mapsto f(x) x ↦ f ( x ) x ↦ f ( 1 − x ) − 1 x \mapsto f(1-x)^{-1} x ↦ f ( 1 − x ) − 1 1 1 1
f 1 ( x ) : = min { 1 , f ( x ) } and f 2 ( x ) : = min { 1 , 1 f ( 1 − x ) } , f_1(x):=\min\{1,f(x)\}\qquad\text{and}\qquad f_2(x):=\min\left\{1,\frac{1}{f(1-x)}\right\}, f 1 ( x ) := min { 1 , f ( x )} and f 2 ( x ) := min { 1 , f ( 1 − x ) 1 } , and m k ( n ) m_k^{(n)} m k ( n ) θ i ( n ) : = f ( i n + 1 ) \theta_i^{(n)}:=f\left(\frac{i}{n+1}\right) θ i ( n ) := f ( n + 1 i ) f 1 f_1 f 1 f 2 f_2 f 2
∑ k ∈ Z m k ( n ) ≍ ψ f 1 ( n ) + ψ f 2 ( n ) . \sum_{k\in\mathbb{Z}}\sqrt{m_k^{(n)}}\asymp\psi_{f_1}(n)+\psi_{f_2}(n). k ∈ Z ∑ m k ( n ) ≍ ψ f 1 ( n ) + ψ f 2 ( n ) . ▲
Remark 2.6. If f f f ( 0 , 1 ) (0,1) ( 0 , 1 ) p k = f − 1 ( e − ( k + 1 ) ) − f − 1 ( e − k ) p_k=f^{-1}(e^{-(k+1)})-f^{-1}(e^{-k}) p k = f − 1 ( e − ( k + 1 ) ) − f − 1 ( e − k ) k ∈ N 0 k\in\mathbb{N}_0 k ∈ N 0 k ∈ N 0 k\in\mathbb{N}_0 k ∈ N 0 inf f = 0 \inf f=0 inf f = 0 f f f [ 0 , 1 ) [0,1) [ 0 , 1 ) ψ f ( n ) ≍ n \psi_f(n)\asymp\sqrt{n} ψ f ( n ) ≍ n m k ( n ) = 0 m_k^{(n)}=0 m k ( n ) = 0 k > sup ( − log f ) k>\sup(-\log f) k > sup ( − log f )
▲
Remark 2.7. In the present context, if τ n \tau_n τ n θ ( n ) ( f ) \theta^{(n)}(f) θ ( n ) ( f ) E [ LIS ( τ n ) ] = o ( n ) \mathbb{E}[\operatorname{LIS}(\tau_n)]=o(n) E [ LIS ( τ n )] = o ( n ) f : [ 0 , 1 ) → ( 0 , ∞ ) f:[0,1)\to(0,\infty) f : [ 0 , 1 ) → ( 0 , ∞ ) Theorem 1.4 , and the fact that the limit permuton μ f \mu_f μ f [5 Proposition 2.3] or [Dub24, Proposition 2.1]. In contrast, if one considers e.g. the “exponential Sukhatme” weights θ k : = α − k \theta_k:=\alpha^{-k} θ k := α − k α > 1 \alpha>1 α > 1 Theorem 1.4 does not apply and Theorem 2.1 gives that E [ LIS ( τ n ) ] ≍ n \mathbb{E}[\operatorname{LIS}(\tau_n)]\asymp n E [ LIS ( τ n )] ≍ n
▲
Now, let us give criteria for ψ f ( n ) \psi_f(n) ψ f ( n ) n \sqrt{n} n n β n^\beta n β β ∈ ( 1 / 2 , 1 ) \beta\in(1/2,1) β ∈ ( 1/2 , 1 )
Lemma 2.8. Let ( p k ) k ≥ 0 (p_k)_{k\geq0} ( p k ) k ≥ 0 n ∈ N ↦ ψ f ( n ) n\in\mathbb{N}\mapsto\psi_f(n) n ∈ N ↦ ψ f ( n )
ψ f ( n ) = O ( n ) if and only if ∑ k ≥ 0 p k < ∞ . \psi_f(n)=O(\sqrt{n})\quad\text{if and only if}\quad\sum_{k\geq0}\sqrt{p_k}<\infty. ψ f ( n ) = O ( n ) if and only if k ≥ 0 ∑ p k < ∞. Proof. First, assume that the family ( p k ) k ≥ 0 (\sqrt{p_k})_{k\geq0} ( p k ) k ≥ 0 ψ f ( n ) \psi_f(n) ψ f ( n )
ψ f ( n ) = ∑ k ≥ 0 min { n p k , n p k } ≤ n ∑ k ≥ 0 p k = O ( n ) . \psi_f(n)=\sum_{k\geq0}\min\{np_k,\sqrt{np_k}\}\leq\sqrt{n}\sum_{k\geq0}\sqrt{p_k}=O(\sqrt{n}). ψ f ( n ) = k ≥ 0 ∑ min { n p k , n p k } ≤ n k ≥ 0 ∑ p k = O ( n ) . Now, assume instead that ψ f ( n ) = O ( n ) \psi_f(n)=O(\sqrt{n}) ψ f ( n ) = O ( n ) K ∈ N K\in\mathbb{N} K ∈ N n 0 = n 0 ( K ) n_0=n_0(K) n 0 = n 0 ( K )
for all n ≥ n 0 n\geq n_0 n ≥ n 0 k ∈ [ 0 , K ] k\in[0,K] k ∈ [ 0 , K ] p k > 0 p_k>0 p k > 0 n p k ≥ 1 np_k\geq1 n p k ≥ 1
so that min { n p k , n p k } = n p k \min\{np_k,\sqrt{np_k}\}=\sqrt{np_k} min { n p k , n p k } = n p k n ≥ n 0 n\geq n_0 n ≥ n 0 k ∈ [ 0 , K ] k\in[0,K] k ∈ [ 0 , K ]
∑ k = 0 K p k ≤ ψ f ( n ) n ≤ C \sum_{k=0}^{K}\sqrt{p_k}\leq\frac{\psi_f(n)}{\sqrt{n}}\leq C k = 0 ∑ K p k ≤ n ψ f ( n ) ≤ C for some absolute constant C > 0 C>0 C > 0 K → ∞ K\to\infty K → ∞
Example 2.9. Thanks to Proposition 2.4 and Lemma 2.8 , we can easily find functions f f f n \sqrt{n} n
Let α > 0 \alpha>0 α > 0 f : x ∈ [ 0 , 1 ] ↦ ( 1 − x ) α f:x\in[0,1]\mapsto(1-x)^\alpha f : x ∈ [ 0 , 1 ] ↦ ( 1 − x ) α − log f -\log f − log f p k = e − k / α ( 1 − e − 1 / α ) p_k=e^{-k/\alpha}(1-e^{-1/\alpha}) p k = e − k / α ( 1 − e − 1/ α ) k ≥ 0 k\geq0 k ≥ 0 ∑ k p k < ∞ \sum_k\sqrt{p_k}<\infty ∑ k p k < ∞ θ i = n − i + 1 \theta_i=n-i+1 θ i = n − i + 1 θ i = ( n − i + 1 ) α \theta_i=(n-i+1)^\alpha θ i = ( n − i + 1 ) α n \sqrt{n} n
Let α > 0 \alpha>0 α > 0 f : x ∈ [ 0 , 1 ] ↦ exp [ 1 − ( 1 − x ) − α ] f:x\in[0,1]\mapsto\exp[1-(1-x)^{-\alpha}] f : x ∈ [ 0 , 1 ] ↦ exp [ 1 − ( 1 − x ) − α ] − log f -\log f − log f p k ≍ k − α + 1 α p_k\asymp k^{-\frac{\alpha+1}{\alpha}} p k ≍ k − α α + 1 k ≥ 1 k\geq1 k ≥ 1 ∑ k p k < ∞ \sum_k\sqrt{p_k}<\infty ∑ k p k < ∞ α < 1 \alpha<1 α < 1 θ i = exp [ − ( n n − i + 1 ) α ] \theta_i=\exp\left[-\left(\frac{n}{n-i+1}\right)^\alpha\right] θ i = exp [ − ( n − i + 1 n ) α ] n \sqrt{n} n α < 1 \alpha<1 α < 1
Example 2.10. Assume that p k ≍ k − γ p_k \asymp k^{-\gamma} p k ≍ k − γ γ > 1 \gamma> 1 γ > 1
ψ f ( n ) ≍ { n if γ > 2 ; n log n if γ = 2 ; n 1 / γ if γ < 2. \psi_f(n) \asymp
\begin{cases}
\sqrt{n} & \text{if } \gamma> 2;\\
\sqrt{n}\log n & \text{if } \gamma= 2;\\
n^{1/\gamma} & \text{if } \gamma< 2.
\end{cases} ψ f ( n ) ≍ ⎩ ⎨ ⎧ n n log n n 1/ γ if γ > 2 ; if γ = 2 ; if γ < 2. In particular, for f : x ∈ [ 0 , 1 ] ↦ exp [ 1 − ( 1 − x ) − α ] f:x \in[0,1] \mapsto\exp[1-(1-x)^{-\alpha}] f : x ∈ [ 0 , 1 ] ↦ exp [ 1 − ( 1 − x ) − α ] n \sqrt{n} n α < 1 \alpha< 1 α < 1 n log n \sqrt{n}\log n n log n α = 1 \alpha= 1 α = 1 n α α + 1 n^{\frac{\alpha}{\alpha+1}} n α + 1 α α > 1 \alpha> 1 α > 1
Finally, we conclude with another formula which can be convenient for the computation of ψ f ( n ) \psi_f(n) ψ f ( n )
Lemma 2.11. Let f f f [ 0 , 1 ] [0,1] [ 0 , 1 ] [ 0 , 1 ) [0,1) [ 0 , 1 ) f ( 0 ) = 1 f(0)=1 f ( 0 ) = 1 f ( 1 ) = 0 f(1)=0 f ( 1 ) = 0 f f f C 1 C^1 C 1 [ 0 , 1 ] [0,1] [ 0 , 1 ] H : = − log f H := -\log f H := − log f
p k ≤ 1 H ′ ∘ H − 1 ( k ) = − e − k f ′ ∘ f − 1 ( e − k ) ≤ p k − 1 p_k \le\frac{1}{H' \circ H^{-1}(k)} = \frac{-e^{-k}}{f' \circ f^{-1}(e^{-k})} \le p_{k-1} p k ≤ H ′ ∘ H − 1 ( k ) 1 = f ′ ∘ f − 1 ( e − k ) − e − k ≤ p k − 1 for all k ∈ N k \in\mathbb{N} k ∈ N
Proof. Observe that, thanks to our assumptions, H H H ( 0 , 1 ) (0,1) ( 0 , 1 ) ( 0 , ∞ ) (0,\infty) ( 0 , ∞ ) H − 1 H^{-1} H − 1 C 1 C^1 C 1 ( 0 , 1 ) (0,1) ( 0 , 1 ) k ∈ N k \in\mathbb{N} k ∈ N p k = H − 1 ( k + 1 ) − H − 1 ( k ) p_k=H^{-1}(k+1)-H^{-1}(k) p k = H − 1 ( k + 1 ) − H − 1 ( k ) ξ k ∈ [ k , k + 1 ] \xi_k \in[k,k+1] ξ k ∈ [ k , k + 1 ]
p k = ( H − 1 ) ′ ( ξ k ) = 1 H ′ ∘ H − 1 ( ξ k ) . p_k=(H^{-1})'(\xi_k)=\frac{1}{H' \circ H^{-1}(\xi_k)}. p k = ( H − 1 ) ′ ( ξ k ) = H ′ ∘ H − 1 ( ξ k ) 1 . Since H H H
1 H ′ ∘ H − 1 ( k + 1 ) ≤ p k ≤ 1 H ′ ∘ H − 1 ( k ) , \frac{1}{H' \circ H^{-1}(k+1)} \le p_k \le\frac{1}{H' \circ H^{-1}(k)}, H ′ ∘ H − 1 ( k + 1 ) 1 ≤ p k ≤ H ′ ∘ H − 1 ( k ) 1 , and the conclusion follows.
A superuniformity property
Lemma 2.12. Let 0 ≤ u ≤ v ≤ ∞ 0 \le u \le v \le\infty 0 ≤ u ≤ v ≤ ∞ v > 0 v > 0 v > 0
G : θ ∈ [ 0 , ∞ ) ↦ 1 − e − θ u 1 − e − θ v , G:\theta\in[0,\infty) \mapsto\frac{1-e^{-\theta u}}{1-e^{-\theta v}}, G : θ ∈ [ 0 , ∞ ) ↦ 1 − e − θ v 1 − e − θ u , with convention e − θ × ∞ = 0 e^{-\theta\times\infty}=0 e − θ × ∞ = 0
Proof. For v = ∞ v=\infty v = ∞ v < ∞ v<\infty v < ∞ u e θ v − v e θ u + ( v − u ) u e^{\theta v}-v e^{\theta u}+(v-u) u e θ v − v e θ u + ( v − u ) 0 0 0 θ = 0 \theta=0 θ = 0 u v ( e θ v − e θ u ) ≥ 0 uv(e^{\theta v}-e^{\theta u}) \ge0 uv ( e θ v − e θ u ) ≥ 0
Proposition 2.13. Let θ 1 ≥ ⋯ ≥ θ k \theta_1 \ge\cdots\ge\theta_k θ 1 ≥ ⋯ ≥ θ k 0 ≤ c < d ≤ ∞ 0 \le c < d \le\infty 0 ≤ c < d ≤ ∞ i ∈ [ k ] i \in[k] i ∈ [ k ] Z i Z_i Z i E i / θ i E_i/\theta_i E i / θ i [ c , d ] [c,d] [ c , d ] E i ∼ Exp ( 1 ) E_i \sim\operatorname{Exp}(1) E i ∼ Exp ( 1 ) LIS ( Z 1 , … , Z k ) \operatorname{LIS}(Z_1,\ldots,Z_k) LIS ( Z 1 , … , Z k ) LIS ( σ k ) \operatorname{LIS}(\sigma_k) LIS ( σ k ) σ k ∼ Unif ( S k ) \sigma_k \sim\operatorname{Unif}(\mathfrak{S}_k) σ k ∼ Unif ( S k )
Proof. If d = ∞ d=\infty d = ∞ i ∈ [ k ] i \in[k] i ∈ [ k ] G i G_i G i Z i Z_i Z i
for t ∈ [ c , d ] , G i ( t ) = P ( Z i ≤ t ) = ∫ c t θ i e − s θ i d s ∫ c d θ i e − s θ i d s = e − c θ i − e − t θ i e − c θ i − e − d θ i = 1 − e − ( t − c ) θ i 1 − e − ( d − c ) θ i . \text{for }t \in[c,d],\qquad G_i(t)=\mathbb{P}(Z_i \le t)=\frac{\int_c^t \theta_i e^{-s\theta_i}\,\mathrm{d}s}{\int_c^d \theta_i e^{-s\theta_i}\,\mathrm{d}s}=\frac{e^{-c\theta_i}-e^{-t\theta_i}}{e^{-c\theta_i}-e^{-d\theta_i}}=\frac{1-e^{-(t-c)\theta_i}}{1-e^{-(d-c)\theta_i}}. for t ∈ [ c , d ] , G i ( t ) = P ( Z i ≤ t ) = ∫ c d θ i e − s θ i d s ∫ c t θ i e − s θ i d s = e − c θ i − e − d θ i e − c θ i − e − t θ i = 1 − e − ( d − c ) θ i 1 − e − ( t − c ) θ i . By Lemma 2.12, we know that for any fixed t ∈ ( c , d ) t \in(c,d) t ∈ ( c , d )
for all 1 ≤ i < j ≤ k , G i ( t ) ≥ G j ( t ) . (9) \text{for all }1 \le i < j \le k,\qquad G_i(t) \ge G_j(t). \tag*{(9)} for all 1 ≤ i < j ≤ k , G i ( t ) ≥ G j ( t ) . (9) Now, let U 1 , … , U k U_1,\ldots,U_k U 1 , … , U k [ 0 , 1 ] [0,1] [ 0 , 1 ] ( Z 1 , … , Z k ) (Z_1,\ldots,Z_k) ( Z 1 , … , Z k ) ( G 1 − 1 ( U 1 ) , … , G k − 1 ( U k ) ) (G_1^{-1}(U_1),\ldots,G_k^{-1}(U_k)) ( G 1 − 1 ( U 1 ) , … , G k − 1 ( U k ))
LIS ( U 1 , … , U k ) ≤ LIS ( G 1 − 1 ( U 1 ) , … , G k − 1 ( U k ) ) . (10) \operatorname{LIS}(U_1,\ldots,U_k) \le\operatorname{LIS}(G_1^{-1}(U_1),\ldots,G_k^{-1}(U_k)). \tag*{(10)} LIS ( U 1 , … , U k ) ≤ LIS ( G 1 − 1 ( U 1 ) , … , G k − 1 ( U k )) . (10) Indeed, if i < j i<j i < j U i < U j U_i<U_j U i < U j
G i − 1 ( U i ) < G i − 1 ( U j ) = G i − 1 ( G j ( G j − 1 ( U j ) ) ) ≤ G i − 1 ( G i ( G j − 1 ( U j ) ) ) = G j − 1 ( U j ) , G_i^{-1}(U_i)<G_i^{-1}(U_j)=G_i^{-1}(G_j(G_j^{-1}(U_j)))\le G_i^{-1}(G_i(G_j^{-1}(U_j)))=G_j^{-1}(U_j), G i − 1 ( U i ) < G i − 1 ( U j ) = G i − 1 ( G j ( G j − 1 ( U j ))) ≤ G i − 1 ( G i ( G j − 1 ( U j ))) = G j − 1 ( U j ) , where we used that t ↦ G i ( t ) t\mapsto G_i(t) t ↦ G i ( t ) LIS ( Z 1 , … , Z k ) \operatorname{LIS}(Z_1,\ldots,Z_k) LIS ( Z 1 , … , Z k ) LIS ( U 1 , … , U k ) \operatorname{LIS}(U_1,\ldots,U_k) LIS ( U 1 , … , U k ) LIS ( U 1 , … , U k ) \operatorname{LIS}(U_1,\ldots,U_k) LIS ( U 1 , … , U k )
Corollary 2.14. For each n ∈ N n\in\mathbb{N} n ∈ N θ ( n ) = ( θ 1 ( n ) ≥ ⋯ ≥ θ n ( n ) ) \boldsymbol{\theta}^{(n)}=(\theta_1^{(n)}\ge\cdots\ge\theta_n^{(n)}) θ ( n ) = ( θ 1 ( n ) ≥ ⋯ ≥ θ n ( n ) ) τ n \tau_n τ n ( θ ( n ) ) (\boldsymbol{\theta}^{(n)}) ( θ ( n ) ) ε > 0 \varepsilon>0 ε > 0
P ( LIS ( τ n ) ≤ ( 2 − ε ) n ) → n → ∞ 0. \mathbb{P}\left(\operatorname{LIS}(\tau_n)\le(2-\varepsilon)\sqrt{n}\right)\xrightarrow[n\to\infty]{}0. P ( LIS ( τ n ) ≤ ( 2 − ε ) n ) n → ∞ 0. Proof. By Lemma 1.3 , we know that LIS ( τ n ) \operatorname{LIS}(\tau_n) LIS ( τ n ) LIS ( E 1 / θ 1 ( n ) , … , E n / θ n ( n ) ) \operatorname{LIS}(E_1/\theta_1^{(n)},\ldots,E_n/\theta_n^{(n)}) LIS ( E 1 / θ 1 ( n ) , … , E n / θ n ( n ) ) E 1 , … , E n E_1,\ldots,E_n E 1 , … , E n Exp ( 1 ) \operatorname{Exp}(1) Exp ( 1 ) Theorem 1.1 and Proposition 2.13 (with c = 0 c=0 c = 0 d = ∞ d=\infty d = ∞
Proof of th: LIS growth rate - general
Lemma 2.15. Let Y 1 , … , Y m Y_1,\ldots,Y_m Y 1 , … , Y m Y i Y_i Y i g i g_i g i R \mathbb{R} R g g g R \mathbb{R} R R ≥ 1 R\ge1 R ≥ 1 i ∈ [ m ] i\in[m] i ∈ [ m ] x ∈ R x\in\mathbb{R} x ∈ R g i ( x ) ≤ R g ( x ) g_i(x)\le Rg(x) g i ( x ) ≤ R g ( x ) δ > 0 \delta>0 δ > 0
P ( LIS ( Y 1 , … , Y m ) ≥ ( 1 + δ ) e R m ) ≤ ( 1 1 + δ ) R m and E [ LIS ( Y 1 , … , Y m ) ] ≤ 2 e R m . \mathbb{P}\left(\operatorname{LIS}(Y_1,\ldots,Y_m)\ge(1+\delta)e\sqrt{Rm}\right)\le\left(\frac{1}{1+\delta}\right)^{\sqrt{Rm}}
\qquad\text{and}\qquad
\mathbb{E}[\operatorname{LIS}(Y_1,\ldots,Y_m)]\le2e\sqrt{Rm}. P ( LIS ( Y 1 , … , Y m ) ≥ ( 1 + δ ) e R m ) ≤ ( 1 + δ 1 ) R m and E [ LIS ( Y 1 , … , Y m )] ≤ 2 e R m . Proof. For any 1 ≤ ℓ ≤ m 1\le\ell\le m 1 ≤ ℓ ≤ m i 1 < ⋯ < i ℓ i_1<\cdots<i_\ell i 1 < ⋯ < i ℓ
P ( Y i 1 < ⋯ < Y i ℓ ) = ∫ y 1 < ⋯ < y ℓ ∏ 1 ≤ k ≤ ℓ ( g i k ( y k ) d y k ) ≤ R ℓ ∫ y 1 < ⋯ < y ℓ ∏ 1 ≤ k ≤ ℓ ( g ( y k ) d y k ) = R ℓ ℓ ! . \mathbb{P}(Y_{i_1}<\cdots<Y_{i_\ell})=\int_{y_1<\cdots<y_\ell}\prod_{1\le k\le\ell}(g_{i_k}(y_k)\,dy_k)\le R^\ell\int_{y_1<\cdots<y_\ell}\prod_{1\le k\le\ell}(g(y_k)\,dy_k)=\frac{R^\ell}{\ell!}. P ( Y i 1 < ⋯ < Y i ℓ ) = ∫ y 1 < ⋯ < y ℓ 1 ≤ k ≤ ℓ ∏ ( g i k ( y k ) d y k ) ≤ R ℓ ∫ y 1 < ⋯ < y ℓ 1 ≤ k ≤ ℓ ∏ ( g ( y k ) d y k ) = ℓ ! R ℓ . Thus, a union bound and a Stirling bound lead to
P ( LIS ( Y 1 , … , Y m ) ≥ ℓ ) ≤ ( m ℓ ) R ℓ ℓ ! ≤ ( m R ) ℓ ( ℓ ! ) 2 ≤ ( e 2 R m ℓ 2 ) ℓ 1 2 π ℓ . \mathbb{P}(\operatorname{LIS}(Y_1,\ldots,Y_m)\ge\ell)\le\binom{m}{\ell}\frac{R^\ell}{\ell!}\le\frac{(mR)^\ell}{(\ell!)^2}\le\left(\frac{e^2Rm}{\ell^2}\right)^\ell\frac{1}{2\pi\ell}. P ( LIS ( Y 1 , … , Y m ) ≥ ℓ ) ≤ ( ℓ m ) ℓ ! R ℓ ≤ ( ℓ ! ) 2 ( m R ) ℓ ≤ ( ℓ 2 e 2 R m ) ℓ 2 π ℓ 1 . From there, the claimed probability bound is straightforward. Finally:
E [ LIS ( Y 1 , … , Y m ) ] ≤ e R m + ∑ ℓ = ⌈ e R m ⌉ m P ( LIS ( Y 1 , … , Y m ) ≥ ℓ ) ≤ e R m + ∑ ℓ = ⌈ e R m ⌉ m 1 2 π ℓ , \mathbb{E}[\operatorname{LIS}(Y_1,\ldots,Y_m)]\le e\sqrt{Rm}+\sum_{\ell=\lceil e\sqrt{Rm}\rceil}^{m}\mathbb{P}(\operatorname{LIS}(Y_1,\ldots,Y_m)\ge\ell)\le e\sqrt{Rm}+\sum_{\ell=\lceil e\sqrt{Rm}\rceil}^{m}\frac{1}{2\pi\ell}, E [ LIS ( Y 1 , … , Y m )] ≤ e R m + ℓ = ⌈ e R m ⌉ ∑ m P ( LIS ( Y 1 , … , Y m ) ≥ ℓ ) ≤ e R m + ℓ = ⌈ e R m ⌉ ∑ m 2 π ℓ 1 , and the conclusion easily follows.
Proof of Theorem 2.1. To ease notation, we may omit the dependence on n n n Figure 3 for an illustration of this proof.
Figure 3. Illustration of the proof of Theorem 2.1 . The points ( θ i , E i ) (\theta_i,E_i) ( θ i , E i ) [ k , k + 1 ) × [ 0 , ∞ ) [k,k+1)\times[0,\infty) [ k , k + 1 ) × [ 0 , ∞ ) Proposition 2.13 provides a lower bound for the LIS on each square [ k , k + 1 ) 2 [k,k+1)^2 [ k , k + 1 ) 2
Let E 1 , … , E n E_1,\ldots,E_n E 1 , … , E n E i E_i E i Exp ( θ i ) \operatorname{Exp}(\theta_i) Exp ( θ i ) Lemma 1.3 , LIS ( τ n ) \operatorname{LIS}(\tau_n) LIS ( τ n ) LIS ( E 1 , … , E n ) \operatorname{LIS}(E_1,\ldots,E_n) LIS ( E 1 , … , E n )
Upper bound. Recall that for any k ∈ Z k\in\mathbb{Z} k ∈ Z i ∈ B k i\in B_k i ∈ B k e − k − 1 ≤ θ i ≤ e − k e^{-k-1}\le\theta_i\le e^{-k} e − k − 1 ≤ θ i ≤ e − k E i E_i E i x ↦ R g k ( x ) x\mapsto Rg_k(x) x ↦ R g k ( x ) R : = e R:=e R := e g k g_k g k Exp ( e − k − 1 ) \operatorname{Exp}(e^{-k-1}) Exp ( e − k − 1 )
E [ LIS ( E i , i ∈ B k ) ] ≤ 2 e 3 / 2 m k , \mathbb{E}[\operatorname{LIS}(E_i,i\in B_k)]\le2e^{3/2}\sqrt{m_k}, E [ LIS ( E i , i ∈ B k )] ≤ 2 e 3/2 m k , and we conclude by noting that
LIS ( E 1 , … , E n ) ≤ ∑ k ∈ Z LIS ( E i , i ∈ B k ) . \operatorname{LIS}(E_1,\ldots,E_n) \le\sum_{k\in\mathbb{Z}} \operatorname{LIS}(E_i,i\in B_k). LIS ( E 1 , … , E n ) ≤ k ∈ Z ∑ LIS ( E i , i ∈ B k ) . Lower bound. For k ∈ Z k\in\mathbb{Z} k ∈ Z J k : = [ e k , e k + 1 ) J_k:=[e^k,e^{k+1}) J k := [ e k , e k + 1 )
LIS ( E 1 , … , E n ) ≥ ∑ k ∈ Z LIS ( { E i : i ∈ B k , E i ∈ J k } ) . (11) \operatorname{LIS}(E_1,\ldots,E_n) \ge\sum_{k\in\mathbb{Z}} \operatorname{LIS}(\{E_i:i\in B_k,E_i\in J_k\}). \tag*{(11)} LIS ( E 1 , … , E n ) ≥ k ∈ Z ∑ LIS ({ E i : i ∈ B k , E i ∈ J k }) . (11) Indeed, this follows from two observations. Consider k < k ′ k<k' k < k ′ i ∈ B k i\in B_k i ∈ B k j ∈ B k ′ j\in B_{k'} j ∈ B k ′ i < j i<j i < j E i ∈ J k E_i\in J_k E i ∈ J k E j ∈ J k ′ E_j\in J_{k'} E j ∈ J k ′ E i < E j E_i<E_j E i < E j { E i : i ∈ B k , E i ∈ J k } \{E_i:i\in B_k,E_i\in J_k\} { E i : i ∈ B k , E i ∈ J k } { E 1 , … , E n } \{E_1,\ldots,E_n\} { E 1 , … , E n }
Now, for each k ∈ Z k\in\mathbb{Z} k ∈ Z
R k : = { i ∈ B k : E i ∈ J k } and r k : = # R k . R_k:=\{i\in B_k:E_i\in J_k\}\quad\text{and}\quad r_k:=\#R_k. R k := { i ∈ B k : E i ∈ J k } and r k := # R k . For i ∈ B k i\in B_k i ∈ B k i ∈ R k i\in R_k i ∈ R k E i E_i E i Exp ( θ i ) \operatorname{Exp}(\theta_i) Exp ( θ i ) J k J_k J k Proposition 2.13 implies that
E [ LIS ( { E i , i ∈ R k } ) ∣ R k ] ≥ E [ LIS ( σ r k ) ∣ R k ] = ℓ r k , \mathbb{E}[\operatorname{LIS}(\{E_i,i\in R_k\})\mid R_k]\ge\mathbb{E}[\operatorname{LIS}(\sigma_{r_k})\mid R_k]=\ell_{r_k}, E [ LIS ({ E i , i ∈ R k }) ∣ R k ] ≥ E [ LIS ( σ r k ) ∣ R k ] = ℓ r k , where σ r k \sigma_{r_k} σ r k r k r_k r k ℓ r ≥ r \ell_r\ge\sqrt{r} ℓ r ≥ r r ∈ N 0 r\in\mathbb{N}_0 r ∈ N 0
E [ LIS ( { E i , i ∈ R k } ) ] ≥ E [ r k ] . (12) \mathbb{E}[\operatorname{LIS}(\{E_i,i\in R_k\})]\ge\mathbb{E}[\sqrt{r_k}]. \tag*{(12)} E [ LIS ({ E i , i ∈ R k })] ≥ E [ r k ] . (12) Now, for i ∈ B k i\in B_k i ∈ B k E i ∈ J k E_i\in J_k E i ∈ J k e − θ i e k − e − θ i e k + 1 e^{-\theta_i e^k}-e^{-\theta_i e^{k+1}} e − θ i e k − e − θ i e k + 1 e − k − 1 ≤ θ i ≤ e − k e^{-k-1}\le\theta_i\le e^{-k} e − k − 1 ≤ θ i ≤ e − k p > 0 p>0 p > 0 S m k , p S_{m_k,p} S m k , p Bin ( m k , p ) \operatorname{Bin}(m_k,p) Bin ( m k , p )
E [ r k ] ≥ E [ S m k , p ] . (13) \mathbb{E}[\sqrt{r_k}]\ge\mathbb{E}[\sqrt{S_{m_k,p}}]. \tag*{(13)} E [ r k ] ≥ E [ S m k , p ] . (13) In this context, it is easy to see that E [ S m , p ] ∼ m p \mathbb{E}[\sqrt{S_{m,p}}]\sim\sqrt{mp} E [ S m , p ] ∼ m p m → ∞ m\to\infty m → ∞ c > 0 c>0 c > 0 E [ S m , p ] ≥ c m \mathbb{E}[\sqrt{S_{m,p}}]\ge c\sqrt{m} E [ S m , p ] ≥ c m m ∈ N 0 m\in\mathbb{N}_0 m ∈ N 0
E [ LIS ( E 1 , … , E n ) ] ≥ c ∑ k ∈ Z m k \mathbb{E}[\operatorname{LIS}(E_1,\ldots,E_n)]\ge c\sum_{k\in\mathbb{Z}}\sqrt{m_k} E [ LIS ( E 1 , … , E n )] ≥ c k ∈ Z ∑ m k as desired.
A concentration inequality
In this short section, we explain why it is not restrictive to state Theorem 2.1 for the expectation of LIS ( τ n ) \operatorname{LIS}(\tau_n) LIS ( τ n )
Theorem 2.16 ([26 ] ). Let n ∈ N n \in\mathbb{N} n ∈ N Z 1 , … , Z n Z_1,\ldots,Z_n Z 1 , … , Z n independent random variables with values in a common space Z \mathcal{Z} Z h : Z n → R h:\mathcal{Z}^n\to\mathbb{R} h : Z n → R bounded differences property : for all i ∈ [ n ] i\in[n] i ∈ [ n ] z 1 , … , z n , w i ∈ Z z_1,\ldots,z_n,w_i\in\mathcal{Z} z 1 , … , z n , w i ∈ Z
∣ h ( z 1 , … , z n ) − h ( z 1 , … , w i , … , z n ) ∣ ≤ c \left|h(z_1,\ldots,z_n)-h(z_1,\ldots,w_i,\ldots,z_n)\right|\le c ∣ h ( z 1 , … , z n ) − h ( z 1 , … , w i , … , z n ) ∣ ≤ c for some constant c > 0 c>0 c > 0 λ > 0 \lambda>0 λ > 0
P ( ∣ h ( Z 1 , … , Z n ) − E [ h ( Z 1 , … , Z n ) ] ∣ > λ ) ≤ 2 exp ( − 2 λ 2 n c 2 ) . \mathbb{P}\left(\left|h(Z_1,\ldots,Z_n)-\mathbb{E}[h(Z_1,\ldots,Z_n)]\right|>\lambda\right)\le2\exp\left(-\frac{2\lambda^2}{nc^2}\right). P ( ∣ h ( Z 1 , … , Z n ) − E [ h ( Z 1 , … , Z n )] ∣ > λ ) ≤ 2 exp ( − n c 2 2 λ 2 ) . This inequality is readily applicable to the study of LIS of random permutations; see, e.g., [14 ] for the case of permuton samples. The Luce distribution is no exception to this:
Corollary 2.17. Let n ∈ N n\in\mathbb{N} n ∈ N τ n \tau_n τ n θ 1 , … , θ n \theta_1,\ldots,\theta_n θ 1 , … , θ n λ > 0 \lambda>0 λ > 0
P ( ∣ LIS ( τ n ) − E [ LIS ( τ n ) ] ∣ > λ ) ≤ 2 exp ( − 2 λ 2 n ) . \mathbb{P}\left(\left|\operatorname{LIS}(\tau_n)-\mathbb{E}[\operatorname{LIS}(\tau_n)]\right|>\lambda\right)\le2\exp\left(-\frac{2\lambda^2}{n}\right). P ( ∣ LIS ( τ n ) − E [ LIS ( τ n )] ∣ > λ ) ≤ 2 exp ( − n 2 λ 2 ) . Proof. Using Lemma 1.3, we see that LIS ( τ n ) \operatorname{LIS}(\tau_n) LIS ( τ n ) LIS ( E 1 , … , E n ) \operatorname{LIS}(E_1,\ldots,E_n) LIS ( E 1 , … , E n ) E i E_i E i i ∈ [ n ] i\in[n] i ∈ [ n ] Exp ( θ i ) \operatorname{Exp}(\theta_i) Exp ( θ i )
This allows us to deduce tail probabilities from estimates on E [ LIS ( τ n ) ] \mathbb{E}[\operatorname{LIS}(\tau_n)] E [ LIS ( τ n )]
Corollary 2.18. For each n ∈ N n\in\mathbb{N} n ∈ N θ ( n ) = ( θ 1 ≥ ⋯ ≥ θ n ) \theta^{(n)}=(\theta_1\ge\cdots\ge\theta_n) θ ( n ) = ( θ 1 ≥ ⋯ ≥ θ n ) non-increasing sequence of positive weights and let τ n \tau_n τ n ( θ ( n ) ) (\theta^{(n)}) ( θ ( n ) )
lim λ → ∞ lim inf n → ∞ P ( LIS ( τ n ) ∈ [ 1 λ E [ LIS ( τ n ) ] , λ E [ LIS ( τ n ) ] ] ) = 1. \lim_{\lambda\to\infty}\liminf_{n\to\infty}\mathbb{P}\left(\operatorname{LIS}(\tau_n)\in\left[\frac{1}{\lambda}\mathbb{E}[\operatorname{LIS}(\tau_n)],\lambda\mathbb{E}[\operatorname{LIS}(\tau_n)]\right]\right)=1. λ → ∞ lim n → ∞ lim inf P ( LIS ( τ n ) ∈ [ λ 1 E [ LIS ( τ n )] , λ E [ LIS ( τ n )] ] ) = 1. Proof. Recall that, by Proposition 2.13 and Theorem 1.1, E [ LIS ( τ n ) ] ≥ ℓ n ≥ n \mathbb{E}[\operatorname{LIS}(\tau_n)]\ge\ell_n\ge\sqrt{n} E [ LIS ( τ n )] ≥ ℓ n ≥ n n ∈ N n\in\mathbb{N} n ∈ N λ > 1 \lambda>1 λ > 1
P ( LIS ( τ n ) > λ E [ LIS ( τ n ) ] ) ≤ P ( ∣ LIS ( τ n ) − E [ LIS ( τ n ) ] ∣ > ( λ − 1 ) E [ LIS ( τ n ) ] ) ≤ 2 exp ( − 2 ( λ − 1 ) 2 ) \mathbb{P}\left(\operatorname{LIS}(\tau_n)>\lambda\mathbb{E}[\operatorname{LIS}(\tau_n)]\right)\le\mathbb{P}\left(\left|\operatorname{LIS}(\tau_n)-\mathbb{E}[\operatorname{LIS}(\tau_n)]\right|>(\lambda-1)\mathbb{E}[\operatorname{LIS}(\tau_n)]\right)\le2\exp\left(-2(\lambda-1)^2\right) P ( LIS ( τ n ) > λ E [ LIS ( τ n )] ) ≤ P ( ∣ LIS ( τ n ) − E [ LIS ( τ n )] ∣ > ( λ − 1 ) E [ LIS ( τ n )] ) ≤ 2 exp ( − 2 ( λ − 1 ) 2 ) by Corollary 2.17. This proves the upper tail decay1 λ > 2 \lambda>2 λ > 2
P ( LIS ( τ n ) < 1 λ E [ LIS ( τ n ) ] ) ≤ P ( ∣ LIS ( τ n ) − E [ LIS ( τ n ) ] ∣ > 1 2 E [ LIS ( τ n ) ] ) ≤ 2 exp ( − E [ LIS ( τ n ) ] 2 2 n ) . \mathbb{P}\left(\operatorname{LIS}(\tau_n)<\frac{1}{\lambda}\mathbb{E}[\operatorname{LIS}(\tau_n)]\right)\le\mathbb{P}\left(\left|\operatorname{LIS}(\tau_n)-\mathbb{E}[\operatorname{LIS}(\tau_n)]\right|>\frac{1}{2}\mathbb{E}[\operatorname{LIS}(\tau_n)]\right)\le2\exp\left(-\frac{\mathbb{E}[\operatorname{LIS}(\tau_n)]^2}{2n}\right). P ( LIS ( τ n ) < λ 1 E [ LIS ( τ n )] ) ≤ P ( ∣ LIS ( τ n ) − E [ LIS ( τ n )] ∣ > 2 1 E [ LIS ( τ n )] ) ≤ 2 exp ( − 2 n E [ LIS ( τ n ) ] 2 ) . Now, let us distinguish two cases. First, assume that E [ LIS ( τ n ) ] > λ n \mathbb{E}[\operatorname{LIS}(\tau_n)]>\lambda\sqrt{n} E [ LIS ( τ n )] > λ n
P ( LIS ( τ n ) < 1 λ E [ LIS ( τ n ) ] ) ≤ 2 exp ( − λ 2 / 2 ) . \mathbb{P}\left(\operatorname{LIS}(\tau_n)<\frac{1}{\lambda}\mathbb{E}[\operatorname{LIS}(\tau_n)]\right)\le2\exp\left(-\lambda^2/2\right). P ( LIS ( τ n ) < λ 1 E [ LIS ( τ n )] ) ≤ 2 exp ( − λ 2 /2 ) . Second, assume that E [ LIS ( τ n ) ] ≤ λ n \mathbb{E}[\operatorname{LIS}(\tau_n)]\le\lambda\sqrt{n} E [ LIS ( τ n )] ≤ λ n
P ( LIS ( τ n ) < 1 λ E [ LIS ( τ n ) ] ) ≤ P ( LIS ( τ n ) < n ) , \mathbb{P}\left(\operatorname{LIS}(\tau_n)<\frac{1}{\lambda}\mathbb{E}[\operatorname{LIS}(\tau_n)]\right)\le\mathbb{P}\left(\operatorname{LIS}(\tau_n)<\sqrt{n}\right), P ( LIS ( τ n ) < λ 1 E [ LIS ( τ n )] ) ≤ P ( LIS ( τ n ) < n ) , where the above goes to 0 0 0 n → ∞ n\to\infty n → ∞
Remark 2.19. One could use Talagrand’s inequality to get sharper tail bounds; see, e.g., [32 ] or [22 Theorem 2.29] . We leave such details to the reader. ▲
Computing the constant in the n \sqrt{n} n
The continuous Luce model
Let us discuss here what we may call the “continuous” Luce model, in opposition with the “discrete” Luce model. Recall (Theorem 1.4 ) that if θ ( n ) = ( θ 1 ( n ) , … , θ n ( n ) ) \theta^{(n)}=(\theta^{(n)}_1,\ldots,\theta^{(n)}_n) θ ( n ) = ( θ 1 ( n ) , … , θ n ( n ) ) f f f [ 0 , 1 ) [0,1) [ 0 , 1 ) θ ( n ) \theta^{(n)} θ ( n ) μ f \mu_f μ f
Lemma 3.1. Let μ f \mu_f μ f Theorem 1.4 . Then, for all n ∈ N n\in\mathbb{N} n ∈ N σ n , μ f \sigma_{n,\mu_f} σ n , μ f μ f \mu_f μ f f ( U ( 1 ) ) , … , f ( U ( n ) ) f(U_{(1)}),\ldots,f(U_{(n)}) f ( U ( 1 ) ) , … , f ( U ( n ) ) U ( 1 ) < … < U ( n ) U_{(1)}<\ldots<U_{(n)} U ( 1 ) < … < U ( n ) [ 0 , 1 ] [0,1] [ 0 , 1 ]
P ( σ n , μ f = σ ) = E [ P ( τ n U = σ ∣ U 1 , … , U n ) ] , \mathbb{P}(\sigma_{n,\mu_f}=\sigma)=\mathbb{E}\left[\mathbb{P}(\tau_n^{\mathrm{U}}=\sigma\mid U_1,\ldots,U_n)\right], P ( σ n , μ f = σ ) = E [ P ( τ n U = σ ∣ U 1 , … , U n ) ] , for any σ ∈ S n \sigma\in\mathfrak{S}_n σ ∈ S n τ n U \tau_n^{\mathrm{U}} τ n U f ( U ( 1 ) ) , … , f ( U ( n ) ) f(U_{(1)}),\ldots,f(U_{(n)}) f ( U ( 1 ) ) , … , f ( U ( n ) )
Therefore, we may say that σ n , μ f \sigma_{n,\mu_f} σ n , μ f f f f f f f θ ( n ) ( f ) : = ( f ( i − 1 n ) ) 1 ≤ i ≤ n \theta^{(n)}(f):=\left(f\left(\frac{i-1}{n}\right)\right)_{1\le i\le n} θ ( n ) ( f ) := ( f ( n i − 1 ) ) 1 ≤ i ≤ n θ i = ( n − i + 1 ) / n \theta_i=(n-i+1)/n θ i = ( n − i + 1 ) / n
Remark 3.2. We choose here to stick with the “canonical” choice of weights θ i ( n ) = f ( ( i − 1 ) / n ) \theta_i^{(n)}=f((i-1)/n) θ i ( n ) = f (( i − 1 ) / n ) f ( x i ( n ) ) f(x_i^{(n)}) f ( x i ( n ) ) ( x 1 ( n ) < … < x n ( n ) ) (x_1^{(n)}<\ldots<x_n^{(n)}) ( x 1 ( n ) < … < x n ( n ) )
The main goal of this section is to argue that the discrete and continuous Luce models display similar behaviors. In particular, we show in Theorem 3.13 that their LIS admit the same limit constant in the n \sqrt{n} n [18 ] ) to the LIS of (discrete) Luce permutations. As a warm-up, we start by showing that both models share the same growth rate.
Lemma 3.3. Let f f f [ 0 , 1 ) [0,1) [ 0 , 1 ) f ( 0 ) = 1 f(0)=1 f ( 0 ) = 1 μ f \mu_f μ f Theorem 1.4 . For each n ∈ N n\in\mathbb{N} n ∈ N σ n , μ f \sigma_{n,\mu_f} σ n , μ f μ f \mu_f μ f
E [ LIS ( σ n , μ f ) ] ≍ ψ f ( n ) , \mathbb{E}\left[\operatorname{LIS}(\sigma_{n,\mu_f})\right]\asymp\psi_f(n), E [ LIS ( σ n , μ f ) ] ≍ ψ f ( n ) , where n ↦ ψ f ( n ) n\mapsto\psi_f(n) n ↦ ψ f ( n )
Proof. Let U : = ( U 1 , … , U n ) \mathbf{U}:=(U_1,\ldots,U_n) U := ( U 1 , … , U n ) [ 0 , 1 ] [0,1] [ 0 , 1 ] U ( 1 ) < … < U ( n ) U_{(1)}<\ldots<U_{(n)} U ( 1 ) < … < U ( n ) τ n U \tau_n^{\mathrm{U}} τ n U f ( U ( i ) ) 1 ≤ i ≤ n f(U_{(i)})_{1\le i\le n} f ( U ( i ) ) 1 ≤ i ≤ n τ n U \tau_n^{\mathrm{U}} τ n U Sample n ( μ f ) \operatorname{Sample}_n(\mu_f) Sample n ( μ f )
We can apply Theorem 2.1 to τ n U \tau_n^{\mathrm{U}} τ n U U \mathbf{U} U
E [ E [ LIS ( τ n U ) ∣ U ] ] ≍ E [ ∑ k ∈ N 0 m k ( n ) ( U ) ] , \mathbb{E}\left[\mathbb{E}\left[\operatorname{LIS}(\tau_n^{\mathrm{U}})\mid\mathbf{U}\right]\right]\asymp\mathbb{E}\left[\sum_{k\in\mathbb{N}_0}\sqrt{m_k^{(n)}(\mathbf{U})}\right], E [ E [ LIS ( τ n U ) ∣ U ] ] ≍ E [ k ∈ N 0 ∑ m k ( n ) ( U ) ] , where
m k ( n ) ( U ) : = # { i ∈ [ n ] : k ≤ − log f ( U i ) < k + 1 } . m_k^{(n)}(\mathbf{U}):=\#\left\{i\in[n]: k\le-\log f(U_i)<k+1\right\}. m k ( n ) ( U ) := # { i ∈ [ n ] : k ≤ − log f ( U i ) < k + 1 } . With the notation of Proposition 2.4, we see that the unconditional law of m k ( n ) ( U ) m_k^{(n)}(\mathbf{U}) m k ( n ) ( U ) Bin ( n , p k ) \operatorname{Bin}(n,p_k) Bin ( n , p k )
Remark 3.4. If f f f LIS ( τ n ) \operatorname{LIS}(\tau_n) LIS ( τ n ) τ n \tau_n τ n ( θ ( n ) ( f ) ) (\theta^{(n)}(f)) ( θ ( n ) ( f ))
Example 3.5. Despite our philosophy here being that Luce random permutations τ n \tau_n τ n σ n , μ f \sigma_{n,\mu_f} σ n , μ f f : x ∈ [ 0 , 1 ] ↦ 1 − x f:x\in[0,1]\mapsto1-x f : x ∈ [ 0 , 1 ] ↦ 1 − x ( h n ) (h_n) ( h n ) ( w n ) (w_n) ( w n ) 1 ≤ h n ≤ n 1\le h_n\le n 1 ≤ h n ≤ n w n > 0 w_n>0 w n > 0
θ i ( n ) : = { w n h n − i + 1 if 1 ≤ i ≤ h n ; n − i + 1 n if h n < i ≤ n . \theta_i^{(n)}:=\begin{cases}
w_n^{h_n-i+1} & \text{if }1\le i\le h_n;\\
\dfrac{n-i+1}{n} & \text{if }h_n<i\le n.
\end{cases} θ i ( n ) := ⎩ ⎨ ⎧ w n h n − i + 1 n n − i + 1 if 1 ≤ i ≤ h n ; if h n < i ≤ n . If h n = o ( n ) h_n=o(n) h n = o ( n ) τ n \tau_n τ n ( θ i ( n ) ) (\theta_i^{(n)}) ( θ i ( n ) ) μ f \mu_f μ f LIS ( τ n ) \operatorname{LIS}(\tau_n) LIS ( τ n ) E 1 , … , E n E_1,\ldots,E_n E 1 , … , E n θ i ( n ) \theta_i^{(n)} θ i ( n ) i < h n i<h_n i < h n
P ( E i > E i + 1 ) = θ i + 1 ( n ) θ i ( n ) + θ i + 1 ( n ) = 1 w n + 1 , \mathbb{P}(E_i>E_{i+1})=\frac{\theta_{i+1}^{(n)}}{\theta_i^{(n)}+\theta_{i+1}^{(n)}}=\frac{1}{w_n+1}, P ( E i > E i + 1 ) = θ i ( n ) + θ i + 1 ( n ) θ i + 1 ( n ) = w n + 1 1 , and thus:
P ( E 1 < … < E h n ) ≥ 1 − h n − 1 w n + 1 . \mathbb{P}(E_1<\ldots<E_{h_n})\ge1-\frac{h_n-1}{w_n+1}. P ( E 1 < … < E h n ) ≥ 1 − w n + 1 h n − 1 . If we choose our sequences to satisfy h n = o ( w n ) h_n=o(w_n) h n = o ( w n ) 1 1 1 LIS ( τ n ) \operatorname{LIS}(\tau_n) LIS ( τ n ) h n h_n h n h n : = ⌊ n β ⌋ h_n:=\lfloor n^\beta\rfloor h n := ⌊ n β ⌋ β ∈ ( 1 / 2 , 1 ) \beta\in(1/2,1) β ∈ ( 1/2 , 1 ) w n : = n w_n:=n w n := n LIS ( τ n ) \operatorname{LIS}(\tau_n) LIS ( τ n ) ⌊ n β ⌋ \lfloor n^\beta\rfloor ⌊ n β ⌋ n \sqrt{n} n
To conclude this section, let us formulate an equivalent description of the comparison between the discrete model and the continuous model. Although we will not formally need it, we believe it helps better understand the current situation. Beforehand, we need to introduce some notation.
Let μ \mu μ ρ \rho ρ ρ ( x , ⋅ ) \rho(x,\cdot) ρ ( x , ⋅ ) x ∈ [ 0 , 1 ) x\in[0,1) x ∈ [ 0 , 1 ) ρ f ( x , ⋅ ) \rho_f(x,\cdot) ρ f ( x , ⋅ ) F ( E / f ( x ) ) F(E/f(x)) F ( E / f ( x )) 0 ≤ x 1 ≤ … ≤ x n < 1 0\le x_1\le\ldots\le x_n<1 0 ≤ x 1 ≤ … ≤ x n < 1 σ x 1 , … , x n , ρ \sigma_{x_1,\ldots,x_n,\rho} σ x 1 , … , x n , ρ Perm ( Y 1 , … , Y n ) \operatorname{Perm}(Y_1,\ldots,Y_n) Perm ( Y 1 , … , Y n ) ( Y i ) 1 ≤ i ≤ n (Y_i)_{1\le i\le n} ( Y i ) 1 ≤ i ≤ n Y i Y_i Y i ρ ( x i , ⋅ ) \rho(x_i,\cdot) ρ ( x i , ⋅ ) Sample x 1 , … , x n ( ρ ) \operatorname{Sample}_{x_1,\ldots,x_n}(\rho) Sample x 1 , … , x n ( ρ ) σ x 1 , … , x n , ρ \sigma_{x_1,\ldots,x_n,\rho} σ x 1 , … , x n , ρ Sample n ( μ ) \operatorname{Sample}_n(\mu) Sample n ( μ ) Sample U ( 1 ) , … , U ( n ) ( ρ ) \operatorname{Sample}_{U_{(1)},\ldots,U_{(n)}}(\rho) Sample U ( 1 ) , … , U ( n ) ( ρ ) U ( 1 ) < … < U ( n ) U_{(1)}<\ldots<U_{(n)} U ( 1 ) < … < U ( n )
Lemma 3.6. Let f f f [ 0 , 1 ) [0,1) [ 0 , 1 ) μ f \mu_f μ f ρ f \rho_f ρ f 0 ≤ x 1 ≤ … ≤ x n < 1 0\le x_1\le\ldots\le x_n<1 0 ≤ x 1 ≤ … ≤ x n < 1
Sample x 1 , … , x n ( ρ f ) = Luce ( f ( x 1 ) , … , f ( x n ) ) . \operatorname{Sample}_{x_1,\ldots,x_n}(\rho_f)=\operatorname{Luce}(f(x_1),\ldots,f(x_n)). Sample x 1 , … , x n ( ρ f ) = Luce ( f ( x 1 ) , … , f ( x n )) . Proof. Recall from Theorem 1.4 that ρ f ( x , ⋅ ) \rho_f(x,\cdot) ρ f ( x , ⋅ ) F ( E / f ( x ) ) F(E/f(x)) F ( E / f ( x )) E ∼ Exp ( 1 ) E\sim\operatorname{Exp}(1) E ∼ Exp ( 1 ) E / f ( x ) E/f(x) E / f ( x ) Exp ( f ( x ) ) \operatorname{Exp}(f(x)) Exp ( f ( x )) F F F Sample x 1 , … , x n ( ρ f ) \operatorname{Sample}_{x_1,\ldots,x_n}(\rho_f) Sample x 1 , … , x n ( ρ f ) Perm ( E 1 , … , E n ) \operatorname{Perm}(E_1,\ldots,E_n) Perm ( E 1 , … , E n ) E i ∼ Exp ( f ( x i ) ) E_i\sim\operatorname{Exp}(f(x_i)) E i ∼ Exp ( f ( x i ))
Let us briefly summarize our two comparison results. On the one hand, Lemma 3.1 states the continuous Luce model is like a discrete Luce model with random weights . On the other hand, Lemma 3.6 states that the discrete Luce model is like a continuous Luce model (i.e., a permuton sample) with specified x x x . Both points of view are particularly well-adapted to the use of coupling techniques, although we found it slightly easier to use the first one. This is illustrated in the next section.
Coupling the discrete and the continuous models
In view of Lemma 3.1, one should expect that the discrete model Luce ( θ ( n ) ( f ) ) \operatorname{Luce}(\theta^{(n)}(f)) Luce ( θ ( n ) ( f )) Sample n ( μ f ) \operatorname{Sample}_n(\mu_f) Sample n ( μ f )
Proposition 3.7. Let f f f C 1 C^1 C 1 [ 0 , 1 ] [0,1] [ 0 , 1 ] sup f ≤ 1 \sup f\le1 sup f ≤ 1 μ f \mu_f μ f ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) τ n ∼ Luce ( θ ( n ) ( f ) ) \tau_n\sim\operatorname{Luce}(\theta^{(n)}(f)) τ n ∼ Luce ( θ ( n ) ( f )) σ n , μ f ∼ Sample n ( μ f ) \sigma_{n,\mu_f}\sim\operatorname{Sample}_n(\mu_f) σ n , μ f ∼ Sample n ( μ f ) I u n m a t c h e d ⊆ [ ( 1 − ε ) n ] \mathcal{I}_{\mathrm{unmatched}}\subseteq[(1-\varepsilon)n] I unmatched ⊆ [( 1 − ε ) n ]
(i) Perm ( { τ n ( i ) : i ∈ [ ( 1 − ε ) n ] ∖ I u n m a t c h e d } ) = Perm ( { σ n , μ f ( i ) : i ∈ [ ( 1 − ε ) n ] ∖ I u n m a t c h e d } ) \operatorname{Perm}(\{\tau_n(i): i \in[(1-\varepsilon)n]\setminus\mathcal{I}_{\mathrm{unmatched}}\})=\operatorname{Perm}(\{\sigma_{n,\mu_f}(i): i \in[(1-\varepsilon)n]\setminus\mathcal{I}_{\mathrm{unmatched}}\}) Perm ({ τ n ( i ) : i ∈ [( 1 − ε ) n ] ∖ I unmatched }) = Perm ({ σ n , μ f ( i ) : i ∈ [( 1 − ε ) n ] ∖ I unmatched })
(ii) E [ # I u n m a t c h e d ] = O ( n ( log n ) 3 / 2 ) \mathbb{E}[\#\mathcal{I}_{\mathrm{unmatched}}]=O(\sqrt{n}(\log n)^{3/2}) E [ # I unmatched ] = O ( n ( log n ) 3/2 )
(iii) max { E [ LIS ( { τ n ( i ) : i ∈ I u n m a t c h e d } ) ] , E [ LIS ( { σ n , μ f ( i ) : i ∈ I u n m a t c h e d } ) ] } = O ( n 1 / 4 ( log n ) 3 / 4 ) \max\{\mathbb{E}[\operatorname{LIS}(\{\tau_n(i):i\in\mathcal{I}_{\mathrm{unmatched}}\})],\mathbb{E}[\operatorname{LIS}(\{\sigma_{n,\mu_f}(i):i\in\mathcal{I}_{\mathrm{unmatched}}\})]\}=O(n^{1/4}(\log n)^{3/4}) max { E [ LIS ({ τ n ( i ) : i ∈ I unmatched })] , E [ LIS ({ σ n , μ f ( i ) : i ∈ I unmatched })]} = O ( n 1/4 ( log n ) 3/4 )
Proof. For i ∈ [ n ] i\in[n] i ∈ [ n ] x i : = i − 1 n x_i:=\frac{i-1}{n} x i := n i − 1 ( E i ) 1 ≤ i ≤ n (E_i)_{1\leq i\leq n} ( E i ) 1 ≤ i ≤ n E i ∼ Exp ( f ( x i ) ) E_i\sim\operatorname{Exp}(f(x_i)) E i ∼ Exp ( f ( x i )) τ n : = Perm ( E 1 , … , E n ) \tau_n:=\operatorname{Perm}(E_1,\ldots,E_n) τ n := Perm ( E 1 , … , E n ) ( θ ( n ) ( f ) ) (\theta^{(n)}(f)) ( θ ( n ) ( f ))
Let U : = { U i : i ∈ [ n ] } \mathrm{U}:=\{U_i:i\in[n]\} U := { U i : i ∈ [ n ]} [ 0 , 1 ] [0,1] [ 0 , 1 ] U ( 1 ) < ⋯ < U ( n ) U_{(1)}<\cdots<U_{(n)} U ( 1 ) < ⋯ < U ( n ) U \mathrm{U} U ( T i ) 1 ≤ i ≤ n (T_i)_{1\leq i\leq n} ( T i ) 1 ≤ i ≤ n T i ∼ Exp ( f ( U ( i ) ) ) T_i\sim\operatorname{Exp}(f(U_{(i)})) T i ∼ Exp ( f ( U ( i ) )) σ n : = Perm ( T 1 , … , T n ) \sigma_n:=\operatorname{Perm}(T_1,\ldots,T_n) σ n := Perm ( T 1 , … , T n ) Sample n ( μ f ) \operatorname{Sample}_n(\mu_f) Sample n ( μ f ) U \mathrm{U} U ( T i ) 1 ≤ i ≤ n (T_i)_{1\leq i\leq n} ( T i ) 1 ≤ i ≤ n ( E i ) 1 ≤ i ≤ n (E_i)_{1\leq i\leq n} ( E i ) 1 ≤ i ≤ n
Set t n : = log n t_n:=\sqrt{\log n} t n := log n
P ( A n ) ≥ 1 − 2 e − 2 t n 2 = 1 − 2 n 2 where A n : = { sup 1 ≤ i ≤ n ∣ U ( i ) − x i ∣ ≤ t n n } . (14) \mathbb{P}(A_n)\geq1-2e^{-2t_n^2}=1-\frac{2}{n^2}
\quad\text{where}\quad
A_n:=\left\{\sup_{1\leq i\leq n}|U_{(i)}-x_i|\leq\frac{t_n}{\sqrt{n}}\right\}. \tag*{(14)} P ( A n ) ≥ 1 − 2 e − 2 t n 2 = 1 − n 2 2 where A n := { 1 ≤ i ≤ n sup ∣ U ( i ) − x i ∣ ≤ n t n } . (14) Observe that for n n n A n A_n A n i ∈ [ n ] i\in[n] i ∈ [ n ] x i ∈ [ 0 , 1 − ε ] x_i\in[0,1-\varepsilon] x i ∈ [ 0 , 1 − ε ] U ( i ) ∈ [ 0 , 1 − 1 2 ε ] U_{(i)}\in[0,1-\frac{1}{2}\varepsilon] U ( i ) ∈ [ 0 , 1 − 2 1 ε ]
Let
η : = min { 1 4 , min [ 0 , 1 − 1 2 ε ] f } > 0 and δ n : = t n n max { 1 , max [ 0 , 1 − 1 2 ε ] ∣ f ′ ∣ } = o ( 1 ) , \eta:=\min\left\{\frac{1}{4},\min_{[0,1-\frac{1}{2}\varepsilon]}f\right\}>0
\quad\text{and}\quad
\delta_n:=\frac{t_n}{\sqrt{n}}\max\left\{1,\max_{[0,1-\frac{1}{2}\varepsilon]}|f'|\right\}=o(1), η := min { 4 1 , [ 0 , 1 − 2 1 ε ] min f } > 0 and δ n := n t n max { 1 , [ 0 , 1 − 2 1 ε ] max ∣ f ′ ∣ } = o ( 1 ) , and write θ i : = f ( x i ) \theta_i:=f(x_i) θ i := f ( x i ) θ i ′ : = f ( U ( i ) ) \theta_i':=f(U_{(i)}) θ i ′ := f ( U ( i ) ) i ∈ [ n ] i\in[n] i ∈ [ n ] A n A_n A n i ∈ [ ( 1 − ε ) n ] i\in[(1-\varepsilon)n] i ∈ [( 1 − ε ) n ] θ i , θ i ′ ∈ [ η , 1 ] \theta_i,\theta_i'\in[\eta,1] θ i , θ i ′ ∈ [ η , 1 ] ∣ θ i − θ i ′ ∣ ≤ δ n |\theta_i-\theta_i'|\leq\delta_n ∣ θ i − θ i ′ ∣ ≤ δ n U \mathrm{U} U A n A_n A n i ∈ [ ( 1 − ε ) n ] i\in[(1-\varepsilon)n] i ∈ [( 1 − ε ) n ] ( E i ) 1 ≤ i ≤ n (E_i)_{1\leq i\leq n} ( E i ) 1 ≤ i ≤ n ( T i ) 1 ≤ i ≤ n (T_i)_{1\leq i\leq n} ( T i ) 1 ≤ i ≤ n i ∈ [ ( 1 − ε ) n ] i\in[(1-\varepsilon)n] i ∈ [( 1 − ε ) n ]
P ( E i ≠ T i ) ≤ 2 δ n η ( 1 + log 1 2 δ n ) = : q n \mathbb{P}(E_i\ne T_i)\leq\frac{2\delta_n}{\eta}(1+\log\frac{1}{2\delta_n})=:q_n P ( E i = T i ) ≤ η 2 δ n ( 1 + log 2 δ n 1 ) =: q n
the law of E i E_i E i { E i ≠ T i } \{E_i\ne T_i\} { E i = T i } R g n Rg_n R g n R ∈ ( 0 , ∞ ) R\in(0,\infty) R ∈ ( 0 , ∞ ) g n g_n g n [ 0 , ∞ ) [0,\infty) [ 0 , ∞ ) n n n ε \varepsilon ε f f f
The random variables E i E_i E i T i T_i T i i > ( 1 − ε ) n i>(1-\varepsilon)n i > ( 1 − ε ) n ¬ A n \neg A_n ¬ A n ( E i ) 1 ≤ i ≤ n (E_i)_{1\leq i\leq n} ( E i ) 1 ≤ i ≤ n ( T i ) 1 ≤ i ≤ n (T_i)_{1\leq i\leq n} ( T i ) 1 ≤ i ≤ n
We set I u n m a t c h e d : = { i ∈ [ ( 1 − ε ) n ] : E i ≠ T i } \mathcal{I}_{\mathrm{unmatched}}:=\{i\in[(1-\varepsilon)n]:E_i\ne T_i\} I unmatched := { i ∈ [( 1 − ε ) n ] : E i = T i } A n A_n A n I u n m a t c h e d \mathcal{I}_{\mathrm{unmatched}} I unmatched Bin ( n , q n ) \operatorname{Bin}(n,q_n) Bin ( n , q n ) ¬ A n \neg A_n ¬ A n n n n
E [ # I u n m a t c h e d ] ≤ n q n + 2 n − 1 = O ( n ( log n ) 3 / 2 ) . \mathbb{E}[\#\mathcal{I}_{\mathrm{unmatched}}]\leq nq_n+2n^{-1}=O(\sqrt{n}(\log n)^{3/2}). E [ # I unmatched ] ≤ n q n + 2 n − 1 = O ( n ( log n ) 3/2 ) . This proves the second item. Finally, we can apply Lemma 2.15 to the sequence ( E i , i ∈ I u n m a t c h e d ) (E_i,i\in\mathcal{I}_{\mathrm{unmatched}}) ( E i , i ∈ I unmatched )
E [ E [ LIS ( E i : i ∈ I u n m a t c h e d ) ∣ U , A n , I u n m a t c h e d ] ] ≤ E [ 2 e R # I u n m a t c h e d ] ≤ O ( n 1 / 4 ( log n ) 3 / 4 ) , \mathbb{E}[\mathbb{E}[\operatorname{LIS}(E_i:i\in\mathcal{I}_{\mathrm{unmatched}})\mid\mathrm{U},A_n,\mathcal{I}_{\mathrm{unmatched}}]]
\leq\mathbb{E}[2e\sqrt{R\#\mathcal{I}_{\mathrm{unmatched}}}]
\leq O(n^{1/4}(\log n)^{3/4}), E [ E [ LIS ( E i : i ∈ I unmatched ) ∣ U , A n , I unmatched ]] ≤ E [ 2 e R # I unmatched ] ≤ O ( n 1/4 ( log n ) 3/4 ) , where we used Jensen’s inequality. It suffices to bound the LIS by n n n ¬ A n \neg A_n ¬ A n τ n \tau_n τ n σ n \sigma_n σ n
Retrieving the limit constant from the continuous model
This section is devoted to our second main result, Theorem 3.13. We start with a few preliminary results that will ease its proof.
Lemma 3.8. Let ( θ i ) 1 ≤ i ≤ n (\theta_i)_{1\leq i\leq n} ( θ i ) 1 ≤ i ≤ n τ n \tau_n τ n θ 1 , … , θ n \theta_1,\ldots,\theta_n θ 1 , … , θ n k ∈ [ n ] k\in[n] k ∈ [ n ] 1 ≤ i 1 < ⋯ < i k ≤ n 1\leq i_1<\cdots<i_k\leq n 1 ≤ i 1 < ⋯ < i k ≤ n Perm ( τ n ( i 1 ) , … , τ n ( i k ) ) \operatorname{Perm}(\tau_n(i_1),\ldots,\tau_n(i_k)) Perm ( τ n ( i 1 ) , … , τ n ( i k )) θ i 1 , … , θ i k \theta_{i_1},\ldots,\theta_{i_k} θ i 1 , … , θ i k
Proof. This is immediate by Lemma 1.3.
Lemma 3.9. Fix A > 0 A>0 A > 0 m ∈ N m\in\mathbb{N} m ∈ N b > a > 0 b>a>0 b > a > 0 θ 1 , … , θ m ∈ [ a , b ] \theta_1,\ldots,\theta_m\in[a,b] θ 1 , … , θ m ∈ [ a , b ] ( E i ) 1 ≤ i ≤ m (E_i)_{1\le i\le m} ( E i ) 1 ≤ i ≤ m ( θ i ) 1 ≤ i ≤ m (\theta_i)_{1\le i\le m} ( θ i ) 1 ≤ i ≤ m A A A
P ( LIS ( E 1 , … , E m ) ≥ 2 e b a m ) ≤ 1 2 m \mathbb{P}\left(\operatorname{LIS}(E_1,\ldots,E_m)\ge2e\sqrt{\frac{b}{a}}\sqrt{m}\right)\le\frac{1}{2\sqrt{m}} P ( LIS ( E 1 , … , E m ) ≥ 2 e a b m ) ≤ 2 m 1 and
E [ LIS ( E 1 , … , E m ) ] ≤ 2 e b a m . \mathbb{E}\left[\operatorname{LIS}(E_1,\ldots,E_m)\right]\le2e\sqrt{\frac{b}{a}}\sqrt{m}. E [ LIS ( E 1 , … , E m ) ] ≤ 2 e a b m . Proof. This is immediate from Lemma 2.15, and the observation that ( E i ) 1 ≤ i ≤ m (E_i)_{1\le i\le m} ( E i ) 1 ≤ i ≤ m ( A + T i ) 1 ≤ i ≤ m (A+T_i)_{1\le i\le m} ( A + T i ) 1 ≤ i ≤ m ( T i ) 1 ≤ i ≤ m (T_i)_{1\le i\le m} ( T i ) 1 ≤ i ≤ m ( θ i ) 1 ≤ i ≤ m (\theta_i)_{1\le i\le m} ( θ i ) 1 ≤ i ≤ m
Corollary 3.10. Let f f f [ 0 , 1 ) [0,1) [ 0 , 1 ) μ f \mu_f μ f Theorem 1.4 . For each n ∈ N n\in\mathbb{N} n ∈ N σ n \sigma_n σ n μ f \mu_f μ f 0 < α , β < 1 0<\alpha,\beta<1 0 < α , β < 1
lim sup n → ∞ 1 n LIS ( { σ n ( i ) : i ≤ α n , σ n ( i ) ≥ β n } ) ≤ η α , β , (15) \limsup_{n\to\infty}\frac{1}{\sqrt{n}}\operatorname{LIS}(\{\sigma_n(i):i\le\alpha n,\sigma_n(i)\ge\beta n\})\le\eta_{\alpha,\beta}, \tag*{(15)} n → ∞ lim sup n 1 LIS ({ σ n ( i ) : i ≤ α n , σ n ( i ) ≥ β n }) ≤ η α , β , (15) in probability and in expectation, where ( η α , β ) 0 < α , β < 1 (\eta_{\alpha,\beta})_{0<\alpha,\beta<1} ( η α , β ) 0 < α , β < 1 α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 )
η α , β ⟶ 0 as β → 1. \eta_{\alpha,\beta}\longrightarrow0\quad\text{as }\beta\to1. η α , β ⟶ 0 as β → 1. Proof. Let ( U i ) 1 ≤ i ≤ n (U_i)_{1\le i\le n} ( U i ) 1 ≤ i ≤ n U 1 < ⋯ < U n U_1<\cdots<U_n U 1 < ⋯ < U n ( E i ) 1 ≤ i ≤ n (E_i)_{1\le i\le n} ( E i ) 1 ≤ i ≤ n i ∈ [ n ] i\in[n] i ∈ [ n ] V i : = F − 1 ( E i / f ( U i ) ) V_i:=F^{-1}(E_i/f(U_i)) V i := F − 1 ( E i / f ( U i )) Theorem 1.4 . By that same theorem, P : = { ( U i , V i ) : i ∈ [ n ] } \mathcal{P}:=\{(U_i,V_i):i\in[n]\} P := {( U i , V i ) : i ∈ [ n ]} μ f \mu_f μ f σ n : = Perm ( P ) = Perm ( V 1 , … , V n ) \sigma_n:=\operatorname{Perm}(\mathcal{P})=\operatorname{Perm}(V_1,\ldots,V_n) σ n := Perm ( P ) = Perm ( V 1 , … , V n ) μ f \mu_f μ f 0 < α , β < 1 0<\alpha,\beta<1 0 < α , β < 1
I α : = max { i ∈ [ n ] : U i ≤ α } and J β : = max { σ n ( i ) : i ∈ [ n ] , V i < β } . I_\alpha:=\max\{i\in[n]:U_i\le\alpha\}\qquad\text{and}\qquad J_\beta:=\max\{\sigma_n(i):i\in[n],V_i<\beta\}. I α := max { i ∈ [ n ] : U i ≤ α } and J β := max { σ n ( i ) : i ∈ [ n ] , V i < β } . Since μ f \mu_f μ f { U i : i ∈ [ n ] } \{U_i:i\in[n]\} { U i : i ∈ [ n ]} { V i : i ∈ [ n ] } \{V_i:i\in[n]\} { V i : i ∈ [ n ]} [ 0 , 1 ] [0,1] [ 0 , 1 ]
1 n I α ⟶ α and 1 n J β ⟶ β , (16) \frac{1}{n}I_\alpha\longrightarrow\alpha\qquad\text{and}\qquad\frac{1}{n}J_\beta\longrightarrow\beta, \tag*{(16)} n 1 I α ⟶ α and n 1 J β ⟶ β , (16) almost surely. Let us write here
σ n ⟨ I α , J β ⟩ : = Perm ( σ n ( i ) : i ≤ I α , σ n ( i ) > J β ) , \sigma_n^{\langle I_\alpha,J_\beta\rangle}:=\operatorname{Perm}(\sigma_n(i):i\le I_\alpha,\sigma_n(i)>J_\beta), σ n ⟨ I α , J β ⟩ := Perm ( σ n ( i ) : i ≤ I α , σ n ( i ) > J β ) , and note that it coincides with
σ n ⟨ I α , J β ⟩ = Perm ( { ( U i , V i ) : i ∈ [ n ] , U i ≤ α , V i ≥ β } ) = Perm ( P ∩ B α , β ) , \sigma_n^{\langle I_\alpha,J_\beta\rangle}
=\operatorname{Perm}(\{(U_i,V_i):i\in[n],U_i\le\alpha,V_i\ge\beta\})
=\operatorname{Perm}(\mathcal{P}\cap B_{\alpha,\beta}), σ n ⟨ I α , J β ⟩ = Perm ({( U i , V i ) : i ∈ [ n ] , U i ≤ α , V i ≥ β }) = Perm ( P ∩ B α , β ) , with the notation of § 1.5 and B α , β : = [ 0 , α ] × [ β , 1 ] B_{\alpha,\beta}:=[0,\alpha]\times[\beta,1] B α , β := [ 0 , α ] × [ β , 1 ] σ n ⟨ I α , J β ⟩ \sigma_n^{\langle I_\alpha,J_\beta\rangle} σ n ⟨ I α , J β ⟩ μ f \mu_f μ f P \mathcal{P} P σ n \sigma_n σ n B α , β B_{\alpha,\beta} B α , β σ n ⟨ I α , J β ⟩ \sigma_n^{\langle I_\alpha,J_\beta\rangle} σ n ⟨ I α , J β ⟩ N α , β N_{\alpha,\beta} N α , β n n n μ f ( B α , β ) \mu_f(B_{\alpha,\beta}) μ f ( B α , β )
I : = { i ∈ [ n ] : ( U i , V i ) ∈ B α , β } , \mathcal{I}:=\{i\in[n]:(U_i,V_i)\in B_{\alpha,\beta}\}, I := { i ∈ [ n ] : ( U i , V i ) ∈ B α , β } , and the sequence U : = ( U i ) 1 ≤ i ≤ n \mathbf{U}:=(U_i)_{1\le i\le n} U := ( U i ) 1 ≤ i ≤ n ( F − 1 ( V i ) ) i ∈ I (F^{-1}(V_i))_{i\in\mathcal{I}} ( F − 1 ( V i ) ) i ∈ I ( f ( U i ) ) i ∈ I (f(U_i))_{i\in\mathcal{I}} ( f ( U i ) ) i ∈ I F − 1 ( β ) F^{-1}(\beta) F − 1 ( β )
P ( LIS ( { V i : i ∈ I } ) ≥ 2 e λ α N α , β ∣ U , I ) ≤ 1 2 N α , β \mathbb{P}\left(\operatorname{LIS}(\{V_i:i\in\mathcal{I}\})\ge2e\sqrt{\lambda_\alpha N_{\alpha,\beta}}\mathrel{\big|}\mathbf{U},\mathcal{I}\right)\le\frac{1}{2\sqrt{N_{\alpha,\beta}}} P ( LIS ({ V i : i ∈ I }) ≥ 2 e λ α N α , β U , I ) ≤ 2 N α , β 1 and
E [ LIS ( { V i : i ∈ I } ) ∣ U , I ] ≤ 2 e λ α N α , β , \mathbb{E}\left[\operatorname{LIS}(\{V_i:i\in\mathcal{I}\})\mathrel{\big|}\mathbf{U},\mathcal{I}\right]\le2e\sqrt{\lambda_\alpha N_{\alpha,\beta}}, E [ LIS ({ V i : i ∈ I }) U , I ] ≤ 2 e λ α N α , β , where λ α : = max [ 0 , α ] f min [ 0 , α ] f ∈ ( 0 , ∞ ) \lambda_\alpha:=\frac{\max_{[0,\alpha]}f}{\min_{[0,\alpha]}f}\in(0,\infty) λ α := m i n [ 0 , α ] f m a x [ 0 , α ] f ∈ ( 0 , ∞ ) 1 n N α , β ⟶ μ f ( B α , β ) > 0 \frac{1}{n}N_{\alpha,\beta}\longrightarrow\mu_f(B_{\alpha,\beta})>0 n 1 N α , β ⟶ μ f ( B α , β ) > 0 n → ∞ n\to\infty n → ∞ 0 < α , β < 1 0<\alpha,\beta<1 0 < α , β < 1
E [ LIS ( { V i : i ∈ I } ) ] ≤ 2 e λ α μ f ( B α , β ) n . \mathbb{E}\left[\operatorname{LIS}(\{V_i:i\in\mathcal{I}\})\right]\le2e\sqrt{\lambda_\alpha\mu_f(B_{\alpha,\beta})n}. E [ LIS ({ V i : i ∈ I }) ] ≤ 2 e λ α μ f ( B α , β ) n . Setting η α , β : = 2 e λ α μ f ( B α , β ) \eta_{\alpha,\beta}:=2e\sqrt{\lambda_\alpha\mu_f(B_{\alpha,\beta})} η α , β := 2 e λ α μ f ( B α , β )
Figure 4. Illustration of the main arguments in the proof of Theorem 3.13 . The permuton sample σ n , μ f \sigma_{n,\mu_f} σ n , μ f μ f \mu_f μ f [ 0 , 1 ] 2 [0,1]^2 [ 0 , 1 ] 2 Proposition 3.12 identifies the limit constant for the LIS of points in [ 0 , α ] × [ 0 , β ] [0,\alpha]\times[0,\beta] [ 0 , α ] × [ 0 , β ] α , β ∈ ( 0 , 1 ) \alpha,\beta\in(0,1) α , β ∈ ( 0 , 1 ) Corollary 3.10 bounds the LIS of points in [ 0 , α ] × [ β , 1 ] [0,\alpha]\times[\beta,1] [ 0 , α ] × [ β , 1 ] β = β ( α ) → 1 \beta=\beta(\alpha)\to1 β = β ( α ) → 1 Theorem 3.13 , we bound the LIS of points in [ α , 1 ] × [ 0 , 1 ] [\alpha,1]\times[0,1] [ α , 1 ] × [ 0 , 1 ] α → 1 \alpha\to1 α → 1 Proposition 3.7 shows that τ n \tau_n τ n σ n , μ f \sigma_{n,\mu_f} σ n , μ f [ 0 , α ] × [ 0 , 1 ] [0,\alpha]\times[0,1] [ 0 , α ] × [ 0 , 1 ] α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 )
Proposition 3.12. Let μ \mu μ ρ \rho ρ C 1 C^1 C 1 [ 0 , α ] 2 [0,\alpha]^2 [ 0 , α ] 2 α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) n ∈ N n \in\mathbb{N} n ∈ N σ n \sigma_n σ n μ \mu μ α , β ∈ ( 0 , 1 ] \alpha,\beta\in(0,1] α , β ∈ ( 0 , 1 ]
σ n ( α , β ) : = Perm ( { σ n ( i ) : i ≤ α n , σ n ( i ) ≤ β n } ) . \sigma_n^{(\alpha,\beta)} := \operatorname{Perm}(\{\sigma_n(i): i \le\alpha n,\sigma_n(i) \le\beta n\}). σ n ( α , β ) := Perm ({ σ n ( i ) : i ≤ α n , σ n ( i ) ≤ β n }) . Then, there exists a family of finite constants ( K α , β ) 0 < α , β < 1 (K_{\alpha,\beta})_{0<\alpha,\beta<1} ( K α , β ) 0 < α , β < 1 0 < α , β < 1 0 < \alpha,\beta< 1 0 < α , β < 1
lim n → ∞ 1 n LIS ( σ n ( α , β ) ) = 2 K α , β , \lim_{n\to\infty} \frac{1}{\sqrt{n}}\operatorname{LIS}\left(\sigma_n^{(\alpha,\beta)}\right) = 2K_{\alpha,\beta}, n → ∞ lim n 1 LIS ( σ n ( α , β ) ) = 2 K α , β , in probability and in expectation, and
K α , β → ( α , β ) → ( 1 , 1 ) K : = sup ϕ ↗ ∫ 0 1 ϕ ′ ( t ) ρ ( t , ϕ ( t ) ) d t , K_{\alpha,\beta} \xrightarrow[(\alpha,\beta)\to(1,1)]{} K := \sup_{\phi\nearrow} \int_0^1 \sqrt{\phi'(t)\rho(t,\phi(t))}\,\mathrm{d}t, K α , β ( α , β ) → ( 1 , 1 ) K := ϕ ↗ sup ∫ 0 1 ϕ ′ ( t ) ρ ( t , ϕ ( t )) d t , where the supremum ranges over all non-decreasing, right-continuous curves ϕ : [ 0 , 1 ) → [ 0 , 1 ) \phi: [0,1) \to[0,1) ϕ : [ 0 , 1 ) → [ 0 , 1 )
Proof. Let α , β ∈ ( 0 , 1 ) \alpha,\beta\in(0,1) α , β ∈ ( 0 , 1 ) R α , β : = [ 0 , α ] × [ 0 , β ] R_{\alpha,\beta} := [0,\alpha] \times[0,\beta] R α , β := [ 0 , α ] × [ 0 , β ] ρ α , β \rho_{\alpha,\beta} ρ α , β ρ \rho ρ R α , β R_{\alpha,\beta} R α , β
ρ α , β = 1 μ ( R α , β ) ρ 1 R α , β . \rho_{\alpha,\beta} = \frac{1}{\mu(R_{\alpha,\beta})}\rho\mathbf{1}_{R_{\alpha,\beta}}. ρ α , β = μ ( R α , β ) 1 ρ 1 R α , β . Write σ n = Perm ( P ) \sigma_n = \operatorname{Perm}(\mathcal{P}) σ n = Perm ( P ) P \mathcal{P} P μ \mu μ n n n [ 0 , 1 ] 2 [0,1]^2 [ 0 , 1 ] 2 σ ~ n ( α , β ) : = Perm ( P ∩ R α , β ) \widetilde{\sigma}_n^{(\alpha,\beta)} := \operatorname{Perm}(\mathcal{P} \cap R_{\alpha,\beta}) σ n ( α , β ) := Perm ( P ∩ R α , β ) R α , β R_{\alpha,\beta} R α , β σ ~ n ( α , β ) \widetilde{\sigma}_n^{(\alpha,\beta)} σ n ( α , β ) σ n ( α , β ) \sigma_n^{(\alpha,\beta)} σ n ( α , β ) σ ~ n ( α , β ) = σ n ( I α / n , J β / n ) \widetilde{\sigma}_n^{(\alpha,\beta)} = \sigma_n^{(I_{\alpha}/n,J_{\beta}/n)} σ n ( α , β ) = σ n ( I α / n , J β / n ) I α , J β I_\alpha,J_\beta I α , J β α n , β n \alpha n,\beta n α n , β n σ ~ n ( α , β ) \widetilde{\sigma}_n^{(\alpha,\beta)} σ n ( α , β ) σ ~ n ( α , β ) \widetilde{\sigma}_n^{(\alpha,\beta)} σ n ( α , β ) N α , β ∼ Bin ( n , μ ( R α , β ) ) N_{\alpha,\beta} \sim\operatorname{Bin}(n,\mu(R_{\alpha,\beta})) N α , β ∼ Bin ( n , μ ( R α , β )) N α , β N_{\alpha,\beta} N α , β Perm ( P ~ ) \operatorname{Perm}(\widetilde{\mathcal{P}}) Perm ( P ) P ~ \widetilde{\mathcal{P}} P N α , β N_{\alpha,\beta} N α , β R α , β R_{\alpha,\beta} R α , β ρ α , β \rho_{\alpha,\beta} ρ α , β ρ ~ α , β \widetilde{\rho}_{\alpha,\beta} ρ α , β [ 0 , 1 ] 2 [0,1]^2 [ 0 , 1 ] 2 ρ α , β \rho_{\alpha,\beta} ρ α , β
for all ( x , y ) ∈ [ 0 , 1 ] 2 , ρ ~ α , β ( x , y ) : = α β ρ α , β ( α x , β y ) = α β μ ( R α , β ) ρ ( α x , β y ) . \text{for all }(x,y)\in[0,1]^2,\qquad\widetilde{\rho}_{\alpha,\beta}(x,y):=\alpha\beta\rho_{\alpha,\beta}(\alpha x,\beta y)=\frac{\alpha\beta}{\mu(R_{\alpha,\beta})}\rho(\alpha x,\beta y). for all ( x , y ) ∈ [ 0 , 1 ] 2 , ρ α , β ( x , y ) := α β ρ α , β ( α x , β y ) = μ ( R α , β ) α β ρ ( α x , β y ) . Note that the Perm map is invariant under linear transformations. Therefore, conditionally given N α , β N_{\alpha,\beta} N α , β σ ~ n ( α , β ) \widetilde{\sigma}_n^{(\alpha,\beta)} σ n ( α , β ) 2 Perm ( P ~ ) \operatorname{Perm}(\widetilde{\mathcal{P}}) Perm ( P ) P ~ \widetilde{\mathcal{P}} P N α , β N_{\alpha,\beta} N α , β [ 0 , 1 ] 2 [0,1]^2 [ 0 , 1 ] 2 ρ ~ α , β \widetilde{\rho}_{\alpha,\beta} ρ α , β ρ ~ α , β \widetilde{\rho}_{\alpha,\beta} ρ α , β C 1 C^1 C 1 [ 0 , 1 ] 2 [0,1]^2 [ 0 , 1 ] 2 [18 Theorem 2] :
1 N α , β LIS ( σ ~ n ( α , β ) ) → n → ∞ P 2 sup ϕ ↗ ∫ 0 1 ϕ ′ ( t ) ρ ~ α , β ( t , ϕ ( t ) ) d t \frac{1}{\sqrt{N_{\alpha,\beta}}}\operatorname{LIS}\left(\widetilde{\sigma}_n^{(\alpha,\beta)}\right) \xrightarrow[n\to\infty]{\mathbb{P}} 2\sup_{\phi\nearrow}\int_0^1\sqrt{\phi'(t)\widetilde{\rho}_{\alpha,\beta}(t,\phi(t))}\,\mathrm{d}t N α , β 1 LIS ( σ n ( α , β ) ) P n → ∞ 2 ϕ ↗ sup ∫ 0 1 ϕ ′ ( t ) ρ α , β ( t , ϕ ( t )) d t in probability and in expectation, and further:
1 n LIS ( σ ~ n ( α , β ) ) → n → ∞ 2 μ ( R α , β ) sup ϕ ↗ ∫ 0 1 ϕ ′ ( t ) ρ ~ α , β ( t , ϕ ( t ) ) d t = : 2 K α , β \frac{1}{\sqrt{n}}\operatorname{LIS}\left(\widetilde{\sigma}_n^{(\alpha,\beta)}\right) \xrightarrow[n\to\infty]{} 2\sqrt{\mu(R_{\alpha,\beta})}\sup_{\phi\nearrow}\int_0^1\sqrt{\phi'(t)\widetilde{\rho}_{\alpha,\beta}(t,\phi(t))}\,\mathrm{d}t =: 2K_{\alpha,\beta} n 1 LIS ( σ n ( α , β ) ) n → ∞ 2 μ ( R α , β ) ϕ ↗ sup ∫ 0 1 ϕ ′ ( t ) ρ α , β ( t , ϕ ( t )) d t =: 2 K α , β in probability and in expectation. It remains only to show that K α , β → K K_{\alpha,\beta} \to K K α , β → K ( α , β ) → ( 1 , 1 ) (\alpha,\beta) \to(1,1) ( α , β ) → ( 1 , 1 ) μ ( R α , β ) → μ ( [ 0 , 1 ] 2 ) = 1 \mu(R_{\alpha,\beta}) \to\mu([0,1]^2) = 1 μ ( R α , β ) → μ ([ 0 , 1 ] 2 ) = 1 ( α , β ) → ( 1 , 1 ) (\alpha,\beta) \to(1,1) ( α , β ) → ( 1 , 1 ) μ \mu μ α , β ∈ ( 0 , 1 ] \alpha,\beta\in(0,1] α , β ∈ ( 0 , 1 ] C ↗ ( α , β ) C^{\nearrow}(\alpha,\beta) C ↗ ( α , β ) ϕ : [ 0 , α ) → [ 0 , β ) \phi: [0,\alpha) \to[0,\beta) ϕ : [ 0 , α ) → [ 0 , β )
sup ϕ ∈ C ↗ ( 1 , 1 ) ∫ 0 1 ϕ ′ ( t ) ρ ~ α , β ( t , ϕ ( t ) ) d t = 1 μ ( R α , β ) sup ϕ ∈ C ↗ ( α , β ) ∫ 0 α ϕ ′ ( t ) ρ ( t , ϕ ( t ) ) d t . \sup_{\phi\in C^{\nearrow}(1,1)} \int_0^1 \sqrt{\phi'(t)\widetilde{\rho}_{\alpha,\beta}(t,\phi(t))}\,\mathrm{d}t
=
\frac{1}{\sqrt{\mu(R_{\alpha,\beta})}}
\sup_{\phi\in C^{\nearrow}(\alpha,\beta)} \int_0^\alpha\sqrt{\phi'(t)\rho(t,\phi(t))}\,\mathrm{d}t . ϕ ∈ C ↗ ( 1 , 1 ) sup ∫ 0 1 ϕ ′ ( t ) ρ α , β ( t , ϕ ( t )) d t = μ ( R α , β ) 1 ϕ ∈ C ↗ ( α , β ) sup ∫ 0 α ϕ ′ ( t ) ρ ( t , ϕ ( t )) d t . and thus, it remains to show that
sup ϕ ∈ C ↗ ( α , β ) ∫ 0 α ϕ ′ ( t ) ρ ( t , ϕ ( t ) ) d t → ( α , β ) → ( 1 , 1 ) sup ϕ ∈ C ↗ ( 1 , 1 ) ∫ 0 1 ϕ ′ ( t ) ρ ( t , ϕ ( t ) ) d t . (17) \sup_{\phi\in C^{\nearrow}(\alpha,\beta)} \int_0^\alpha\sqrt{\phi'(t)\rho(t,\phi(t))}\,\mathrm{d}t
\xrightarrow[(\alpha,\beta)\to(1,1)]{}
\sup_{\phi\in C^{\nearrow}(1,1)} \int_0^1 \sqrt{\phi'(t)\rho(t,\phi(t))}\,\mathrm{d}t . \tag*{(17)} ϕ ∈ C ↗ ( α , β ) sup ∫ 0 α ϕ ′ ( t ) ρ ( t , ϕ ( t )) d t ( α , β ) → ( 1 , 1 ) ϕ ∈ C ↗ ( 1 , 1 ) sup ∫ 0 1 ϕ ′ ( t ) ρ ( t , ϕ ( t )) d t . (17) It is clear that the left-hand side is less than or equal to the right-hand side. Conversely, consider ϕ ∈ C ↗ ( 1 , 1 ) \phi\in C^{\nearrow}(1,1) ϕ ∈ C ↗ ( 1 , 1 )
t α , β : = sup { t ∈ [ 0 , α ) : ϕ ( t ) < β 2 } . t_{\alpha,\beta}:=\sup\{t\in[0,\alpha):\phi(t)<\beta^2\}. t α , β := sup { t ∈ [ 0 , α ) : ϕ ( t ) < β 2 } . Since t α , β → 1 t_{\alpha,\beta}\to1 t α , β → 1 ( α , β ) → 1 (\alpha,\beta)\to1 ( α , β ) → 1
∫ 0 t α , β ϕ ′ ( t ) ρ ( t , ϕ ( t ) ) d t → ( α , β ) → ( 1 , 1 ) ∫ 0 1 ϕ ′ ( t ) ρ ( t , ϕ ( t ) ) d t . \int_0^{t_{\alpha,\beta}} \sqrt{\phi'(t)\rho(t,\phi(t))}\,\mathrm{d}t
\xrightarrow[(\alpha,\beta)\to(1,1)]{}
\int_0^1 \sqrt{\phi'(t)\rho(t,\phi(t))}\,\mathrm{d}t . ∫ 0 t α , β ϕ ′ ( t ) ρ ( t , ϕ ( t )) d t ( α , β ) → ( 1 , 1 ) ∫ 0 1 ϕ ′ ( t ) ρ ( t , ϕ ( t )) d t . Moreover, the restriction of ϕ \phi ϕ [ 0 , t α , β ) [0,t_{\alpha,\beta}) [ 0 , t α , β ) ϕ α , β \phi_{\alpha,\beta} ϕ α , β C ↗ ( α , β ) C^{\nearrow}(\alpha,\beta) C ↗ ( α , β )
ϕ α , β : = ϕ 1 [ 0 , t α , β ) + β 2 1 [ t α , β , α ) , \phi_{\alpha,\beta}:=\phi\mathbb{1}_{[0,t_{\alpha,\beta})}+\beta^2\mathbb{1}_{[t_{\alpha,\beta},\alpha)} , ϕ α , β := ϕ 1 [ 0 , t α , β ) + β 2 1 [ t α , β , α ) , for which it holds that
∫ 0 t α , β ϕ ′ ( t ) ρ ( t , ϕ ( t ) ) d t = ∫ 0 α ϕ α , β ′ ( t ) ρ ( t , ϕ α , β ( t ) ) d t . \int_0^{t_{\alpha,\beta}} \sqrt{\phi'(t)\rho(t,\phi(t))}\,\mathrm{d}t
=
\int_0^\alpha\sqrt{\phi'_{\alpha,\beta}(t)\rho(t,\phi_{\alpha,\beta}(t))}\,\mathrm{d}t . ∫ 0 t α , β ϕ ′ ( t ) ρ ( t , ϕ ( t )) d t = ∫ 0 α ϕ α , β ′ ( t ) ρ ( t , ϕ α , β ( t )) d t . From there, it is straightforward to deduce that
lim inf ( α , β ) → ( 1 , 1 ) sup ϕ ∈ C ↗ ( α , β ) ∫ 0 α ϕ ′ ( t ) ρ ( t , ϕ ( t ) ) d t ≥ sup ϕ ∈ C ↗ ( 1 , 1 ) ∫ 0 1 ϕ ′ ( t ) ρ ( t , ϕ ( t ) ) d t . \liminf_{(\alpha,\beta)\to(1,1)}
\sup_{\phi\in C^{\nearrow}(\alpha,\beta)}
\int_0^\alpha\sqrt{\phi'(t)\rho(t,\phi(t))}\,\mathrm{d}t
\ge
\sup_{\phi\in C^{\nearrow}(1,1)}
\int_0^1 \sqrt{\phi'(t)\rho(t,\phi(t))}\,\mathrm{d}t . ( α , β ) → ( 1 , 1 ) lim inf ϕ ∈ C ↗ ( α , β ) sup ∫ 0 α ϕ ′ ( t ) ρ ( t , ϕ ( t )) d t ≥ ϕ ∈ C ↗ ( 1 , 1 ) sup ∫ 0 1 ϕ ′ ( t ) ρ ( t , ϕ ( t )) d t . thus showing (17), and concluding this proof.
Now, we can properly state and prove our main result. Some of the main arguments are illustrated in Figure 4 .
Theorem 3.13. Let f f f C 1 C^1 C 1 [ 0 , 1 ) [0,1) [ 0 , 1 ) μ f \mu_f μ f ρ f \rho_f ρ f n ∈ N n\in\mathbb{N} n ∈ N θ ( n ) ( f ) : = ( f ( i − 1 n ) ) 1 ≤ i ≤ n \theta^{(n)}(f):=\left(f\left(\frac{i-1}{n}\right)\right)_{1\le i\le n} θ ( n ) ( f ) := ( f ( n i − 1 ) ) 1 ≤ i ≤ n τ n \tau_n τ n ( θ ( n ) ( f ) ) (\theta^{(n)}(f)) ( θ ( n ) ( f )) σ n , μ f \sigma_{n,\mu_f} σ n , μ f μ f \mu_f μ f − log f -\log f − log f E [ LIS ( τ n ) ] ≍ n \mathbb{E}[\operatorname{LIS}(\tau_n)]\asymp\sqrt{n} E [ LIS ( τ n )] ≍ n
lim n → ∞ 1 2 n LIS ( τ n ) = lim n → ∞ 1 2 n LIS ( σ n , μ f ) = sup ϕ ↗ ∫ 0 1 ϕ ′ ( t ) ρ f ( t , ϕ ( t ) ) d t = : K ( f ) \lim_{n\to\infty}\frac{1}{2\sqrt{n}}\operatorname{LIS}(\tau_n)
=
\lim_{n\to\infty}\frac{1}{2\sqrt{n}}\operatorname{LIS}(\sigma_{n,\mu_f})
=
\sup_{\phi\nearrow}\int_0^1\sqrt{\phi'(t)\rho_f(t,\phi(t))}\,\mathrm{d}t
=:K(f) n → ∞ lim 2 n 1 LIS ( τ n ) = n → ∞ lim 2 n 1 LIS ( σ n , μ f ) = ϕ ↗ sup ∫ 0 1 ϕ ′ ( t ) ρ f ( t , ϕ ( t )) d t =: K ( f ) where the limits hold in probability and in expectation, and the supremum ranges over all non-decreasing, right-continuous curves ϕ : [ 0 , 1 ) → [ 0 , 1 ) \phi:[0,1)\to[0,1) ϕ : [ 0 , 1 ) → [ 0 , 1 )
Proof. We will assume, w.l.o.g., that f f f f ( 0 ) = 1 f(0)=1 f ( 0 ) = 1 ε > 0 \varepsilon>0 ε > 0 n ε : = ⌊ ( 1 − ε ) n ⌋ n_\varepsilon:=\lfloor(1-\varepsilon)n\rfloor n ε := ⌊( 1 − ε ) n ⌋ τ n ∼ Luce ( θ ( n ) ( f ) ) \tau_n\sim\operatorname{Luce}(\theta^{(n)}(f)) τ n ∼ Luce ( θ ( n ) ( f )) σ n ∼ Sample n ( μ f ) \sigma_n\sim\operatorname{Sample}_n(\mu_f) σ n ∼ Sample n ( μ f ) I u n m a t c h e d ⊆ [ n ε ] \mathcal{I}_{\mathrm{unmatched}}\subseteq[n_\varepsilon] I unmatched ⊆ [ n ε ]
the LIS of τ n \tau_n τ n σ n \sigma_n σ n i i i n n n
LIS ( τ n ) \operatorname{LIS}(\tau_n) LIS ( τ n ) LIS ( σ n ) \operatorname{LIS}(\sigma_n) LIS ( σ n )
3. 1 n LIS ( σ n ) 3.\ \frac{1}{\sqrt{n}}\operatorname{LIS}(\sigma_n) 3. n 1 LIS ( σ n )
For π ∈ S n \pi\in\mathfrak{S}_n π ∈ S n 1 ≤ a ≤ b ≤ n 1\leq a\leq b\leq n 1 ≤ a ≤ b ≤ n π [ a , b ] : = Perm ( π ( i ) : a ≤ i ≤ b ) \pi^{[a,b]}:=\operatorname{Perm}(\pi(i):a\leq i\leq b) π [ a , b ] := Perm ( π ( i ) : a ≤ i ≤ b ) § 1.5 , LIS ( π [ a , b ] ) = LIS ( { π ( i ) : a ≤ i ≤ b } ) \operatorname{LIS}(\pi^{[a,b]})=\operatorname{LIS}(\{\pi(i):a\leq i\leq b\}) LIS ( π [ a , b ] ) = LIS ({ π ( i ) : a ≤ i ≤ b })
1. Bounding the LIS on the last indices. By Lemma 3.8 , if τ n ∼ Luce ( θ ( n ) ) \tau_n\sim\operatorname{Luce}(\theta^{(n)}) τ n ∼ Luce ( θ ( n ) ) τ n [ n ε , n ] \tau_n^{[n^\varepsilon,n]} τ n [ n ε , n ] S n − n ε + 1 \mathfrak{S}_{n-n^\varepsilon+1} S n − n ε + 1 ( θ i ( n ) ) n ε ≤ i ≤ n (\theta_i^{(n)})_{n^\varepsilon\leq i\leq n} ( θ i ( n ) ) n ε ≤ i ≤ n Theorem 2.1 and its proof,
E [ LIS ( τ n [ n ε , n ] ) ] ≤ 2 e 3 / 2 ∑ k ∈ Z m k ( n , ε ) where m k ( n , ε ) : = # { i ∈ [ n ε , n ] : k ≤ − log θ i ( n ) < k + 1 } . \mathbb{E}\left[\operatorname{LIS}\left(\tau_n^{[n^\varepsilon,n]}\right)\right]\leq2e^{3/2}\sum_{k\in\mathbb{Z}}\sqrt{m_k^{(n,\varepsilon)}}\qquad\text{where}\qquad m_k^{(n,\varepsilon)}:=\#\left\{i\in[n^\varepsilon,n]:k\leq-\log\theta_i^{(n)}<k+1\right\}. E [ LIS ( τ n [ n ε , n ] ) ] ≤ 2 e 3/2 k ∈ Z ∑ m k ( n , ε ) where m k ( n , ε ) := # { i ∈ [ n ε , n ] : k ≤ − log θ i ( n ) < k + 1 } . Since the weights are non-increasing, letting k ε : = ⌊ − log θ n ε ( n ) ⌋ ≥ 0 k_\varepsilon:=\lfloor-\log\theta_{n^\varepsilon}^{(n)}\rfloor\geq0 k ε := ⌊ − log θ n ε ( n ) ⌋ ≥ 0
E [ LIS ( τ n [ n ε , n ] ) ] ≤ 2 e 3 / 2 ∑ k ≥ k ε m k ( n , ε ) . (18) \mathbb{E}\left[\operatorname{LIS}\left(\tau_n^{[n^\varepsilon,n]}\right)\right]\leq2e^{3/2}\sum_{k\geq k_\varepsilon}\sqrt{m_k^{(n,\varepsilon)}}. \tag*{(18)} E [ LIS ( τ n [ n ε , n ] ) ] ≤ 2 e 3/2 k ≥ k ε ∑ m k ( n , ε ) . (18) Now, recall that we assume θ i ( n ) : = f ( i − 1 n ) \theta_i^{(n)}:=f\left(\frac{i-1}{n}\right) θ i ( n ) := f ( n i − 1 ) (6) to (8) ), we get that
∑ k ≥ k ε m k ( n , ε ) ≤ 2 + 2 ∑ k ≥ k ε n p k ( ε ) where p k ( ε ) : = Leb ( A k ∩ [ 1 − ε , 1 ) ) . \sum_{k\geq k_\varepsilon}\sqrt{m_k^{(n,\varepsilon)}}\leq2+2\sum_{k\geq k_\varepsilon}\sqrt{np_k^{(\varepsilon)}}\qquad\text{where}\qquad p_k^{(\varepsilon)}:=\operatorname{Leb}(A_k\cap[1-\varepsilon,1)). k ≥ k ε ∑ m k ( n , ε ) ≤ 2 + 2 k ≥ k ε ∑ n p k ( ε ) where p k ( ε ) := Leb ( A k ∩ [ 1 − ε , 1 )) . In order to argue that this divided by n \sqrt{n} n 0 0 0 ε → 0 \varepsilon\to0 ε → 0
(a) Assume that inf [ 0 , 1 ) f > 0 \inf_{[0,1)}f>0 inf [ 0 , 1 ) f > 0 f f f − log f -\log f − log f [ 0 , 1 ) [0,1) [ 0 , 1 ) ε > 0 \varepsilon>0 ε > 0 ⌊ − log f ⌋ \lfloor-\log f\rfloor ⌊ − log f ⌋ ( 1 − ε , 1 ) (1-\varepsilon,1) ( 1 − ε , 1 ) ε > 0 \varepsilon>0 ε > 0
∑ k ≥ k ε p k ( ε ) = p k ε ( ε ) ≤ ε → ε → 0 + 0. \sum_{k\geq k_\varepsilon}\sqrt{p_k^{(\varepsilon)}}=\sqrt{p_{k_\varepsilon}^{(\varepsilon)}}\leq\sqrt{\varepsilon}\xrightarrow[\varepsilon\to0+]{}0. k ≥ k ε ∑ p k ( ε ) = p k ε ( ε ) ≤ ε ε → 0 + 0. (b) Assume that inf [ 0 , 1 ) f = 0 \inf_{[0,1)}f=0 inf [ 0 , 1 ) f = 0 f ( t ) → 0 f(t)\to0 f ( t ) → 0 t ↑ 1 t\uparrow1 t ↑ 1 k ε → ∞ k_\varepsilon\to\infty k ε → ∞ ε → 0 \varepsilon\to0 ε → 0 p k ( ε ) p_k^{(\varepsilon)} p k ( ε ) p k p_k p k Lemma 2.8 and our assumption that E [ LIS ( τ n ) ] ≍ n \mathbb{E}[\operatorname{LIS}(\tau_n)]\asymp\sqrt{n} E [ LIS ( τ n )] ≍ n ( p k ) k ≥ 0 (\sqrt{p_k})_{k\geq0} ( p k ) k ≥ 0
∑ k ≥ k ε p k ( ε ) ≤ ∑ k ≥ k ε p k → ε → 0 + 0. \sum_{k\geq k_\varepsilon}\sqrt{p_k^{(\varepsilon)}}\leq\sum_{k\geq k_\varepsilon}\sqrt{p_k}\xrightarrow[\varepsilon\to0+]{}0. k ≥ k ε ∑ p k ( ε ) ≤ k ≥ k ε ∑ p k ε → 0 + 0. Coming back to (18) , we conclude that there exists an absolute constant c ε ≥ 0 c_{\varepsilon} \ge0 c ε ≥ 0 f f f ε \varepsilon ε
lim sup n → ∞ 1 n E [ LIS ( τ n [ n ε , n ] ) ] ≤ c ε , (19) \limsup_{n\to\infty} \frac{1}{\sqrt{n}} \mathbb{E}\left[\operatorname{LIS}\left(\tau_n^{[n\varepsilon,n]}\right)\right] \le c_{\varepsilon}, \tag*{(19)} n → ∞ lim sup n 1 E [ LIS ( τ n [ n ε , n ] ) ] ≤ c ε , (19) and that c ε → 0 c_{\varepsilon} \to0 c ε → 0 ε → 0 \varepsilon\to0 ε → 0 σ n \sigma_n σ n Lemma 3.3 .
Now, recall that we assumed E [ LIS ( τ n ) ] ≍ n \mathbb{E}[\operatorname{LIS}(\tau_n)] \asymp\sqrt{n} E [ LIS ( τ n )] ≍ n LIS ( σ n ) \operatorname{LIS}(\sigma_n) LIS ( σ n ) Lemma 3.3 . Hence, we can find an absolute constant C > 0 C > 0 C > 0
lim inf n → ∞ 1 n E [ LIS ( τ n ) ] ≥ C , (20) \liminf_{n\to\infty} \frac{1}{\sqrt{n}}\mathbb{E}[\operatorname{LIS}(\tau_n)] \ge C, \tag*{(20)} n → ∞ lim inf n 1 E [ LIS ( τ n )] ≥ C , (20) and likewise for σ n \sigma_n σ n (19) and (20) that
lim inf n → ∞ 1 n E [ LIS ( τ n [ 1 , n ε ] ) ] ≥ C − c ε = C − o ε ( 1 ) , (21) \liminf_{n\to\infty} \frac{1}{\sqrt{n}}\mathbb{E}\left[\operatorname{LIS}\left(\tau_n^{[1,n\varepsilon]}\right)\right] \ge C-c_{\varepsilon}=C-o_{\varepsilon}(1), \tag*{(21)} n → ∞ lim inf n 1 E [ LIS ( τ n [ 1 , n ε ] ) ] ≥ C − c ε = C − o ε ( 1 ) , (21) and likewise for σ n \sigma_n σ n o ε ( 1 ) o_{\varepsilon}(1) o ε ( 1 ) 0 0 0 ε → 0 \varepsilon\to0 ε → 0 ε > 0 \varepsilon>0 ε > 0 C − c ε ≥ 1 2 C C-c_{\varepsilon}\ge\frac{1}{2}C C − c ε ≥ 2 1 C
Finally, since τ n [ 1 , n ε ] \tau_n^{[1,n\varepsilon]} τ n [ 1 , n ε ] Corollary 2.18 together with (21) imply that
lim sup n → ∞ P ( LIS ( τ n [ 1 , n ε ] ) ≤ δ n ) → δ → 0 + 0 , (22) \limsup_{n\to\infty}\mathbb{P}\left(\operatorname{LIS}\left(\tau_n^{[1,n\varepsilon]}\right)\le\delta\sqrt{n}\right)\xrightarrow[\delta\to0^+]{}0, \tag*{(22)} n → ∞ lim sup P ( LIS ( τ n [ 1 , n ε ] ) ≤ δ n ) δ → 0 + 0 , (22) i.e., LIS ( { τ n ( i ) : i ∈ [ n ε ] } ) \operatorname{LIS}(\{\tau_n(i):i\in[n\varepsilon]\}) LIS ({ τ n ( i ) : i ∈ [ n ε ]}) n \sqrt{n} n σ n \sigma_n σ n
Comparing the discrete and the continuous models
Write
LIS ( { τ n ( i ) : i ∈ [ n ε ] ∖ I u n m a t c h e d } ) ≤ LIS ( { τ n ( i ) : i ∈ [ n ε ] } ) ≤ LIS ( { τ n ( i ) : i ∈ [ n ε ] ∖ I u n m a t c h e d } ) + LIS ( { τ n ( i ) : i ∈ I u n m a t c h e d } ) . \operatorname{LIS}(\{\tau_n(i):i\in[n\varepsilon]\setminus\mathcal{I}_{\mathrm{unmatched}}\})
\le\operatorname{LIS}(\{\tau_n(i):i\in[n\varepsilon]\})
\le\operatorname{LIS}(\{\tau_n(i):i\in[n\varepsilon]\setminus\mathcal{I}_{\mathrm{unmatched}}\})+\operatorname{LIS}(\{\tau_n(i):i\in\mathcal{I}_{\mathrm{unmatched}}\}). LIS ({ τ n ( i ) : i ∈ [ n ε ] ∖ I unmatched }) ≤ LIS ({ τ n ( i ) : i ∈ [ n ε ]}) ≤ LIS ({ τ n ( i ) : i ∈ [ n ε ] ∖ I unmatched }) + LIS ({ τ n ( i ) : i ∈ I unmatched }) . Since the middle term is of order Θ ( n ) \Theta(\sqrt{n}) Θ ( n ) (21) and (22) , item (iii) of our coupling (see Proposition 3.7 ) implies that
LIS ( { τ n ( i ) : i ∈ [ n ε ] } ) LIS ( { τ n ( i ) : i ∈ [ n ε ] ∖ I u n m a t c h e d } ) → n → ∞ 1 , \frac{\operatorname{LIS}(\{\tau_n(i):i\in[n\varepsilon]\})}{\operatorname{LIS}(\{\tau_n(i):i\in[n\varepsilon]\setminus\mathcal{I}_{\mathrm{unmatched}}\})}\xrightarrow[n\to\infty]{}1, LIS ({ τ n ( i ) : i ∈ [ n ε ] ∖ I unmatched }) LIS ({ τ n ( i ) : i ∈ [ n ε ]}) n → ∞ 1 , in probability and for the ratio of expectations, and likewise for σ n \sigma_n σ n Proposition 3.7 :
LIS ( τ n [ 1 , n ε ] ) LIS ( σ n [ 1 , n ε ] ) → n → ∞ 1 , (23) \frac{\operatorname{LIS}\left(\tau_n^{[1,n\varepsilon]}\right)}{\operatorname{LIS}\left(\sigma_n^{[1,n\varepsilon]}\right)}\xrightarrow[n\to\infty]{}1, \tag*{(23)} LIS ( σ n [ 1 , n ε ] ) LIS ( τ n [ 1 , n ε ] ) n → ∞ 1 , (23) in probability and for the ratio of expectations.
Concluding for the continuous model
In this final step of our proof, we shall argue that, for any given ε > 0 \varepsilon>0 ε > 0
2 K ε − ≤ lim inf n → ∞ 1 n LIS ( σ n [ 1 , n ε ] ) ≤ lim sup n → ∞ 1 n LIS ( σ n [ 1 , n ε ] ) ≤ 2 K ε + (24) 2K_{\varepsilon}^{-}\le\liminf_{n\to\infty}\frac{1}{\sqrt{n}}\operatorname{LIS}\left(\sigma_n^{[1,n\varepsilon]}\right)\le\limsup_{n\to\infty}\frac{1}{\sqrt{n}}\operatorname{LIS}\left(\sigma_n^{[1,n\varepsilon]}\right)\le2K_{\varepsilon}^{+} \tag*{(24)} 2 K ε − ≤ n → ∞ lim inf n 1 LIS ( σ n [ 1 , n ε ] ) ≤ n → ∞ lim sup n 1 LIS ( σ n [ 1 , n ε ] ) ≤ 2 K ε + (24) in expectation and in probability, where the constants K ε − , K ε + K_{\varepsilon}^{-},K_{\varepsilon}^{+} K ε − , K ε +
lim ε → 0 + K ε + = lim ε → 0 + K ε − = K , where K : = sup ϕ ∫ 0 1 ϕ ′ ( t ) ρ f ( t , ϕ ( t ) ) d t . (25) \lim_{\varepsilon\to0^+}K_{\varepsilon}^{+}=\lim_{\varepsilon\to0^+}K_{\varepsilon}^{-}=K,\qquad\text{where}\qquad K:=\sup_{\phi}\int_0^1\sqrt{\phi'(t)\rho_f(t,\phi(t))}\,\mathrm{d}t. \tag*{(25)} ε → 0 + lim K ε + = ε → 0 + lim K ε − = K , where K := ϕ sup ∫ 0 1 ϕ ′ ( t ) ρ f ( t , ϕ ( t )) d t . (25) Before proving eqs. (24) and (25) , let us see how they imply Theorem 3.13 . The lower bound is simple to derive:
lim inf n → ∞ 1 n LIS ( σ n ) ≥ sup ε > 0 lim inf n → ∞ 1 n LIS ( σ n [ 1 , n ε ] ) ≥ 2 K , \liminf_{n\to\infty}\frac{1}{\sqrt{n}}\operatorname{LIS}(\sigma_n)\ge\sup_{\varepsilon>0}\liminf_{n\to\infty}\frac{1}{\sqrt{n}}\operatorname{LIS}\left(\sigma_n^{[1,n\varepsilon]}\right)\ge2K, n → ∞ lim inf n 1 LIS ( σ n ) ≥ ε > 0 sup n → ∞ lim inf n 1 LIS ( σ n [ 1 , n ε ] ) ≥ 2 K , in probability and in expectation. Note that from there, our assumption that E [ LIS ( τ n ) ] ≍ n \mathbb{E}[\operatorname{LIS}(\tau_n)] \asymp\sqrt{n} E [ LIS ( τ n )] ≍ n σ n \sigma_n σ n Lemma 3.3 ) implies that K < ∞ K < \infty K < ∞
The corresponding upper bound is immediate for the expectation, using (19) . For the probability claim, consider δ > 0 \delta> 0 δ > 0 ε > 0 \varepsilon> 0 ε > 0
P ( LIS ( σ n ) ≥ 2 ( 1 + 3 δ ) K n ) ≤ o ( 1 ) + P ( LIS ( σ n ) ≥ ( 1 + 2 δ ) LIS ( σ n [ 1 , n ε ] ) ) ≤ o ( 1 ) + P ( LIS ( σ n [ n ε , n ] ) ≥ 2 δ LIS ( σ n [ 1 , n ε ] ) ) ≤ o ( 1 ) + P ( LIS ( σ n [ n ε , n ] ) ≥ δ K n ) ≤ o ( 1 ) + c ε δ K . \begin{aligned}
\mathbb{P}\left(\operatorname{LIS}(\sigma_n) \ge2(1+3\delta)K\sqrt{n}\right)
&\le o(1)+\mathbb{P}\left(\operatorname{LIS}(\sigma_n)\ge(1+2\delta)\operatorname{LIS}\left(\sigma_n^{[1,n^\varepsilon]}\right)\right)\\
&\le o(1)+\mathbb{P}\left(\operatorname{LIS}\left(\sigma_n^{[n^\varepsilon,n]}\right)\ge2\delta\operatorname{LIS}\left(\sigma_n^{[1,n^\varepsilon]}\right)\right)\\
&\le o(1)+\mathbb{P}\left(\operatorname{LIS}\left(\sigma_n^{[n^\varepsilon,n]}\right)\ge\delta K\sqrt{n}\right)\\
&\le o(1)+\frac{c_\varepsilon}{\delta K}.
\end{aligned} P ( LIS ( σ n ) ≥ 2 ( 1 + 3 δ ) K n ) ≤ o ( 1 ) + P ( LIS ( σ n ) ≥ ( 1 + 2 δ ) LIS ( σ n [ 1 , n ε ] ) ) ≤ o ( 1 ) + P ( LIS ( σ n [ n ε , n ] ) ≥ 2 δ LIS ( σ n [ 1 , n ε ] ) ) ≤ o ( 1 ) + P ( LIS ( σ n [ n ε , n ] ) ≥ δ K n ) ≤ o ( 1 ) + δ K c ε . where we used (24) for the first and third inequalities, (19) for the last inequality, and we let o ( 1 ) o(1) o ( 1 ) 0 0 0 n → ∞ n \to\infty n → ∞ ε > 0 \varepsilon> 0 ε > 0 δ > 0 \delta> 0 δ > 0 ε > 0 \varepsilon> 0 ε > 0 c ε → 0 c_\varepsilon\to0 c ε → 0 ε → 0 + \varepsilon\to0^+ ε → 0 +
lim sup n → ∞ 1 2 n LIS ( σ n ) ≤ K \limsup_{n\to\infty}\frac{1}{2\sqrt{n}}\operatorname{LIS}(\sigma_n)\le K n → ∞ lim sup 2 n 1 LIS ( σ n ) ≤ K in probability. The same holds for τ n \tau_n τ n (23) .
Now, it remains only to prove eqs. (24) and (25) . For α , β ∈ ( 0 , 1 ) \alpha,\beta\in(0,1) α , β ∈ ( 0 , 1 )
σ n ( α , β ) : = Perm ( σ n ( i ) : i ≤ α n , σ n ( i ) ≤ β n ) and σ n ⟨ α , β ⟩ : = Perm ( σ n ( i ) : i ≤ α n , σ n ( i ) ≥ β n ) , \sigma_n^{(\alpha,\beta)}:=\operatorname{Perm}(\sigma_n(i):i\le\alpha n,\sigma_n(i)\le\beta n)
\quad\text{and}\quad
\sigma_n^{\langle\alpha,\beta\rangle}:=\operatorname{Perm}(\sigma_n(i):i\le\alpha n,\sigma_n(i)\ge\beta n), σ n ( α , β ) := Perm ( σ n ( i ) : i ≤ α n , σ n ( i ) ≤ β n ) and σ n ⟨ α , β ⟩ := Perm ( σ n ( i ) : i ≤ α n , σ n ( i ) ≥ β n ) , and note that, letting α : = 1 − ε \alpha:=1-\varepsilon α := 1 − ε
LIS ( σ n ( α , β ) ) ≤ LIS ( σ n [ 1 , n ε ] ) ≤ LIS ( σ n ( α , β ) ) + LIS ( σ n ⟨ α , β ⟩ ) . \operatorname{LIS}\left(\sigma_n^{(\alpha,\beta)}\right)
\le\operatorname{LIS}\left(\sigma_n^{[1,n^\varepsilon]}\right)
\le\operatorname{LIS}\left(\sigma_n^{(\alpha,\beta)}\right)+\operatorname{LIS}\left(\sigma_n^{\langle\alpha,\beta\rangle}\right). LIS ( σ n ( α , β ) ) ≤ LIS ( σ n [ 1 , n ε ] ) ≤ LIS ( σ n ( α , β ) ) + LIS ( σ n ⟨ α , β ⟩ ) . Thus, by Corollary 3.10 and Proposition 3.12 ,
2 K α , β ≤ lim inf n → ∞ 1 n LIS ( σ n [ 1 , n ε ] ) ≤ lim sup n → ∞ 1 n LIS ( σ n [ 1 , n ε ] ) ≤ 2 K α , β + η α , β , 2K_{\alpha,\beta}\le\liminf_{n\to\infty}\frac{1}{\sqrt{n}}\operatorname{LIS}\left(\sigma_n^{[1,n^\varepsilon]}\right)
\le\limsup_{n\to\infty}\frac{1}{\sqrt{n}}\operatorname{LIS}\left(\sigma_n^{[1,n^\varepsilon]}\right)
\le2K_{\alpha,\beta}+\eta_{\alpha,\beta}, 2 K α , β ≤ n → ∞ lim inf n 1 LIS ( σ n [ 1 , n ε ] ) ≤ n → ∞ lim sup n 1 LIS ( σ n [ 1 , n ε ] ) ≤ 2 K α , β + η α , β , in probability and in expectation, for any given α : = 1 − ε ∈ ( 0 , 1 ) \alpha:=1-\varepsilon\in(0,1) α := 1 − ε ∈ ( 0 , 1 ) β ∈ ( 0 , 1 ) \beta\in(0,1) β ∈ ( 0 , 1 ) η α , β → 0 \eta_{\alpha,\beta}\to0 η α , β → 0 β → 1 \beta\to1 β → 1 β : = β ( α ) \beta:=\beta(\alpha) β := β ( α ) β ≥ α \beta\ge\alpha β ≥ α η α , β ≤ 1 − α \eta_{\alpha,\beta}\le1-\alpha η α , β ≤ 1 − α α : = 1 − ε \alpha:=1-\varepsilon α := 1 − ε β : = β ( α ) \beta:=\beta(\alpha) β := β ( α ) (24) with K − : = K α , β ( α ) K^-:=K_{\alpha,\beta(\alpha)} K − := K α , β ( α ) K + : = K α , β ( α ) + 1 2 ( 1 − α ) K^+:=K_{\alpha,\beta(\alpha)}+\frac{1}{2}(1-\alpha) K + := K α , β ( α ) + 2 1 ( 1 − α ) K α , β ( α ) → K K_{\alpha,\beta(\alpha)}\to K K α , β ( α ) → K α → 1 \alpha\to1 α → 1 Proposition 3.12 , this proves (25) and concludes the proof. □
On the variational problem
Lemma 3.14. Let f : [ 0 , 1 ) → ( 0 , ∞ ) f:[0,1)\to(0,\infty) f : [ 0 , 1 ) → ( 0 , ∞ ) C 1 C^1 C 1
K ( f ) : = sup ϕ : [ 0 , 1 ) ↗ [ 0 , 1 ) ∫ 0 1 ϕ ′ ( t ) ρ f ( t , ϕ ( t ) ) d t K(f):=\sup_{\phi:[0,1)\nearrow[0,1)}\int_0^1\sqrt{\phi'(t)\rho_f(t,\phi(t))}\,\mathrm{d}t K ( f ) := ϕ : [ 0 , 1 ) ↗ [ 0 , 1 ) sup ∫ 0 1 ϕ ′ ( t ) ρ f ( t , ϕ ( t )) d t be the limit constant of Theorem 3.13 , where the supremum ranges over all non-decreasing, right-continuous curves ϕ : [ 0 , 1 ) → [ 0 , 1 ) \phi:[0,1)\to[0,1) ϕ : [ 0 , 1 ) → [ 0 , 1 )
K ( f ) = sup u : [ 0 , 1 ) ↗ [ 0 , ∞ ) ∫ 0 1 f ( t ) u ′ ( t ) e − f ( t ) u ( t ) d t (26) K(f)=\sup_{u:[0,1)\nearrow[0,\infty)}\int_0^1\sqrt{f(t)u'(t)e^{-f(t)u(t)}}\,\mathrm{d}t \tag*{(26)} K ( f ) = u : [ 0 , 1 ) ↗ [ 0 , ∞ ) sup ∫ 0 1 f ( t ) u ′ ( t ) e − f ( t ) u ( t ) d t (26) where the supremum ranges over all non-decreasing, right-continuous curves u : [ 0 , 1 ) → [ 0 , ∞ ) u:[0,1)\to[0,\infty) u : [ 0 , 1 ) → [ 0 , ∞ )
Proof. Recall from (1) and (3) that, for ( x , y ) ∈ ( 0 , 1 ) 2 (x,y)\in(0,1)^2 ( x , y ) ∈ ( 0 , 1 ) 2
ρ f ( x , y ) = f ( x ) e − f ( x ) F − 1 ( y ) F ′ ( F − 1 ( y ) ) . \rho_f(x,y)=\frac{f(x)e^{-f(x)F^{-1}(y)}}{F'(F^{-1}(y))}. ρ f ( x , y ) = F ′ ( F − 1 ( y )) f ( x ) e − f ( x ) F − 1 ( y ) . The claimed formula is then straightforward by considering the mapping
ϕ : [ 0 , 1 ) ↗ [ 0 , 1 ) ⟷ u = F − 1 ∘ ϕ : [ 0 , 1 ) ↗ [ 0 , ∞ ) . \phi:[0,1)\nearrow[0,1)\quad\longleftrightarrow\quad u=F^{-1}\circ\phi:[0,1)\nearrow[0,\infty). ϕ : [ 0 , 1 ) ↗ [ 0 , 1 ) ⟷ u = F − 1 ∘ ϕ : [ 0 , 1 ) ↗ [ 0 , ∞ ) . □ \square □
Remark 3.15. It would not be difficult to see that we can restrict our attention to the curves u : [ 0 , 1 ) ↗ [ 0 , ∞ ) u:[0,1)\nearrow[0,\infty) u : [ 0 , 1 ) ↗ [ 0 , ∞ ) u ( 0 ) = 0 u(0)=0 u ( 0 ) = 0 ▲ \blacktriangle ▲
Letting A ( u ) : = ∫ 0 1 f ( t ) u ′ ( t ) e − f ( t ) u ( t ) d t A(u):=\int_0^1\sqrt{f(t)u'(t)e^{-f(t)u(t)}}\,\mathrm{d}t A ( u ) := ∫ 0 1 f ( t ) u ′ ( t ) e − f ( t ) u ( t ) d t K ( f ) = A ( u f ∗ ) K(f)=A(u_f^*) K ( f ) = A ( u f ∗ ) u f ∗ ∈ C 1 ( [ 0 , 1 ) , [ 0 , ∞ ) ) u_f^*\in C^1([0,1),[0,\infty)) u f ∗ ∈ C 1 ([ 0 , 1 ) , [ 0 , ∞ )) u f ∗ u_f^* u f ∗ τ n \tau_n τ n σ n , μ f \sigma_{n,\mu_f} σ n , μ f ϕ f ∗ : = F ∘ u f ∗ \phi_f^*:=F\circ u_f^* ϕ f ∗ := F ∘ u f ∗ [ 0 , 1 ] 2 [0,1]^2 [ 0 , 1 ] 2
Nonetheless, (26) yields non-trivial bounds for K ( f ) K(f) K ( f ) u 1 = F − 1 u_1=F^{-1} u 1 = F − 1 ϕ = id [ 0 , 1 ] \phi=\operatorname{id}_{[0,1]} ϕ = id [ 0 , 1 ]
A ( u 1 ) = ∫ 0 1 ρ f ( t , t ) d t A(u_1)=\int_0^1\sqrt{\rho_f(t,t)}\,\mathrm{d}t A ( u 1 ) = ∫ 0 1 ρ f ( t , t ) d t is related to the length of increasing subsequences that are close to the diagonal. However, computing A ( u 1 ) A(u_1) A ( u 1 ) f f f u 0 : = 1 f − 1 f ( 0 ) u_0:=\frac{1}{f}-\frac{1}{f(0)} u 0 := f 1 − f ( 0 ) 1
K ( f ) ≥ A ( u 0 ) = ∫ 0 1 − f ′ ( t ) f ( t ) f ( t ) f ( 0 ) e f ( t ) f ( 0 ) − 1 d t . (27) K(f)\ge A(u_0)=\int_0^1\sqrt{\frac{-f'(t)}{f(t)}\frac{f(t)}{f(0)}e^{\frac{f(t)}{f(0)}-1}}\,\mathrm{d}t. \tag*{(27)} K ( f ) ≥ A ( u 0 ) = ∫ 0 1 f ( t ) − f ′ ( t ) f ( 0 ) f ( t ) e f ( 0 ) f ( t ) − 1 d t . (27) Although u 0 u_0 u 0 u 1 u_1 u 1
K ( f ) ≥ A ( u 0 ) = 2 e ∫ 0 1 e s 2 / 2 d s , K(f)\ge A(u_0)=\frac{2}{\sqrt{e}}\int_0^1 e^{s^2/2}\,\mathrm{d}s, K ( f ) ≥ A ( u 0 ) = e 2 ∫ 0 1 e s 2 /2 d s , with corresponding curves u 0 ( t ) = t 1 − t u_0(t)=\frac{t}{1-t} u 0 ( t ) = 1 − t t ϕ 0 ( t ) = 1 − 1 − t t ( 1 − e − t 1 − t ) \phi_0(t)=1-\frac{1-t}{t}(1-e^{-\frac{t}{1-t}}) ϕ 0 ( t ) = 1 − t 1 − t ( 1 − e − 1 − t t ) Figure 5 , middle.
Figure 5. Simulations of the renormalized curves { ( I k n , τ n ( I k ) n ) : 1 ≤ k ≤ LIS ( τ n ) } \left\{\left(\frac{I_k}{n},\frac{\tau_n(I_k)}{n}\right):1\le k\le\operatorname{LIS}(\tau_n)\right\} { ( n I k , n τ n ( I k ) ) : 1 ≤ k ≤ LIS ( τ n ) } τ n \tau_n τ n f ( t ) = 1 f(t)=1 f ( t ) = 1 f ( t ) = 1 − t f(t)=1-t f ( t ) = 1 − t f β ( t ) = e − β t f_\beta(t)=e^{-\beta t} f β ( t ) = e − β t β = 6 \beta=6 β = 6 ϕ 0 = F ∘ u 0 \phi_0=F\circ u_0 ϕ 0 = F ∘ u 0 u 0 = 1 / f − 1 u_0=1/f-1 u 0 = 1/ f − 1 Lemma 3.14 is also plotted. In all three cases, we sampled 5 random permutations (each with a different color) of size 52000 and plotted an arbitrary longest increasing subsequence (the scattered points). In the case of uniform permutations, the longest increasing subsequences are indeed concentrated around the diagonal, and the fluctuations are described by geodesics in the directed landscape [17 ] .
K ( f β ) ≥ A ( u 0 ) = β e ∫ 0 1 e 1 2 e − β t d t , K(f_\beta)\ge A(u_0)=\sqrt{\frac{\beta}{e}}\int_0^1 e^{\frac{1}{2}e^{-\beta t}}\,\mathrm{d}t, K ( f β ) ≥ A ( u 0 ) = e β ∫ 0 1 e 2 1 e − β t d t , which can be expressed in terms of the exponential integral function. In particular, we derive the simpler bound K ( f β ) > β / e K(f_\beta)>\sqrt{\beta/e} K ( f β ) > β / e K ( f β ) ≥ 1 K(f_\beta)\ge1 K ( f β ) ≥ 1 3 L β = β − 1 / 2 arsinh ( e β − 1 ) L_\beta=\beta^{-1/2}\operatorname{arsinh}(\sqrt{e^\beta}-1) L β = β − 1/2 arsinh ( e β − 1 ) [27 ] , and deduce that K ( f β ) > L β K(f_\beta)>L_\beta K ( f β ) > L β β \beta β β ≥ 7 \beta\ge7 β ≥ 7
Acknowledgments
V.D. is partially supported by the ANR project LOUCCOUM (Large Objects Under Combinatorial Constraints and Outside Uniform Models, ANR-24-CE40-7809). J.B. is partially supported by NSF grant DMS-2441646 and an Alfred P. Sloan Research Fellowship.
AI Disclosure
An AI tool was used for literature search and during the revision of this manuscript to check for possible errors, typographical mistakes, and language issues. It was not used to develop the mathematical ideas, results, or proofs. All suggested changes were reviewed by the authors, who take full responsibility for the final content of the paper.
Three probability lemmas
In this short appendix, we collect three general probability results that we use in our proofs. The first one is an elementary estimate for the expectation of the square root of a binomial random variable; we include a quick proof for completeness.
Lemma A.1. Let N N N n ∈ N n\in\mathbb{N} n ∈ N p ∈ [ 0 , 1 ] p\in[0,1] p ∈ [ 0 , 1 ]
E [ N ] ≍ min { n p , n p } \mathbb{E}\left[\sqrt{N}\right]\asymp\min\{np,\sqrt{np}\} E [ N ] ≍ min { n p , n p } uniformly over n ∈ N n\in\mathbb{N} n ∈ N p ∈ [ 0 , 1 ] p\in[0,1] p ∈ [ 0 , 1 ]
Proof. For simplicity, we assume that n ≥ 4 n\ge4 n ≥ 4
Small parameters. First, assume that n p ≤ 3 np\le3 n p ≤ 3 N ≤ N \sqrt{N}\le N N ≤ N
E [ N ] ≤ n p . \mathbb{E}\left[\sqrt{N}\right]\le np. E [ N ] ≤ n p . For the lower bound, we have
E [ N ] ≥ n p ( 1 − p ) n − 1 ≥ n p ( 1 − 3 n ) n , \mathbb{E}\left[\sqrt{N}\right]\ge np(1-p)^{n-1}\ge np\left(1-\frac{3}{n}\right)^n, E [ N ] ≥ n p ( 1 − p ) n − 1 ≥ n p ( 1 − n 3 ) n , and the conclusion easily follows.
Large parameters. Now, assume that n p > 3 np>3 n p > 3 E [ N ] ≤ n p \mathbb{E}\left[\sqrt{N}\right]\le\sqrt{np} E [ N ] ≤ n p
P ( ∣ N − n p ∣ ≥ 2 n p ) ≤ 1 2 \mathbb{P}\left(\lvert N-np\rvert\ge\sqrt{2np}\right)\le\frac{1}{2} P ( ∣ N − n p ∣ ≥ 2 n p ) ≤ 2 1 by the Bienaymé–Tchebychev inequality, and thus:
E [ N ] ≥ n p − 2 n p P ( N ≥ n p − 2 n p ) ≥ 1 2 1 − 2 3 n p , \mathbb{E}\left[\sqrt{N}\right] \ge\sqrt{np-\sqrt{2np}}\mathbb{P}\left(N \ge np-\sqrt{2np}\right) \ge\frac{1}{2}\sqrt{1-\sqrt{\frac{2}{3}}\sqrt{np}}, E [ N ] ≥ n p − 2 n p P ( N ≥ n p − 2 n p ) ≥ 2 1 1 − 3 2 n p , and the conclusion follows.
Then, we state a useful result about the coupling of exponential random variables.
Lemma A.2. Fix η ∈ ( 0 , 1 / 2 ) \eta\in(0,1/2) η ∈ ( 0 , 1/2 ) δ ∈ ( 0 , η / 2 ) \delta\in(0,\eta/2) δ ∈ ( 0 , η /2 ) θ , θ ′ ∈ [ η , 1 ] \theta,\theta' \in[\eta,1] θ , θ ′ ∈ [ η , 1 ] ∣ θ − θ ′ ∣ ≤ δ |\theta-\theta'| \le\delta ∣ θ − θ ′ ∣ ≤ δ E ∼ Exp ( θ ) E \sim\operatorname{Exp}(\theta) E ∼ Exp ( θ ) T ∼ Exp ( θ ′ ) T \sim\operatorname{Exp}(\theta') T ∼ Exp ( θ ′ )
(i) P ( E ≠ T ) ≤ 2 δ η ( 1 + log 1 2 δ ) \mathbb{P}(E \ne T) \le\frac{2\delta}{\eta}\left(1+\log\frac{1}{2\delta}\right) P ( E = T ) ≤ η 2 δ ( 1 + log 2 δ 1 )
(ii) the law of E E E { E ≠ T } \{E \ne T\} { E = T } r θ r_\theta r θ [ 0 , ∞ ) [0,\infty) [ 0 , ∞ ) r θ ≤ R g r_\theta\le Rg r θ ≤ R g
R : = 1 η 1 − log ( 2 δ ) 1 − log ( 2 δ ) + log η R := \frac{1}{\eta}\frac{1-\log(2\delta)}{1-\log(2\delta)+\log\eta} R := η 1 1 − log ( 2 δ ) + log η 1 − log ( 2 δ ) and g g g ( δ , η ) (\delta,\eta) ( δ , η )
Proof. This is a standard approach by (almost) maximal coupling. Let f 1 f_1 f 1 f 2 f_2 f 2 Exp ( θ ) \operatorname{Exp}(\theta) Exp ( θ ) Exp ( θ ′ ) \operatorname{Exp}(\theta') Exp ( θ ′ ) F : ( λ , x ) ∈ ( 0 , ∞ ) 2 ↦ λ e − λ x F : (\lambda,x) \in(0,\infty)^2 \mapsto\lambda e^{-\lambda x} F : ( λ , x ) ∈ ( 0 , ∞ ) 2 ↦ λ e − λ x F ( θ , ⋅ ) = f 1 ( ⋅ ) F(\theta,\cdot)=f_1(\cdot) F ( θ , ⋅ ) = f 1 ( ⋅ ) F ( θ ′ , ⋅ ) = f 2 ( ⋅ ) F(\theta',\cdot)=f_2(\cdot) F ( θ ′ , ⋅ ) = f 2 ( ⋅ ) ∣ ∂ λ F ( λ , x ) ∣ ≤ 2 |\partial_\lambda F(\lambda,x)| \le2 ∣ ∂ λ F ( λ , x ) ∣ ≤ 2 ( λ , x ) ∈ ( 0 , ∞ ) 2 (\lambda,x) \in(0,\infty)^2 ( λ , x ) ∈ ( 0 , ∞ ) 2
for all x ≥ 0 , ∣ f 1 ( x ) − f 2 ( x ) ∣ ≤ 2 δ . \text{for all }x \ge0,\qquad|f_1(x)-f_2(x)| \le2\delta. for all x ≥ 0 , ∣ f 1 ( x ) − f 2 ( x ) ∣ ≤ 2 δ . Then, let h : x ∈ [ 0 , ∞ ) ↦ max { 0 , f 1 ( x ) − 2 δ } h : x \in[0,\infty) \mapsto\max\{0,f_1(x)-2\delta\} h : x ∈ [ 0 , ∞ ) ↦ max { 0 , f 1 ( x ) − 2 δ } x θ : = 1 θ log θ 2 δ ≥ 0 x_\theta:= \frac{1}{\theta}\log\frac{\theta}{2\delta} \ge0 x θ := θ 1 log 2 δ θ ≥ 0 δ θ : = 2 δ θ ( 1 + log θ 2 δ ) \delta_\theta:= \frac{2\delta}{\theta}\left(1+\log\frac{\theta}{2\delta}\right) δ θ := θ 2 δ ( 1 + log 2 δ θ )
h = ( f 1 − 2 δ ) 1 [ 0 , x θ ] h=(f_1-2\delta)\mathbb{1}_{[0,x_\theta]} h = ( f 1 − 2 δ ) 1 [ 0 , x θ ] and
∫ 0 ∞ ( f 1 ( x ) − h ( x ) ) d x = δ θ . \int_0^\infty(f_1(x)-h(x))\,\mathrm{d}x=\delta_\theta. ∫ 0 ∞ ( f 1 ( x ) − h ( x )) d x = δ θ . We couple E ∼ Exp ( θ ) E \sim\operatorname{Exp}(\theta) E ∼ Exp ( θ ) T ∼ Exp ( θ ′ ) T \sim\operatorname{Exp}(\theta') T ∼ Exp ( θ ′ )
Let U , P , Q 1 , Q 2 U,P,Q_1,Q_2 U , P , Q 1 , Q 2 U U U [ 0 , 1 ] [0,1] [ 0 , 1 ] P P P 1 1 − δ θ h \frac{1}{1-\delta_\theta}h 1 − δ θ 1 h i ∈ { 1 , 2 } i \in\{1,2\} i ∈ { 1 , 2 } Q i Q_i Q i 1 δ θ ( f i − h ) \frac{1}{\delta_\theta}(f_i-h) δ θ 1 ( f i − h ) [ 0 , ∞ ) [0,\infty) [ 0 , ∞ )
if U ≤ 1 − δ θ U \le1-\delta_\theta U ≤ 1 − δ θ E = T = P E=T=P E = T = P
otherwise, if U > 1 − δ θ U>1-\delta_\theta U > 1 − δ θ E = Q 1 E=Q_1 E = Q 1 T = Q 2 T=Q_2 T = Q 2
It is clear that this properly defines a coupling of E ∼ Exp ( θ ) E \sim\operatorname{Exp}(\theta) E ∼ Exp ( θ ) T ∼ Exp ( θ ′ ) T \sim\operatorname{Exp}(\theta') T ∼ Exp ( θ ′ ) Q 1 ≠ Q 2 Q_1 \ne Q_2 Q 1 = Q 2
P ( E ≠ T ) = δ θ ≤ 2 δ η ( 1 + log 1 2 δ ) = : ε , \mathbb{P}(E \ne T)=\delta_\theta\le\frac{2\delta}{\eta}\left(1+\log\frac{1}{2\delta}\right)=:\varepsilon, P ( E = T ) = δ θ ≤ η 2 δ ( 1 + log 2 δ 1 ) =: ε , proving the first item. Then, conditionally on the event { E ≠ T } \{E \ne T\} { E = T } E E E
r θ : = 1 δ θ ( f 1 − h ) = 1 δ θ ( 2 δ 1 [ 0 , x θ ) + f 1 1 [ x θ , ∞ ) ) . r_\theta:=\frac{1}{\delta_\theta}(f_1-h)=\frac{1}{\delta_\theta}\left(2\delta\mathbb{1}_{[0,x_\theta)}+f_1\mathbb{1}_{[x_\theta,\infty)}\right). r θ := δ θ 1 ( f 1 − h ) = δ θ 1 ( 2 δ 1 [ 0 , x θ ) + f 1 1 [ x θ , ∞ ) ) . Observing that
x θ ≤ 1 η log 1 2 δ = : ξ , x_\theta\le\frac{1}{\eta}\log\frac{1}{2\delta}=:\xi, x θ ≤ η 1 log 2 δ 1 =: ξ , we can write, for all $x \ge 0,
f 1 ( x ) − h ( x ) ≤ 2 δ 1 [ 0 , ξ ) ( x ) + e − η x 1 [ ξ , ∞ ) ( x ) = : g ~ ( x ) , f_1(x)-h(x) \le2\delta\mathbb{1}_{[0,\xi)}(x)+e^{-\eta x}\mathbb{1}_{[\xi,\infty)}(x)=:\widetilde{g}(x), f 1 ( x ) − h ( x ) ≤ 2 δ 1 [ 0 , ξ ) ( x ) + e − η x 1 [ ξ , ∞ ) ( x ) =: g ( x ) , where g ~ \widetilde{g} g ε \varepsilon ε [ 0 , ∞ ) [0,\infty) [ 0 , ∞ ) r θ ≤ 1 δ θ ⋅ ( 1 ε g ~ ) r_\theta\le\frac{1}{\delta_\theta}\cdot\left(\frac{1}{\varepsilon}\widetilde{g}\right) r θ ≤ δ θ 1 ⋅ ( ε 1 g )
Finally, we recall the famous Dvoretzky–Kiefer–Wolfowitz (DKW) inequality.
Theorem A.3. Let ( X i ) i ≥ 1 (X_i)_{i\ge1} ( X i ) i ≥ 1 F F F n ∈ N n \in\mathbb{N} n ∈ N
F n : x ∈ R ↦ 1 n ∑ 1 ≤ i ≤ n 1 X i ≤ x F_n : x \in\mathbb{R} \mapsto\frac{1}{n}\sum_{1\le i\le n}\mathbf{1}_{X_i\le x} F n : x ∈ R ↦ n 1 1 ≤ i ≤ n ∑ 1 X i ≤ x denote the associated empirical distribution function. Then, for all t ≥ 0 t \ge0 t ≥ 0
P ( sup x ∈ R ∣ F n ( x ) − F ( x ) ∣ > t ) ≤ 2 e − 2 n t 2 . \mathbb{P}\left(\sup_{x\in\mathbb{R}} \lvert F_n(x)-F(x)\rvert>t\right)\le2e^{-2nt^2}. P ( x ∈ R sup ∣ F n ( x ) − F ( x )∣ > t ) ≤ 2 e − 2 n t 2 . We restate it in the case of uniform random variables for our applications.
Corollary A.4. Let ( U i ) 1 ≤ i ≤ n (U_i)_{1\le i\le n} ( U i ) 1 ≤ i ≤ n [ 0 , 1 ] [0,1] [ 0 , 1 ] U ( 1 ) < ⋯ < U ( n ) U_{(1)}<\cdots<U_{(n)} U ( 1 ) < ⋯ < U ( n ) t ≥ 0 t\ge0 t ≥ 0
P ( sup 1 ≤ i ≤ n ∣ U ( i ) − i − 1 n ∣ > t ) ≤ 2 e − 2 n t 2 . \mathbb{P}\left(\sup_{1\le i\le n}\left\lvert U_{(i)}-\frac{i-1}{n}\right\rvert>t\right)\le2e^{-2nt^2}. P ( 1 ≤ i ≤ n sup U ( i ) − n i − 1 > t ) ≤ 2 e − 2 n t 2 . 
