VMSTA Modern Stochastics: Theory and Applications 2351-60542351-60462351-6046 VTeXMokslininkų g. 2A, 08412 Vilnius, Lithuania VMSTA188 10.15559/21-VMSTA188 Research Article Probabilistic analysis of vantage point trees BohunVladyslavvladyslavbogun@gmail.com Faculty of Computer Science and Cybernetics, Taras Shevchenko National University of Kyiv, 01601 Kyiv, Ukraine 2021 482021844134342742021872021872021 © 2021 The Author(s). Published by VTeX2021 Open access article under the CC BY license.

Probabilistic properties of vantage point trees are studied. A vp-tree built from a sequence of independent identically distributed points in [ − 1 , 1 ] d with the ℓ ∞ -distance function is considered. The length of the leftmost path in the tree, as well as partitions over the space it produces are analyzed. The results include several convergence theorems regarding these characteristics, as the number of nodes in the tree tends to infinity.

 Fixed-point equation machine learning Markov chain nearest neighbor search probabilistic analysis random tree similarity search vantage point tree vp-tree 60F05 60J05 60J20 68P05 68W40 The author was supported by the National Research Foundation of Ukraine (project 2020.02/0014 “Asymptotic regimes of perturbed random walks: on the edge of modern and classical probability”). Introduction

A vantage point tree (vp-tree) is a data structure for fast executing of nearest neighbor search queries in a given metric space. This class of trees was first introduced in 1993 in [17], and is widely used since then. It is not the only class of trees used for nearest neighbor search, other famous examples being kd-trees [3, 12], ball trees [14] as well as many other data structures.

Nearest neighbor search is used nowadays in a wide range of tasks. A simple example of day-to-day usage is geographic search of objects close to a specific location. The nearest points search is used in computational geometry, for example, for identifying intersections, which is a routine task in computer graphics or physics simulations. Last but not least example we mention here is a similarity search, such as search for similar images or similar articles.

Another major field, where the nearest neighbor search is an important tool, is machine learning. More precisely, it is used in variety of regression models. We refer the reader to [5] and [7] for a nice introduction to such models. We also refer to [6], which is a good exposition of ideas behind solving classification problem with the nearest neighbors search. These models proved useful in areas of classification such as text categorization, multimedia categorization and search, pattern recognition, information retrieval and many others. Recent studies have started to combine the nearest neighbor search and neural networks for better and more stable results, see, for example, [15].

Although the fast nearest neighbor search is important by itself, as well as an important ingredient in many algorithms, it and the corresponding data structures are not fully understood from the mathematical viewpoint. Most of the results describing the structure of these trees were obtained using empirical methods. For example, in [9] or [16] vp-trees and their heuristic variations were statistically investigated on specific datasets. Another approach is to compare different tree structures, for example, vp-trees and kd-trees, and collate their characteristics on the same datasets, see [11, 13]. In this paper we use a probabilistic approach to analyze a vp-tree and some related characteristics, as the number of nodes in the tree goes to infinity.

The structure of this paper is the following. In Section 2 we describe a vp-tree model and introduce characteristics that we are going to study. Section 3 contains our main results. In Section 4 we specialize some of the results to a number of partial cases and analyze them in more details.

 Random vantage point tree model

Let ( X , dist ) be an arbitrary metric space. A vp-tree is a binary tree in which each node T stores two values: an element x T ∈ X called a vantage point and a threshold τ T > 00$]]>. One of the most common ways to construct a vp-tree is to do this in a recursive manner from a sequence of elements x 1 , x 2 , … . The tree is empty at the beginning, the first element x 1 is always stored in its root and some threshold τ is assigned. In order to insert the n-th element x n the following recursive procedure is executed. We start from node T which is a root of the tree. If dist ( x T , x n ) ≤ τ then we proceed recursively by adding a new element to the T-th left son, otherwise we proceed into the right son. When on some step the node is empty, then the value x n is stored in it and some threshold is assigned.

In this article we study a special class of random vp-trees. More precisely we consider the metric space ( [ − 1 , 1 ] d , dist ) ( d ≥ 1) with a max-distance function dist ( x , y ) = max 1 ≤ i ≤ d | x i − y i | .

We also need to specify the choice of the thresholds. To this end, fix a parameter τ ∈ ( 0 , 1 ). The threshold of each node T is given by the rule τ T = τ h , where h is the distance from T to the root of the tree plus 1. Another possible option is to pick h as the number of “left turns” in the path from the root to T plus 1. Let us emphasize that such a choice of thresholds is quite natural. If one wants to assign thresholds as mean distances then they will also follow the exponential pattern.

We define the leftmost path of a vp-tree (or of an arbitrary binary tree) as a path which starts in the root and always goes into the left son of the current node till reaching a leaf. Note that for both aforementioned rules of picking a threshold, the value h is the same for elements of the leftmost path.

The sequence of elements x 1 , x 2 , … is a sequence of independent uniformly distributed points on [ − 1 , 1 ] d and this makes the vp-tree, that we construct, random.

Each node in the leftmost path can be enumerated starting from 1. To understand how leftmost path is formed and evolves let us associate with each node T h ( h ≥ 1) in this path a part of space I h ⊂ X, which contains all points x that, if added to the tree would be saved in left subtree of T h . It is obvious that I h ⊂ I h − 1 and, furthermore, a point x is saved in the left subtree of T h if dist ( x , x T h ) ≤ τ h . This gives I h = I h − 1 ∩ B τ h ( x T h ) , h ≥ 1 , where B τ h ( x T h ) is a metric ball of radius τ h and center x T h , that is, B τ h ( x T h ) = { x ∈ X : dist ( x , x T h ) ≤ τ h } . Note that by our choice of the metric, dist ( x , x T h ) ≤ τ h is a d-dimensional cube. The root T 1 of the tree is always a part of the leftmost path, hence we can naturally put I 0 : = X = [ − 1 , 1 ] d which is also a cube. From (2) we conclude that, for all h ≥ 1, I h is an intersection of a rectangle and a cube, and hence is a rectangle itself with edges being parallel to coordinate axes. For such figures it is enough (up to parallel translations) to store only information about their sizes in each dimension which we denote by I h ( i ) , 1 ≤ i ≤ d.

Let T h − 1 be currently the last node in the leftmost path. Then the new node T h will be added to the left of T h − 1 if a new point x n falls inside I h − 1 . From the properties of the uniform distribution, conditionally on x n ∈ I h − 1 , x n has the uniform distribution on I h − 1 . Taking into account that I h − 1 is a rectangle, we also obtain that x n ’s position inside I h − 1 has the uniform distribution along every dimension i = 1 , … , d. Thus, we can write d recursive equations in each dimension for the size of each side of I h , which is just a size of an intersection of two segments: a segment of length I h − 1 ( i ) and a segment of radius τ h and a center distributed uniformly inside the first segment. We compute the size I h ( i ) as the distance between right and left endpoints of the intersection. Let u h ( i ) , h ≥ 1, 1 ≤ i ≤ d, be a family of independent uniformly distributed random variables on [ 0 , 1 ]. We have, for h ≥ 1, 1 ≤ i ≤ d, I h ( i ) = min { I h − 1 ( i ) , u h ( i ) I h − 1 ( i ) + τ h } − max { 0 , u h ( i ) I h − 1 ( i ) − τ h } = ( u h ( i ) I h − 1 ( i ) − max { 0 , u h ( i ) I h − 1 ( i ) − τ h } ) + ( min { I h − 1 ( i ) , u h ( i ) I h − 1 ( i ) + τ h } − u h ( i ) I h − 1 ( i ) ) = ( u h ( i ) I h − 1 ( i ) + min { 0 , τ h − u h ( i ) I h − 1 ( i ) } ) + ( min { I h − 1 ( i ) , u h ( i ) I h − 1 ( i ) + τ h } − u h ( i ) I h − 1 ( i ) ) = min { u h ( i ) I h − 1 ( i ) , τ h } + min { ( 1 − u h ( i ) ) I h − 1 ( i ) , τ h } . Making the substitution X h ( i ) : = I h ( i ) / τ h we obtain the basic recursive formula describing evolution of I h in max-distance case: X h ( i ) = min u h ( i ) X h − 1 ( i ) τ , 1 + min ( 1 − u h ( i ) ) X h − 1 ( i ) τ , 1 .

Convergence of the length of the leftmost path The analysis of the process <inline-formula id="j_vmsta188_ineq_058"><alternatives><mml:math> <mml:mo mathvariant="normal" fence="true" stretchy="false">(</mml:mo> <mml:msub> <mml:mrow> <mml:mi mathvariant="italic">X</mml:mi> </mml:mrow> <mml:mrow> <mml:mi mathvariant="italic">h</mml:mi> </mml:mrow> </mml:msub> <mml:mo mathvariant="normal" fence="true" stretchy="false">)</mml:mo></mml:math><tex-math><![CDATA[$({X_{h}})$]]></tex-math></alternatives></inline-formula>

The process (5) defines sizes of X h = I h / τ h in different dimensions. ( X h ) h ≥ 0 can be considered as a Markov chain over rectangles (with omitting their positions). We define by | X h | (or | I h |) a Lebesgue measure of a corresponding rectangle, which can be simply computed knowing sizes of each edge | X h | = ∏ i = 1 d X h ( i ) .

The Markov chain (5) satisfies 1 ≤ X h ( i ) ≤ 2 , for h ≥ 0 and 1 ≤ i ≤ d.

Let us fix i and prove the statement on h by using induction. For a random vp-tree I 0 = X = B 1 ( 0 ) = [ − 1 , 1 ] d , hence X 0 ( i ) = I 0 ( i ) = 2 and the statement holds. Since min { a , b } ≤ b from (5) we have X h ( i ) ≤ 1 + 1 = 2 . To show that X h ( i ) ≥ 1 we first note that if any of the minimums in (5) takes value 1, then the statement holds. On the other hand, if both minimums are less than 1, then X h ( i ) = u h ( i ) X h − 1 ( i ) τ + ( 1 − u h ( i ) ) X h − 1 ( i ) τ = X h − 1 ( i ) τ ≥ X h − 1 ( i ) ≥ 1 by the inductive assumption, and since τ ∈ ( 0 , 1 ).  □

Let us denote by S a set of all possible values the chain ( X h ) can visit provided that X 0 = B 1 ( 0 ). Note that S is uncountable.

We shall use the notation of stochastic ordering which we recall for convenience.

For two random variables X and Y we say that Y stochastically dominates X and write X ≤ s t Y if P { X ≤ t } ≥ P { Y ≤ t } for all t ∈ R .

The key ingredient for the subsequent analysis is the following theorem which says that the chain ( X h ) h ≥ 0 visits the state B 1 ( 0 ) relatively often.

Fix α ∈ S and put R α : = inf { h ≥ 1 : X h = B 1 ( 0 ) given that X 0 = α } . Then E R α < ∞.

We do believe that the counterpart of this theorem holds in arbitrary metric on [ − 1 , 1 ] d , however we have not been able to prove it in such generality.

We rewrite (2) as follows: X h + 1 = X h τ ⋂ B 1 ( u h + 1 ∗ ) , where u h + 1 ∗ is uniformly distributed inside X h / τ.

Since the positions of rectangles are not important, the recursive equation (11) can be also rewritten as X h + 1 = X h − u h + 1 τ ⋂ B 1 ( 0 ) , where u h + 1 is uniformly distributed in X h .

From Proposition 3.1 it follows that for any state X h there is a d-dimensional square with sides 1 inside X h , or in other words there is always a point x ˆ h such that B δ ( x ˆ h ) ⊂ X h with δ = 1 / 2.

Let us assume that point u h + 1 is chosen inside B δ ( x ˆ h ) and denote Δ = dist ( u h + 1 , x ˆ h ) ≤ δ .

From the triangle inequality we obtain max y ∈ ∂ B δ ( x ˆ h ) dist ( u h + 1 , y ) ≤ Δ + δ , min y ∈ ∂ B δ ( x ˆ h ) dist ( u h + 1 , y ) ≥ δ − Δ , where ∂ B defines the boundary of the set B.

Then, in view of (12), we have max y ∈ ∂ ( B δ ( x ˆ h ) − u h + 1 ) / τ dist ( 0 , y ) ≤ Δ + δ τ , and min y ∈ ∂ ( B δ ( x ˆ h ) − u h + 1 ) / τ dist ( 0 , y ) ≥ δ − Δ τ .

From (16) we have our first property that if Δ + δ τ ≤ 1 (or equally Δ ≤ τ − δ), then B δ / τ ( ( x h ˆ − u h + 1 ) / τ ) ⊂ X h + 1 . From (17) we have our second property that if δ − Δ τ ≥ 1 (or equally Δ ≤ δ − τ), then X h + 1 = B 1 ( 0 ).

Let us now fix a constant k = min { k ∈ N : 1 + τ 2 τ k − 1 ≤ 1 2 }. Since B 1 / 2 ( x ˆ h ) ⊂ X h , we have B 1 + τ 2 τ k − 1 ( x ˆ h ) ⊂ X h . Since k ≥ 2, it holds 1 + τ 2 τ k − 1 < τ. Therefore, if u h + 1 ∈ B ε 1 ( x ˆ h ) with ε 1 = τ − 1 + τ 2 τ k − 1 , which happens with a positive probability, we will obtain B 1 + τ 2 τ k − 2 ( x ˆ h + 1 ) ⊂ X h + 1 from the first property. Repeating this k − 1 times in total, where ε i = τ − 1 + τ 2 τ k − i > 00$]]>, for 1 ≤ i ≤ k − 1, we obtain that B 1 + τ 2 ( x ˆ h + k − 1 ) ⊂ X h + k − 1 and 1 + τ 2 > τ\tau $]]>. Thus, if u h + k ∈ B ε k ( x ˆ h + k − 1 ), which happens with a positive probability, where ε k = 1 + τ 2 − τ, we get that X h + k = B 1 ( 0 ) from the second property. Summarizing, we see that from an arbitrary state α ∈ S the chain jumps in k steps to the state B 1 ( 0 ) with a positive probability which is independent of the starting state α. Note that k also only depends on τ.

We split the evolution of the chain into blocks of length k. The state at the end of each block can be B 1 ( 0 ) with a positive probability, say p, obtained from the described scheme. We denote by g a number of the first block which ends up in the state B 1 ( 0 ). Then since actual probability to end up in the state B 1 ( 0 ) at the end of the block is not less than p we have, for any t ≥ 0, P { g ≤ t } ≥ P { G ≤ t } , where G has a geometric distribution with parameter p (number of trials). Or in terms of stochastic order g ≤ s t G .

Similarly, since the moment R α of the first visit to state B 1 ( 0 ) (after starting state) can occur in the middle of each block, we can write R α ≤ s t k g .

From the properties of stochastic order, inequality also holds for expectations, hence combining last two comparisons we have E R α ≤ k E G = k p < ∞ .  □

We note that in the proof of Theorem 3.3 we did not significantly use that u h has the uniform distribution, and it works for any absolutely continuous distribution, since probability for u h to fall inside some B ε ( x ˆ h ) is positive and larger than some fixed positive constant.

The process (11) in particular case τ = 1 is called the diminishing process of Balint Toth. This process was studied in various partial cases including one-dimensional [1] and multi-dimensional case [10] with B 1 ( 0 ) = [ − 1 , 1 ] d , as well as in other metrics [2, 10]. However evolution of this process with τ < 1 differs a lot and requires an independent study, whilst methods used for τ = 1 cannot be applied to treat the case τ < 1.

From Theorem 3.3 it follows that the chain ( X h ) h ≥ 0 evolves as follows. There is a special state B 1 ( 0 ), which the chain visits infinitely often and time to return to this state is a.s. finite and, moreover, has a finite mean. Thus, the whole evolution of X h can be split into independent cycles between visiting the state B 1 ( 0 ).

In order to proceed we need to recall a notion of the Harris chains. For information about Harris chains and examples we refer the reader to the book [8, Chapter 6]. We will only present here the required definitions.

A Markov chain ( X h ) h ≥ 0 on a state space S is a Harris chain if there are two sets A , B ⊂ S, a positive function q ( x , y ) ≥ ε > 00$]]> for x ∈ A, y ∈ B, and a probability measure ρ concentrated on B such that the following two conditions hold:

P { inf { h ≥ 0 : X h ∈ A } < ∞ } > 00$]]> for all possible starting states X 0 ∈ S;

if x ∈ A and C ⊂ B, then P { X h + 1 ∈ C | X h = x } ≥ ∫ C q ( x , y ) ρ ( d y ).

A Harris chain is called recurrent if there is a state α such that P { inf { h ≥ 1 : X h = α } < ∞ } = 1 when X 0 = α.

A recurrent Harris chain is aperiodic if the greatest common divisor of set { h ≥ 1 : P { X h = α | X 0 = α } > 0 }0\}$]]> is 1.

( X h ) h ≥ 0 is an aperiodic recurrent Harris chain.

Let us first show that ( X h ) h ≥ 0 is a Harris chain. Put A = B = { B 1 ( 0 ) }. From Theorem 3.3 it follows that P { R X 0 < ∞ } = 1. Since inf { h ≥ 0 : X h ∈ A } < ∞ } ≤ R X 0 for all possible starting states, the first condition holds. For the second part of the definition we put q ( x , y ) : = p : = P { X h + 1 = B 1 ( 0 ) | X h = B 1 ( 0 ) }. From the proof of Theorem 3.3, more precisely from the property (17), it follows that p > 00$]]>.

To show recurrence of the chain we put α = B 1 ( 0 ). Then from Theorem 3.3 we have that R α < ∞ almost surely. For the aperiodicity it is enough to note that P { X 1 = α | X 0 = α } = p > 00$]]>.  □

The Markov chain ( X h ) h ≥ 0 has a stationary distribution I ∞ and lim n → ∞ ‖ P { X h = · | X 0 = B 1 ( 0 ) } − I ∞ ( · ) ‖ T V = 0 , where ‖ · ‖ T V denotes the total variance distance.

From Proposition 3.10 we know that ( X h ) is an aperiodic recurrent Harris chain. By Theorem 6.8.5 in [8, p. 323] this chain has a stationary measure. By Theorem 6.8.8 in [8, p. 324] an aperiodic recurrent Harris chain converges to a stationary distribution in the total variation distance as (22) if R B 1 ( 0 ) is almost surely finite. The latter is secured by Theorem 3.3.  □

 Limit theorems for the length of the leftmost path

Using the results on the behavior of the chain ( X h ) we can analyze the length of the leftmost path of a vp-tree constructed from n random points. Let us introduce the following random walk S 0 : = 0 , S k : = ∑ h = 0 k − 1 G h k ≥ 1 , where, given the path of ( I h ) h ≥ 0 , ( G h ) h ≥ 0 are conditionally independent random variables such that the distribution of G h is geometric on N with parameter | I h | 2 d . This sum shows how many points are needed to have the leftmost path of size at least k, since the new node is added to it when a point x n falls into area of size | I h | which is, given ( I h ) h ≥ 0 , a Bernoulli trial.

The size (number of nodes) of the leftmost path in terms of S k can be expressed as L n = max { k ≥ 0 : S k ≤ n } .

The length of the leftmost path can be simply computed from its size as L n − 1.

For a random vp-tree the size of the leftmost path L n satisfies the following weak law of large numbers, as n → ∞, L n log n → P 1 − log τ .

To prove this theorem we need two lemmas. We note that if X ∼ Geom ( a ) and Y ∼ Geom ( b ), then X ≤ s t Y ⇔ a ≥ b .

For random variables G k ∼ Geom ( | I k | 2 d ) ( k ≥ 0) 1 k log G k → P − log τ , as k → ∞.

We compute the distribution function of 1 k log G k . Note that P 1 k log G k ≤ x = E P 1 k log G k ≤ x | I k , and further P { k − 1 log G k ≤ x | I k } = P { G k ≤ exp ( k x ) | I k } = 1 − ( 1 − | I k | / 2 d ) ⌊ exp ( k x ) ⌋ .

From Proposition 3.1 we have that τ k ≤ | I k | ≤ 2 d τ k . Thus we can bound the probability in (29) by inserting lower and upper bounds of  | I k |. Thus, 1 − ( 1 − 2 − d τ k ) ⌊ exp ( k x ) ⌋ ≤ P { k − 1 log G k ≤ x | I k } ≤ 1 − ( 1 − τ k ) ⌊ exp ( k x ) ⌋ . Both upper and lower bounds converge, as k → ∞, to 0 , if log τ + x < 0 1 , if log τ + x > 0 . 0\end{array}\right..\]]]> Hence by the standard sandwich argument P { k − 1 log G k ≤ x | I k } converges to the same values almost surely. By the dominated convergence theorem, the same holds for the unconditional probability P 1 k log G k ≤ x . This finishes the proof.  □

For a random walk S k described in (23) 1 k log S k → P − log τ as k → ∞.

We write the distribution function of S k as P { S k ≤ x } = E { P { S k ≤ x | ( I h ) 0 ≤ h < k } } and study the conditional probability under the expectation.

Since S k ≥ G k − 1 we have an upper bound P { S k ≤ x | ( I h ) 0 ≤ h < k } ≤ P { G k − 1 ≤ x | ( I h ) 0 ≤ h < k } , and the inequality holds for expectations, that is, the unconditional probability.

Let us recall that, given ( I h ) 0 ≤ h ≤ k , the random variables ( G h ) 0 ≤ h ≤ k are independent. We also have that G h ≤ s t G k ( 0 ≤ h < k) since the sequence ( | I h | ) h ≥ 0 is nonincreasing. Thus, we have the bound ∑ h = 0 k − 1 G h ≤ s t ∑ h = 0 k − 1 G k ( h ) ≤ s t k max 0 ≤ h < k G k ( h ) = k G ˆ k where ( G k ( h ) ) 0 ≤ h < k is a set of independent copies of geometrically distributed random variables with the parameter τ k / 2 d , providing G k ≤ s t G k ( 1 ) , and we put G ˆ k : = max 0 ≤ h < k G k ( h ) . Note that the inequality stays for expectations, giving that it holds for unconditional values of S k .

We compute the distribution function of G k ˆ: P 1 k log G ˆ k ≤ x = P { G ˆ k ≤ exp ( k x ) } = 1 − ( 1 − τ k / 2 d ) ⌊ exp ( k x ) ⌋ k , and therefore, as k → ∞, P 1 k log G ˆ k ≤ x → 0 , if log τ + x < 0 1 , if log τ + x ≥ 0 .

Now we combine (34) and (35) to obtain log G k − 1 ≤ s t log S k ≤ s t log k + log G ˆ k . Dividing everything by k we obtain k − 1 k log G k − 1 k − 1 ≤ s t log S k k ≤ s t log k k + log G k ˆ k . From Lemma 3.13 and (37) sending k → ∞ yields 1 k log S k → d − log τ . Convergence in probability is implied from the fact that the limit is a constant.  □

We start by computing the distribution function of L n log n in any point x > 00$]]> and x ≠ − 1 / log τ: P L n log n > x = P { L n > x log n } = P { S ⌊ x log n ⌋ ≤ n } = P { log S ⌊ x log n ⌋ ≤ log n } = P log S ⌊ x log n ⌋ log n ≤ 1 = P log S ⌊ x log n ⌋ x log n ≤ 1 x . x\right\}& =\mathbb{P}\{{L_{n}}>x\log n\}=\mathbb{P}\{{S_{\lfloor x\log n\rfloor }}\le n\}\\ {} & =\mathbb{P}\{\log {S_{\lfloor x\log n\rfloor }}\le \log n\}=\mathbb{P}\left\{\frac{\log {S_{\lfloor x\log n\rfloor }}}{\log n}\le 1\right\}\\ {} & =\mathbb{P}\left\{\frac{\log {S_{\lfloor x\log n\rfloor }}}{x\log n}\le \frac{1}{x}\right\}.\end{aligned}\]]]> By Lemma 3.14 we have P log S ⌊ x log n ⌋ x log n ≤ 1 x → 0 , 1 / x < − log τ 1 , 1 / x > − log τ , -\log \tau \end{array}\right.,\]]]> as k → ∞, and therefore P L n log n ≤ x = 1 − P L n log n > x → 1 , x > − 1 / log τ 0 , x < − 1 / log τ . x\right\}\to \left\{\begin{array}{l@{\hskip10.0pt}l}1,\hspace{1em}& x>-1/\log \tau \\ {} 0,\hspace{1em}& x<-1/\log \tau \end{array}\right..\]]]> Since the convergence in distribution to a constant implies the convergence in probability to the same constant, the theorem is proved.  □

We note that for proving Theorem 3.12 we only used that | I h | / τ h is bounded both from zero and infinity by some absolute constants. The following results demonstrate convergence of L n over subsequences. We first state and prove the result for the random walk ( S k ). Recall that I ∞ is the stationary distribution of the chain ( I h / τ h ) h ≥ 0 .

For a random walk S k defined by (23), as k → ∞, τ k S k → d G ∞ , where G ∞ is a random series ∑ j = 1 ∞ ξ j . Here ( ξ j ) j ≥ 0 are conditionally independent, given I ∞ , random variables such that ξ j ∼ Exp ( | I ∞ | 2 d τ j ).

Let us write the characteristic function of τ k S k : E e i t τ k S k = E E e i t τ k S k | ( I h ) 0 ≤ h < k = E ∏ j = 0 k − 1 | I j | / 2 d e − i t τ k − ( 1 − | I j | / 2 d ) = E ∏ j = 0 k − 1 | I j | / 2 d 1 − i t τ k + O ( τ 2 k ) − ( 1 − | I j | / 2 d ) = E ∏ j = 0 k − 1 | I j | / 2 d | I j | / 2 d − i t τ k + O ( τ 2 k ) = E ∏ j = 0 k − 1 1 1 − 2 d i t τ k − j τ j | I j | + O ( τ 2 k | I j | ) = E ∏ j = 1 k 1 1 − 2 d i t τ j τ k − j | I k − j | + O ( τ k | I k − j | ) O ( τ k ) = E ∏ j = 1 M 1 1 − 2 d i t τ j τ k − j | I k − j | + O ( τ k ) · ∏ j = M + 1 k 1 1 − 2 d i t τ j τ k − j | I k − j | + O ( τ k ) = E A k , M ( t ) · B k , M ( t ) , where 1 ≤ M < k is a fixed parameter and O ( τ k | I k − j | ) = O ( 1 ) by Proposition 3.1.

From Theorem 3.11 the convergence in total variance implies the convergence in distribution, the convergence of modules is also implied considering specifics of given rectangles. Thus, for every fixed M as k → ∞ we have A k , M ( t ) → d ∏ j = 1 M 1 1 − 2 d i t τ j / | I ∞ | . Let us show now that, for any ε > 00$]]>, lim M → ∞ lim sup k → ∞ P { | A k , M ( t ) B k , M ( t ) − A k , M ( t ) | ≥ ε } = 0 .

By Markov’s inequality P { | A k , M ( t ) B k , M ( t ) − A k , M ( t ) | ≥ ε } ≤ E | A k , M ( t ) | | B k , M ( t ) − 1 | ε .

At first we want to show that B k , M ( t ) converges to 1 by separately showing that module and argument of the complex value converge. We have | B k , M ( t ) | 2 = ∏ j = M + 1 k 1 ( 1 + O ( τ k ) ) 2 + ( 2 d t τ j τ k − j | I k − j | + O ( τ k ) ) 2 , log | B k , M ( t ) | 2 = − ∑ j = M + 1 k log ( 1 + O ( τ k ) ) 2 + 2 d t τ j τ k − j | I k − j | + O ( τ k ) 2 = − ∑ j = M + 1 k log 1 + O ( τ k ) + 2 2 d t 2 τ 2 j τ k − j | I k − j | 2 + O ( τ k ) = − ∑ j = M + 1 k 2 2 d t 2 τ 2 j τ k − j | I k − j | 2 + O ( τ k ) + O ( τ 4 j ) + O ( τ 2 j + k ) + O ( τ 2 k ) = − ∑ j = M + 1 k O ( τ 2 j ) + O ( τ k ) . The expansion for logarithm holds starting with some large enough M. We also used Proposition 3.1 which shows that τ k − j / | I k − j | is bounded by nonrandom constants, which also do not dependent on k − j. We note that for a fixed t, the constants in the remainders O ( τ 2 j ) and O ( τ k ) are uniform, that is, do not depend on j, k. Thus, we can write lim M → ∞ lim sup k → ∞ ∑ j = M + 1 k O ( τ 2 j ) + O ( τ k ) = 0 a.s.

For the argument we write arg B k , M ( t ) = − ∑ j = M + 1 k Arg 1 − 2 d i t τ j τ k − j | I k − j | + O ( τ k ) = ∑ j = M + 1 k 2 d t τ j τ k − j | I k − j | 1 + 2 2 d t 2 τ 2 j τ k − j | I k − j | 2 + O ( τ 3 j ) + O ( τ k ) = ∑ j = M + 1 k O ( τ j ) + O ( τ k ) . The expansion for the principal argument holds starting from some large enough M. Arguing as before we can write lim M → ∞ lim sup k → ∞ arg B k , M ( t ) = 0 a.s.

We also showed in process that starting from some large enough k and M the quantity | B k , M ( t ) | is bounded by a nonrandom constant B ‾ > 00$]]> on every stochastic path. Since | A k , M ( t ) B k , M ( t ) | = 1, then | A k , M ( t ) | is also bounded by some constant A ‾ > 00$]]>. Thus, we can write E | A k , M ( t ) | | B k , M ( t ) − 1 | ε ≤ A ‾ E | B k , M ( t ) − 1 | ε . We already showed that lim M → ∞ lim sup k → ∞ | B k , M ( t ) − 1 | = 0 a.s. Since | B k , M ( t ) − 1 | ≤ 1 + B ‾, then by the dominated convergence theorem lim M → ∞ lim k → ∞ E | B k , M ( t ) − 1 | = 0 . Combining pieces together we obtain (47).

By Theorem 3.2 in [4, p. 28] we have that as k → ∞ e i t τ k S k → d lim M → ∞ ∏ j = 1 M 1 1 − 2 d i t τ j / | I ∞ | = ∏ j = 1 ∞ 1 1 − 2 d i t τ j / | I ∞ | .

Elements of the sequence ( e i t τ k S k ) k ≥ 0 are uniformly integrable as characteristic functions, so expectations also converge as k → ∞, E e i t τ k S k → E ∏ j = 1 ∞ 1 1 − 2 d i t τ j / | I ∞ | , and the limiting value here is a characteristic function of G ∞ which finishes the proof.  □

For any fixed T > 00$]]>, L ⌊ T τ − n ⌋ − n → d L ∞ ( T ) as n → ∞ and the distribution function of L ∞ ( T ) is given by P { L ∞ ( T ) ≤ m } = 1 − P { G ∞ ≤ T τ m } for any m ∈ Z with G ∞ defined in Lemma 3.15.

Since L ⌊ T τ − n ⌋ − n takes values only on Z, we study the distribution function only over integer values. For fixed T > 00$]]> and m ∈ Z we have P { L ⌊ T τ − n ⌋ − n > m } = P { L ⌊ T τ − n ⌋ > n + m } = P { S n + m ≤ ⌊ T τ − n ⌋ } = P { τ n + m S n + m ≤ τ n + m ⌊ T τ − n ⌋ } . m\}& =\mathbb{P}\{{L_{\lfloor T{\tau ^{-n}}\rfloor }}>n+m\}=\mathbb{P}\{{S_{n+m}}\le \lfloor T{\tau ^{-n}}\rfloor \}\\ {} & =\mathbb{P}\{{\tau ^{n+m}}{S_{n+m}}\le {\tau ^{n+m}}\lfloor T{\tau ^{-n}}\rfloor \}.\end{aligned}\]]]> From Lemma 3.15 and the fact that τ n ⌊ T τ − n ⌋ → T as n → ∞ we obtain lim n → ∞ P { τ n + m S n + m ≤ τ n + m ⌊ T τ − n ⌋ } = P { G ∞ ≤ T τ m } , which finishes the proof.  □

 One-dimensional convergence

In this section we analyze the random recursive equation (5). Sending h → ∞ in (5) we formally obtain the stochastic fixed-point equation for the limit X ∞ of X h ( i ) : X ∞ = d min { τ − 1 u X ∞ , 1 } + min { τ − 1 ( 1 − u ) X ∞ , 1 } , where u is a uniformly distributed random variable on [ 0 , 1 ]. Let us show, using the contraction method, that X h ( i ) converges to X ∞ , as h → ∞.

The function f ( X , u ) = Law min u X τ , 1 + min ( 1 − u ) X τ , 1 is a strict contraction in the space of probability measures on [ 1 , 2 ] endowed with the ℓ 1 -minimal metric, where u is a uniformly distributed random variable on [ 0 , 1 ] independent of a random variable X taking values in [ 1 , 2 ].

The ℓ 1 -minimal metric between two random variables X and Y is given by ℓ 1 ( X , Y ) = inf E | X ˆ − Y ˆ | , where the infimum is taken over all pairs of random variables ( X ˆ , Y ˆ ) such that X ˆ ∼ X and Y ˆ ∼ Y.

Similarly to the proof of Proposition 3.1 it can be checked that if X takes values in [ 1 , 2 ], the same holds also for f ( X , u ).

We prove the contraction property in two steps.

Step 1. We compute the ℓ 1 -minimal distance between f ( x , u 1 ) and f ( y , u 2 ) for fixed nonrandom numbers x , y ∈ [ 1 , 2 ]. We have ℓ 1 ( f ( x , u ) , f ( y , u ) ) = inf E | f ( x , u 1 ) − f ( x , u 2 ) | .

Since the infimum is taken over all possible dependencies between u 1 and u 2 , we may pick u 1 = u 2 = u. Then ℓ 1 ( f ( x , u 1 ) , f ( y , u 2 ) ) ≤ ∫ [ 0 , 1 ] | f ( x , u ) − f ( y , u ) | d u .

Let us assume for the time being that there is α ∈ ( 0 , 1 ) such that ∫ [ 0 , 1 ] | f ( x , u ) − f ( y , u ) | d u ≤ α | x − y | . Step 2. We compute the ℓ 1 -minimal distance between f ( X , u 1 ) and f ( Y , u 2 ). Combining the above estimates, we obtain ℓ 1 ( f ( X , u 1 ) , f ( Y , u 2 ) ) ≤ α E | X ˆ − Y ˆ | , for arbitrary pair ( X ˆ , Y ˆ ) such that X ˆ ∼ X and Y ˆ ∼ Y. Passing to the infimum over all such pairs, we obtain ℓ 1 ( f ( X , u 1 ) , f ( Y , u 2 ) ) ≤ α ℓ 1 ( X , Y ) for some constant α ∈ ( 0 , 1 ), which is the definition of contraction.

It remains to prove (67). At first we divide f into sum of two functions. f ( x , u ) = f 1 ( x , u ) + f 2 ( x , u ) , where f 1 ( x , u ) = min u X τ , 1 = u x τ , u < τ x 1 , u ≥ τ x and f 2 ( x , u ) = min { ( 1 − u ) X τ , 1 }.

We compute the following integral under the condition x ≤ y: ∫ 0 1 | f 1 ( x , u ) − f 1 ( y , u ) | d u = ∫ 0 τ / y u y τ − u x τ d u + ∫ τ / y τ / x 1 − u x τ d u + ∫ τ / x 1 ( 1 − 1 ) d u = ∫ 0 τ / y u τ ( y − x ) d u + ∫ τ / y τ / x d u − ∫ τ / y τ / x x τ d u = y − x τ u 2 2 | 0 τ / y + τ x − τ y − x τ u 2 2 | τ / y τ / x = y − x 2 τ τ 2 y 2 + τ x − τ y − x 2 τ τ 2 x 2 − τ 2 y 2 = τ ( y − x ) 2 y 2 + τ x − τ y − τ 2 x + τ x 2 y 2 = τ x ( y − x ) + 2 τ y 2 − 2 τ x y − τ y 2 + τ x 2 2 x y 2 = − τ x y + τ y 2 2 x y = τ 2 y − x x y .

Similarly if y ≤ x we obtain that ∫ 0 1 | f 1 ( x , u ) − f 1 ( y , u ) | d u ≤ τ 2 x − y x y , which results in ∫ 0 1 | f 1 ( x , u ) − f 1 ( y , u ) | d u ≤ τ 2 | x − y | x y .

Now we estimate the same integral for f 2 , where f 2 ( x , u ) = 1 , 1 − u ≥ τ x ( 1 − u ) x τ , 1 − u < τ x .

In the integral we make a substitution v = 1 − u: ∫ 0 1 | f 2 ( x , u ) − f 2 ( y , u ) | d u = ∫ 0 1 | f 2 ( x , 1 − v ) − f 2 ( y , 1 − v ) | d v , where we instantly obtain the same estimation as (74), since f 2 ( x , 1 − v ) = f 1 ( x , v ).

Finally, ∫ [ 0 , 1 ] | f ( x , u ) − f ( y , u ) | d u ≤ ∫ 0 1 | f 1 ( x , u ) − f 1 ( y , u ) | d u + ∫ 0 1 | f 2 ( x , u ) − f 2 ( y , u ) | d u ≤ τ 2 | x − y | x y + τ 2 | x − y | x y = τ | x − y | x y ≤ τ | x − y | , which proves (67) with α = τ.  □

The stochastic fixed-point equation (62) has the unique solution X ∞ in the space of probability measures on [ 1 , 2 ] and X h ( i ) → d X ∞ , as h → ∞, for every fixed i = 1 , … , d.

We obtained the same result as in the previous section without resort to geometric interpretation but with explicit usage of the distribution of sequence of points x 1 , x 2 , … . It also allowed us to deduce the stochastic fixed-point equation for X ∞ . Recall that I ∞ is a rectangle with edges being parallel to coordinate axes, its sizes in all dimensions can be given by ( X ∞ ( 1 ) , … , X ∞ ( d ) ), where ( X ∞ ( i ) ) 1 ≤ i ≤ d are independent copies of X ∞ .

It turns out that the distribution of X ∞ can be found explicitly using the stochastic fixed-point equation (62) by directly computing its distribution function F ( t ) = P { X ∞ < t }. The solution depends heavily on the parameter τ.

We start with a rather simple and special example τ ≤ 1 / 2.

For t ∈ [ 1 , 2 ] we write P { X ∞ < t } = P min u X ∞ τ , 1 + min ( 1 − u ) X ∞ τ , 1 < t = P 1 + 1 < t , u X ∞ τ ≥ 1 , ( 1 − u ) X ∞ τ ≥ 1 + P u X ∞ τ + ( 1 − u ) X ∞ τ < t , u X ∞ τ < 1 , ( 1 − u ) X ∞ τ < 1 + P u X ∞ τ + 1 < t , u X ∞ τ < 1 , ( 1 − u ) X ∞ τ ≥ 1 + P 1 + ( 1 − u ) X ∞ τ < t , u X ∞ τ ≥ 1 , ( 1 − u ) X ∞ τ < 1 . The first term is obviously 0, since we assume t ≤ 2. The second term is also 0 since events { u X ∞ τ < 1 } and { ( 1 − u ) X ∞ τ < 1 } cannot occur at the same time for τ ≤ 1 / 2. And the last two terms are symmetrical. P { X ∞ < t } = 2 P u X ∞ τ + 1 < t , u X ∞ τ < 1 , ( 1 − u ) X ∞ τ ≥ 1 = 2 P u X ∞ τ + 1 < t , ( 1 − u ) X ∞ τ ≥ 1 = 2 P u < τ ( t − 1 ) X ∞ , u ≤ X ∞ − τ X ∞ = 2 P u < τ ( t − 1 ) X ∞ . Here in the second equality we used that the event { u X ∞ τ + 1 < t } implies the event { u X ∞ τ < 1 }. And in the last equality we used that the event { u < τ ( t − 1 ) X ∞ } includes the event { u ≤ X ∞ − τ X ∞ } since τ t < 1 ≤ X ∞ . Finally, P { X ∞ < t } = 2 P u < τ ( t − 1 ) X ∞ = 2 E P τ ( t − 1 ) X ∞ > u | X ∞ = 2 E τ ( t − 1 ) X ∞ = 2 τ E 1 X ∞ ( t − 1 ) . u\right\}\big|{X_{\infty }}\right)\\ {} & =2\mathbb{E}\left(\frac{\tau (t-1)}{{X_{\infty }}}\right)=2\tau \mathbb{E}\frac{1}{{X_{\infty }}}(t-1).\end{aligned}\]]]>

And we also have a special state X ∞ = 2: P { X ∞ = 2 } = P 1 + 1 = 2 , u X ∞ τ ≥ 1 , ( 1 − u ) X ∞ τ ≥ 1 = P u ≥ τ X ∞ , u ≤ 1 − τ X ∞ = 1 − 2 τ E 1 X ∞ .

From (80) and (81) we see that X ∞ is a combination of the uniform distribution on [ 1 , 2 ) and an atom at point 2. We only need to compute a constant E 1 X ∞ . E 1 X ∞ = 1 2 P { X ∞ = 2 } + ∫ 1 2 1 t d P { X ∞ < t } = 1 2 1 − 2 τ E 1 X ∞ + ∫ 1 2 2 τ E 1 X ∞ t d t = 1 2 1 − 2 τ E 1 X ∞ + 2 τ E 1 X ∞ ( log 2 − log 1 ) . We solve (82) for an unknown E 1 X ∞ and obtain that E 1 X ∞ = 1 2 τ ( 1 − 2 log 2 + 1 / τ ) .

On Figure 1 the reader can see simultaneous plots of just obtained theoretical values of F ( t ) and statistical values. We refer to statistical values as an empirical cumulative distribution function obtained from values of X h ( i ) taken in 10000 consecutive iterations of the process (5).

Plot of theoretical and statistical values of the distribution function F ( t ) of X ∞ with τ = 0.4

From now on we assume that τ > 1 / 21/2$]]>. We begin as in previous case but write all possibilities for minimums separately.

The situation X ∞ = 2 is possible only when both minimums are 1. P { X ∞ = 2 } = P 1 + 1 = 2 , 1 ≤ u X ∞ τ , 1 ≤ ( 1 − u ) X ∞ τ = P τ X ∞ ≤ u ≤ X ∞ − τ X ∞ , X ∞ ≥ 2 τ = ∫ [ 2 τ , 2 ] 1 − τ x d F ( x ) − ∫ [ 2 τ , 2 ] τ x d F ( x ) = 1 − F ( 2 τ ) − 2 τ ∫ [ 2 τ , 2 ] 1 x d F ( x ) = 1 − F ( 2 τ ) − 2 τ E 1 X ∞ − ∫ [ 1 , 2 τ ) 1 x d F ( x ) .

When X ∞ < 2 there are two possibilities that only one of the minimums in (62) is 1, and both of these situations are symmetrical, so we compute only one of the probabilities: P u X ∞ τ + 1 < t , u X ∞ τ < 1 , ( 1 − u ) X ∞ τ ≥ 1 = P u < τ ( t − 1 ) X ∞ , X ∞ ≥ τ t + P u ≤ X ∞ − τ X ∞ , X ∞ < τ t = ∫ [ τ t , 2 ] τ ( t − 1 ) x d F ( x ) + ∫ [ 1 , τ t ] 1 − τ x d F ( x ) = τ ( t − 1 ) E 1 X ∞ − ∫ [ 1 , τ t ) 1 x d F ( x ) + F ( τ t ) − τ ∫ [ 1 , τ t ) 1 x d F ( x ) .

And the last possibility of X ∞ < 2 is when both minimums are less than 1. P u X ∞ τ + ( 1 − u ) X ∞ τ < t , u X ∞ τ < 1 , ( 1 − u ) X ∞ τ < 1 = P X ∞ − τ X ∞ < u < τ X ∞ , x < τ t = ∫ [ 1 , τ t ] τ x d F ( x ) − ∫ [ 1 , τ t ] ( 1 − τ x ) d F ( x ) = 2 τ ∫ [ 1 , τ t ] 1 x d F ( x ) − F ( τ t ) .

We combine (85) and (86) and get the following for t ∈ [ 1 , 2 ]: P { X ∞ < t } = P u X ∞ τ + ( 1 − u ) X ∞ τ < t , u X ∞ τ < 1 , ( 1 − u ) X ∞ τ < 1 + 2 P u X ∞ τ + 1 < t , u X ∞ τ < 1 , ( 1 − u ) X ∞ τ ≥ 1 = F ( τ t ) + 2 τ ( t − 1 ) E 1 X ∞ − ∫ [ 1 , τ t ) 1 x d F ( x ) .

Now we will show how to retrieve exact values for probability (87). On step 1 we consider that t ∈ [ 1 , 1 / τ ], then τ t < 1 and from (87) one gets: P { X ∞ < t } = 0 + 2 τ ( t − 1 ) E 1 X ∞ − 0 = 2 τ ( t − 1 ) E 1 X ∞ . We also compute the derivative d F ( t ) = 2 τ E 1 X ∞ d t .

We repeat the procedure by computing probabilities and the derivatives for t ∈ [ 1 / τ , 1 / τ 2 ] and so on following intervals by using results from previous intervals. More generally, let us compute an interval on step k when t ∈ [ 1 / τ k − 1 , 1 / τ k ].

We have τ t ∈ [ 1 / τ k − 2 , 1 / τ k − 1 ] which means that F ( τ t ) is a value from previous interval and we can use it. We also have an integral part in (87): ∫ [ 1 , τ t ) 1 x d F ( x ) = ∫ 1 1 / τ 1 x d F ( x ) + ∫ 1 / τ 1 / τ 2 1 x d F ( x ) + ⋯ + ∫ 1 / τ k − 2 τ t 1 x d F ( x ) where the integrals are taken by using computed derivatives on first k − 1 intervals respectively.

At some k we have 1 / τ k > 22$]]> so we stop computing intervals. We have only one unknown variable E 1 X ∞ . We compute this value directly by using computed probabilities and solve an equation for it.

Let us compute X ∞ when 1 / τ < 2 ≤ 1 / τ 2 ( k = 2). We also have that 2 τ ≤ 1 / τ.

When t ≤ 1 / τ, we have P { X ∞ < t } = 2 τ ( t − 1 ) E 1 X ∞ , d F ( t ) = 2 τ E 1 X ∞ d t .

When t ≥ 1 / τ, ∫ [ 1 , τ t ] 1 x d F ( x ) = ∫ 1 τ t 2 τ E 1 X ∞ x d x = 2 τ E 1 X ∞ log ( τ t ) .

After plugging (91) and (92) into (87) we obtain P { X ∞ < t } = F ( τ t ) + 2 τ ( t − 1 ) E 1 X ∞ − 2 τ E 1 X ∞ log ( τ t ) = 2 τ ( τ t − 1 ) E 1 X ∞ + 2 τ ( t − 1 ) E 1 X ∞ − 4 τ 2 ( t − 1 ) log ( τ t ) = 2 τ E 1 X ∞ ( t + τ t − 2 τ t log ( τ t ) + 2 τ log ( τ t ) − 2 ) , and the derivative is d F ( t ) = 2 τ E 1 X ∞ 1 + τ − 2 τ ( 1 + log ( τ t ) ) + 2 τ 1 t .

Finally, we also return to a special case value X ∞ = 2 which was computed at the beginning in (84): P { X ∞ = 2 } = 1 − F ( 2 τ ) − 2 τ E 1 X ∞ − ∫ [ 1 , 2 τ ) 1 x d F ( x ) = 1 − P { X ∞ < 2 } = 1 − 2 τ E 1 X ∞ ( 2 + 2 τ − 4 τ log ( 2 τ ) + 2 τ log ( 2 τ ) − 2 ) = 1 − 4 τ 2 E 1 X ∞ ( 1 − log ( 2 τ ) ) .

We only need to compute the constant E 1 X ∞ : E 1 X ∞ = 1 2 1 − 4 τ 2 E 1 X ∞ ( 1 − log ( 2 τ ) ) + ∫ 1 1 / τ 2 τ E 1 X ∞ x d x + ∫ 1 / τ 2 2 τ E 1 X ∞ ( 1 + τ − 2 τ ( 1 + log ( τ t ) ) + 2 τ 1 t ) x d x = 1 2 1 − 4 τ 2 E 1 X ∞ ( 1 − log ( 2 τ ) ) + ∫ 1 1 / τ 2 τ E 1 X ∞ x d x + 2 τ E 1 X ∞ ∫ 1 / τ 2 1 + τ − 2 τ x d x + ∫ 1 / τ 2 − 2 τ log τ x x d x + ∫ 1 / τ 2 2 τ x 2 d x = 1 2 1 − 4 τ 2 E 1 X ∞ ( 1 − log ( 2 τ ) ) + ∫ 1 1 / τ 2 τ E 1 X ∞ x d x + 2 τ E 1 X ∞ ∗ ∗ ( 1 − τ ) ( log 2 − log ( 1 / τ ) ) − τ ( log 2 ( 2 τ ) − log 2 ( τ / τ ) ) − 2 τ 1 2 − τ = 1 2 1 − 4 τ 2 E 1 X ∞ ( 1 − log ( 2 τ ) ) − 2 τ E 1 X ∞ log ( τ ) + 2 τ E 1 X ∞ ( 1 − τ ) log ( 2 τ ) − τ log 2 ( 2 τ ) + 2 τ τ − 1 2 . By solving this equation for an unknown E 1 X ∞ we obtain: E 1 X ∞ = 1 2 ( 1 − 4 τ 3 + 4 τ 2 + 2 τ 2 log 2 ( 2 τ ) + 2 τ log ( τ ) − 2 τ log ( 2 τ ) ) .

Plot of theoretical and statistical values of the distribution function F ( t ) of X ∞ with τ = 0.7

Plot of statistical values of the distribution function F ( t ) of X ∞ with τ = 0.9

As the end of the example, Figure 2 shows plots of theoretical and statistical values of F ( t ) with τ lying in the studied range.

Finally, without computing theoretical values of the distribution function, we want to show how it further evolves with increasing τ by showing only its statistical values on Figure 3 with τ = 0.9.

 Acknowledgments

I would like to thank my supervisor, Prof. Alexander Marynych, for his dedicated guidance and support throughout this research. I am grateful for his prompt and friendly responses to my questions and queries, as well as for his genuine care about my work. I also thank the anonymous referee for useful suggestions which improved the presentation of my results.

 References Ambrus, G., Kevei, P., Vigh, V.: The diminishing segment process. Stat. Probab. Lett. 82(1), 191–195 (2012). MR2863042. https://doi.org/10.1016/j.spl.2011.09.016 Bavaud, F.: Adjoint transform, overconvexity and sets of constant width. Trans. Am. Math. Soc. 333(1), 315–324 (1992). MR1132431. https://doi.org/10.2307/2154111 Bentley, J.: Multidimensional binary search trees used for associative searching. Commun. ACM 18(9), 509–517 (1975) Billingsley, P.: Convergence of Probability Measures, Second Edition. John Wiley & Sons, Inc., New York (1999). MR1700749. https://doi.org/10.1002/9780470316962 Cover, T.: Estimation by the nearest neighbor rule. IEEE Trans. Inf. Theory 14(1), 50–55 (1968) Cover, T., Hart, P.: Nearest neighbor pattern classification. IEEE Trans. Inf. Theory 13(1), 21–27 (1967) Devroye, L.: The uniform convergence of nearest neighbor regression function estimators and their applications in optimization. IEEE Trans. Inf. Theory 24(2), 142–151 (1978). MR0518942. https://doi.org/10.1109/tit.1978.1055865 Durrett, R.: Probability Theory and Examples, Fourth Edition. Cambridge University Press, New York (2010). MR2722836. https://doi.org/10.1017/CBO9780511779398 Fu, A., Chan, P., Cheung, Y., Moon, Y.: Dynamic vp-tree indexing for n-nearest neighbor search given pair-wise distances. VLDB J. 9, 154–173 (2000) Kevei, P., Vigh, V.: On the diminishing process of Balint Toth. Trans. Am. Math. Soc. 368(12), 8823–8848 (2016). MR3551590. https://doi.org/10.1090/tran/6620 Kumar, N., Zhang, L., Nayar, S.: What is a good nearest neighbors algorithm for finding similar patches in images. In: Lecture Notes in Computer Science, Vol 5303, pp. 364–378. Springer, Berlin (2008) Moore, A.: An introductory tutorial on kd-trees. Technical Report Technical Report No. 209, Computer Laboratory, University of Cambridge, Carnegie Mellon University, Pittsburgh, PA (1991) Narasimhulu, Y., Suthar, A., Pasunuri, R., Venkaiah, V.: Ckd-tree: An improved kd-tree construction algorithm. In: International Semantic Intelligence Conference 2021, pp. 211–218 (2021) Omohundro, S.: Five balltree construction algorithms. Technical Report Technical Report 89-063 (1989) Papernot, N., McDaniel, P.: Deep k-nearest neighbors: Towards confident, interpretable and robust deep learning. CoRR 1803.04765 (2018) Shishibori, M., Lee, S., Kita, K.: An improved method to select candidates on metric index vp-tree. In: Proceedings of the International Conference on Knowledge Discovery and Information Retrieval, vol. 1, pp. 306–311 (2011) Yianilos, P.: Data structures and algorithms for nearest neighbor search in general metric spaces. In: Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 311–321 (1993). MR1213243