Introduction
In a graph G = ( V , E ) G = (V, E) G = ( V , E ) , a set of vertices I ⊆ V I \subseteq V I ⊆ V is independent if no two vertices in I I I are adjacent. A maximum independent set is an independent set of largest possible cardinality, while a maximal independent set is one that is inclusion-wise maximal. Finding a maximum independent set is computationally intractable in general [16 ] , whereas a maximal independent set can be computed by a simple greedy algorithm in linear time. Throughout the paper, MIS stands for maximal independent set.
In 2008, Nguyen and Onak [23 ] initiated the study of determining, in sublinear time, whether a queried vertex u ∈ V u \in V u ∈ V belongs to the MIS produced by the following random-order greedy process:1
For each u ∈ V u \in V u ∈ V , assign rank r ( u ) r(u) r ( u ) chosen uniformly at random from [ 0 , 1 ] [0, 1] [ 0 , 1 ] ;
Greedily augment independent set I I I by iterating over V V V from smallest to largest vertex with respect to their ranks.
We refer to this random-order greedy process as randomized greedy MIS (RGMIS). Nguyen and Onak then studied the following recursive simulation of RGMIS: to determine whether u u u belongs to the MIS, one recursively evaluates every neighbor w w w of u u u with r ( w ) < r ( u ) r(w) < r(u) r ( w ) < r ( u ) . Then u u u belongs to the MIS if and only if none of these neighbors do. Letting Δ \Delta Δ denote the maximum degree of the input graph, the authors proved that the expected number of recursive calls made by this procedure is e O ( Δ ) e^{O(\Delta)} e O ( Δ ) . In fact, this upper bound is tight even on trees.2 The authors also observed that a natural search-pruning heuristic may asymptotically improve this recursive process: if, for some neighbor w w w of u u u with r ( w ) < r ( u ) r(w) < r(u) r ( w ) < r ( u ) , the recursive call returns that w w w belongs to the MIS, then it immediately follows that u u u does not belong to the MIS, and hence no other neighbor of u u u needs to be explored. We refer to RGMIS implemented with this heuristic as pruned RGMIS (see Algorithm 1). The authors conjectured that pruned RGMIS is significantly faster than the unpruned one, and left that direction for future research.
A year later, Yoshida, Yamamoto, and Ito [YYI09] proved that this pruning step drastically improves the average-case complexity of RGMIS. More precisely, they showed that when the query vertex is chosen uniformly at random, pruned RGMIS makes only ∣ E ( G ) ∣ / ∣ V ( G ) ∣ |E(G)|/|V(G)| ∣ E ( G ) ∣/∣ V ( G ) ∣ recursive calls in expectation. In particular, on trees, the expected number of recursive calls made by pruned RGMIS from a uniformly random query vertex is less than 1. Very recently, Dalirrooyfard, Makarychev, and Mitrović [10 ] gave a considerably simpler analysis of the result of [YYI09].
However, works [YYI09, DMM26] leave open whether pruned RGMIS may still require exp ( Θ ( Δ ) ) \exp(\Theta(\Delta)) exp ( Θ ( Δ )) recursive calls from a worst-case vertex. This raises the question of whether, at least on trees, the average-case and worst-case complexities of pruned RGMIS coincide. Karger, Mitrović, Norouzi-Fard, and Tardos [18 ] ruled this out by showing that the two can differ substantially. More formally, they show that for every constant ε > 0 \varepsilon> 0 ε > 0 , there exist a tree and a vertex u u u in that tree such that pruned RGMIS invoked on u u u makes Ω ε ( Δ 2 − ε ) \Omega_{\varepsilon}(\Delta^{2-\varepsilon}) Ω ε ( Δ 2 − ε ) recursive calls in expectation.3 Thus, even on trees, pruned RGMIS exhibits a substantial gap between average-case and worst-case behavior: the average complexity is constant, while the worst-case complexity is at least polynomial in Δ \Delta Δ . This already shows that the tree case captures a nontrivial aspect of the problem.
Although Ghaffari [15 ] gives a local computation algorithm for MIS with query complexity poly ( Δ ) \operatorname{poly}(\Delta) poly ( Δ ) in expectation4 , this does not address the complexity of the specific recursive process induced by RGMIS. Studying this process is natural in its own right: RGMIS is an especially simple and canonical randomized greedy procedure, and related versions of it have been studied in several areas beyond local computation. For instance, random-order greedy processes of this kind long predate their local-computation applications: closely related versions were studied already in Flory’s 1939 work in chemistry [13 ] , and later in the random sequential adsorption literature [12 ] . It has also served as a useful primitive in a number of later algorithmic works.
Since [23 ] , techniques for analyzing RGMIS and related randomized greedy processes have found applications in local and sublinear-time algorithms for vertex cover, matching, set cover, and minimum dominating set [23 YYI09, 24 , 4 ] . Related ideas have also appeared in subsequent work on dynamic and sublinear-time matching, as well as in several other algorithmic settings [7 , 5 MRT25, MRTV25, 22 , 26 , 3 , 1 , 9 ] . However, these developments do not seem to yield progress on the expected query complexity of RGMIS from a worst-case queried vertex. A closely analogous difficulty was noted explicitly by Behnezhad [4 ] in the context of randomized greedy maximal matching, where they wrote that “analyzing the expected query-complexity for a given edge seems to be challenging. ” In the RGMIS setting, the analogous question concerns a worst-case queried vertex.
The question we study goes back to Nguyen and Onak [23 ] , who conjectured in their concluding remarks that their exponential analysis might be far from tight, writing that the complexity may grow “quasi-polynomially, not exponentially, in Δ \Delta Δ .” Despite subsequent progress, this question remains open even on trees.
What is the expected complexity of pruned RGMIS from a worst-case vertex in a tree?
Our result
In this paper we focus on the pruned RGMIS, and hence refer to it as RGMIS for simplicity. We say that a vertex x x x queries a neighbor y y y if the recursive execution of RGMIS at x x x invokes RGMIS on y y y . Given an input tree and a query vertex v v v , we root the tree at v v v . Thus, every recursive call proceeds from a vertex to one of its children, and every query path is simply a path of successive queries starting at v v v .
The run-time of RGMIS is within O ( Δ ) O(\Delta) O ( Δ ) factor of the size of the recursion tree produced by the RGMIS algorithm (see Algorithm 1). The Δ \Delta Δ factor comes from each recursive call having to inspect the adjacency list of a new vertex in the tree and initiating subsequent recursive calls. The run-time bound is also a bound on the portion of the input tree that is inspected by the algorithm. Thus, up to polynomial factor, it suffices to bound the size of the recursion tree, which we henceforth call the query tree , produced by the RGMIS algorithm.
We prove that the expected size of the RGMIS query tree over a worst-case starting vertex (see Definition 2.1 ) obtained from the RGMIS algorithm is polynomial in Δ \Delta Δ on trees.
Theorem 1.1. There exists an absolute constant C > 0 C > 0 C > 0 such that for every integer Δ > 2 \Delta> 2 Δ > 2 , every tree T T T with maximum degree Δ \Delta Δ and every vertex u u u in T T T , the expected size of the query tree Q ( T , u , r ) Q(T,u,r) Q ( T , u , r ) from u u u over uniformly assigned random ranks r r r is at most Δ C \Delta^{C} Δ C , i.e.,
E r [ ∣ Q ( T , u , r ) ∣ ] ≤ Δ C . \mathbb{E}_{r}\left[|Q(T,u,r)|\right] \le\Delta^{C}. E r [ ∣ Q ( T , u , r ) ∣ ] ≤ Δ C .
Other related work
A closely related body of work arises in the framework of local computation algorithms (LCAs), where one seeks to answer local queries while remaining consistent with a single global solution. The LCA model was introduced by Rubinfeld, Tamir, Vardi, and Xie [25 ] and further developed by Alon, Rubinfeld, Vardi, and Xie [2 ] . Maximal independent set has been one of the central benchmark problems in this area. In particular, beyond the recursive simulation of randomized greedy orders considered in the present line of work, subsequent papers obtained improved LCAs for MIS and related problems, including deterministic and stateless algorithms [11 ] , algorithms for non-constant-degree graphs [20 ] , and, very recently, an LCA for MIS with query complexity poly ( Δ ) log n \operatorname{poly}(\Delta) \log n poly ( Δ ) log n [15 ] . More broadly, many other problems have been studied in the centralized local model as well; we refer the reader to the survey of Levi and Medina [19 ] for a general overview.
There is also a separate probabilistic line of work that studies the random greedy independent set via branching-process and local-limit methods, especially on random trees and sparse random graphs. This includes analyses on regular graphs of large girth [14 ] , random graphs with prescribed degree sequences [6 ] , and more recent frameworks that explicitly involve Galton–Watson trees or related branching objects [17 , 8 ] . These works are close in spirit, since they also analyze the random greedy MIS process, but their focus is typically on the size or density of the resulting independent set in random graph models, or on the behavior seen from a typical root, rather than on the worst-case query complexity from a fixed vertex in an arbitrary tree. For this reason, it is not clear that their techniques directly apply to the setting studied here.
Overview of our approach
As already discussed, without pruning, running unpruned RGMIS from the root of a Δ \Delta Δ -ary tree makes Θ ( e Δ ) \Theta(e^{\Delta}) Θ ( e Δ ) queries in expectation. Hence, to show that pruned RGMIS has significantly lower complexity, the main task is to quantify the effect of pruning. To illustrate our starting idea, consider the following thought experiment.
Suppose we want to count the number of recursive calls made at vertices with ranks in ( 1 / 2 , 1 ) (1/2,1) ( 1/2 , 1 ) , and ignore all work performed at vertices of rank below 1 / 2 1/2 1/2 . Moreover, we count a recursive call from u u u to v v v only if v v v itself queries some vertex w w w , and the ranks of u u u , v v v , and w w w all lie in ( 1 / 2 , 1 ) (1/2,1) ( 1/2 , 1 ) . How many vertices with ranks in ( 1 / 2 , 1 ) (1/2,1) ( 1/2 , 1 ) are then queried?
Consider a vertex u u u with rank r ( u ) ∈ ( 1 / 2 , 1 ) r(u) \in(1/2,1) r ( u ) ∈ ( 1/2 , 1 ) that is reached by the recursion. At that point, among all randomness in the subtree rooted at u u u , only the rank r ( u ) r(u) r ( u ) has been revealed. Suppose that u u u queries a child v v v , which in turn queries some vertex w w w with r ( w ) ∈ ( 1 / 2 , 1 ) r(w) \in(1/2,1) r ( w ) ∈ ( 1/2 , 1 ) . For this to happen, it must be the case that all children w ′ w' w ′ of v v v with r ( w ′ ) < 1 / 2 r(w') < 1/2 r ( w ′ ) < 1/2 are not in the MIS. Otherwise, the RGMIS procedure would stop exploring the children of v v v upon reaching such a vertex w ′ w' w ′ , and as a result would never query w w w .
We thus consider the set of promising vertices v v v , defined as follows: let A A A be the set of children v v v of u u u such that no child w w w of v v v with r ( w ) < 1 / 2 r(w) < 1/2 r ( w ) < 1/2 belongs to the MIS. In expectation, how many vertices in A A A with ranks at least 1 / 2 1/2 1/2 are queried by u u u ? To answer this, observe that membership in A A A is determined by the subtree below each v ∈ A v \in A v ∈ A , and therefore does not reveal any information about r ( v ) r(v) r ( v ) itself. Hence, conditioned on A A A , each rank r ( v ) r(v) r ( v ) for v ∈ A v \in A v ∈ A remains uniformly distributed in [ 0 , 1 ] [0,1] [ 0 , 1 ] . A naive estimate therefore gives only that the expected number of vertices in A A A with rank at least 1 / 2 1/2 1/2 queried by u u u is at most ∣ A ∣ / 2 |A|/2 ∣ A ∣/2 . However, pruning gives a much stronger bound. Indeed, suppose that some v ∈ A v \in A v ∈ A satisfies r ( v ) ≤ 1 / 2 r(v) \le1/2 r ( v ) ≤ 1/2 . Then r ( v ) < r ( u ) r(v) < r(u) r ( v ) < r ( u ) , so u u u queries v v v before any child v ′ v' v ′ with r ( v ′ ) > 1 / 2 r(v') > 1/2 r ( v ′ ) > 1/2 . Moreover, by the definition of A A A , no child of v v v with smaller rank belongs to the MIS, and hence v v v itself belongs to the MIS. It follows that u ∉ M I S u \notin\mathrm{MIS} u ∈ / MIS , so the exploration stops at u u u before any child of u u u with rank larger than 1 / 2 1/2 1/2 is queried. Therefore, children in A A A with rank at least 1 / 2 1/2 1/2 are queried only if every vertex in A A A has rank at least 1 / 2 1/2 1/2 . Since the ranks { r ( v ) : v ∈ A } \{r(v) : v \in A\} { r ( v ) : v ∈ A } remain independent and uniform in [ 0 , 1 ] [0,1] [ 0 , 1 ] , this event occurs with probability 2 − ∣ A ∣ 2^{-|A|} 2 − ∣ A ∣ . Thus, conditioned on A A A , the expected number of queried vertices in A A A with ranks in ( 1 / 2 , 1 ) (1/2,1) ( 1/2 , 1 ) is at most 2 − ∣ A ∣ ⋅ ∣ A ∣ 2^{-|A|} \cdot|A| 2 − ∣ A ∣ ⋅ ∣ A ∣ which is at most a constant.
This thought experiment captures the basic mechanism behind our proof, but turning it into a full proof requires overcoming two obstacles. First, what about the cost of exploring vertices with ranks below 1 / 2 1/2 1/2 , which we have so far ignored? Second, and a major challenge in our work, how can one continue this reasoning recursively once previously revealed randomness creates dependencies that were absent in the definition of A A A ? We address these obstacles in two stages.
Interval decomposition, encodings, and the first obstacle (Section 3). We begin with the first obstacle, namely, that the thought experiment ignores all work performed at vertices of rank below 1 / 2 1/2 1/2 . To handle this, we partition the rank space into intervals of the form [ 2 − j , 2 − j + 1 ) [2^{-j},2^{-j+1}) [ 2 − j , 2 − j + 1 ) and use these intervals to encode paths according to the scale of the ranks they encounter. For a fixed such encoding, we then enlarge the class of paths we consider and work with candidate paths , namely paths whose vertices lie in the prescribed intervals, even if they are not necessarily queried by the recursion. Thus, the interval decomposition is what both organizes the analysis and defines the larger family of paths on which we work.
The point of passing to candidate paths is that they reveal only coarse information about the ranks along the path – namely, the interval in which each rank lies, but not its exact value inside that interval. This is exactly the amount of information we can afford to reveal. It preserves enough randomness so that the relative order of vertices that fall within the same interval remains hidden. As a result, the probability that a candidate path is a query path is roughly 1 / ( k 1 ! ⋯ k m ! ) 1/(k_1! \cdots k_m!) 1/ ( k 1 ! ⋯ k m !) , where k i k_i k i denotes the number of vertices on the candidate path that lie in the interval ( 1 / 2 i , 1 / 2 i − 1 ) (1/2^i,1/2^{i-1}) ( 1/ 2 i , 1/ 2 i − 1 ) .
Refined encodings and the second obstacle (Section 4). The second obstacle is that the “clean” independence used in the thought experiment breaks down under recursion. In the thought experiment, the set A A A was useful because we could determine membership in A A A without revealing the actual ranks of the vertices in A A A themselves. In the recursive process, however, once we move one level deeper, some information in the relevant subtrees has already been revealed. Thus, even after passing to candidate paths, one cannot simply repeat the same argument at every level.
This is where the main technical tool of the proof enters, namely a refined path encoding . At each step, there is a natural threshold coming from the interval of the next vertex on the path. The refined encoding records how much this threshold needs to be “lowered”, and uses flags to mark a sparse set of levels where such lowering is genuinely necessary. Informally, these are the levels where we must pay for a large branching event; at the other levels, we avoid revealing comparable information. This is what allows the thought-experiment intuition to be applied repeatedly without exposing too much randomness along the way. Combined with the exponential tail bound for such large-branching events – which we already saw informally in the thought experiment – this yields an exponentially decaying contribution for each valid encoding. Summing over all encodings then gives the desired bound on the number of candidate paths.
Statement on AI use
All of the text in this paper was written by the (human) authors of this submission. AI was used only for proofreading: to identify grammatical and mathematical errors. All comments and suggestions made by AI were thoroughly reviewed by the authors. All proofs and technical ideas in this paper were developed solely by the authors, without any AI involvement.
Preliminaries
The randomized greedy MIS algorithm is outlined in Algorithm 1.
Algorithm 1 The RGMIS algorithm
1: procedure RGMIS($G$, $u$, $r$)
Input: A graph $G$, vertex $u$ and distinct ranks $r : V(G) \to [0,1)$.
Output: Does $u$ belong to the MIS in the greedy algorithm that processes the vertices in increasing order of $r$?
2: Obtain $\Gamma(u)$, the list of neighbors of $u$.
3: for each $w \in \Gamma(u)$ with $r(w) < r(u)$ in increasing order of $r(w)$ do
4: if RGMIS($G$, $w$, $r$) = YES then
5: return NO
6: return YES
In this paper, we are interested in the (expected) size and depth of the recursion tree produced by Algorithm 1 starting from a worst-case vertex v v v of a tree, where expectation is taken over uniformly sampled vertex ranks.
Definition 2.1 (Query tree and size). Given a graph G G G , vertex u ∈ V ( G ) u \in V(G) u ∈ V ( G ) and rank r : V ( G ) → [ 0 , 1 ) r : V(G) \to[0,1) r : V ( G ) → [ 0 , 1 ) , we denote by Q ( G , u , r ) Q(G,u,r) Q ( G , u , r ) , the recursion tree obtained from the execution of RGMIS(G , u , r G,u,r G , u , r ). We use ∣ Q ( G , u , r ) ∣ |Q(G,u,r)| ∣ Q ( G , u , r ) ∣ to denote the size (number of vertices) of the tree Q ( G , u , r ) Q(G,u,r) Q ( G , u , r ) .
Definition 2.2 (Query path). We say that a path P = ( u 0 , u 1 , … u L − 1 ) P = (u_0, u_1, \ldots u_{L-1}) P = ( u 0 , u 1 , … u L − 1 ) in a tree T \mathcal{T} T is a query path if the execution of RGMIS(T , u i , r \mathcal{T},u_i,r T , u i , r ) directly invokes RGMIS(T , u i + 1 , r \mathcal{T},u_{i+1},r T , u i + 1 , r ) for each i = 0 , 1 , … L − 2 i = 0,1,\ldots L-2 i = 0 , 1 , … L − 2 . For simplicity, we say that u i u_i u i queries u i + 1 u_{i+1} u i + 1 if RGMIS(T , u i , r \mathcal{T},u_i,r T , u i , r ) invokes RGMIS(T , u i + 1 , r \mathcal{T},u_{i+1},r T , u i + 1 , r ).
Definition 2.3 (Worst case expected query complexity). For an integer Δ ≥ 1 \Delta\ge1 Δ ≥ 1 , let Tree(Δ \Delta Δ ) denote the set of all trees of maximum degree Δ \Delta Δ . The worst case expected query complexity of Algorithm 1 on a tree of maximum degree Δ \Delta Δ is given by,
max G ∈ Tree ( Δ ) , v ∈ G E r [ ∣ Q ( G , v , r ) ∣ ] \max_{\substack{G \in\operatorname{Tree}(\Delta),\\v\in G}} \mathbb{E}_{r}\left[|Q(G,v,r)|\right] G ∈ Tree ( Δ ) , v ∈ G max E r [ ∣ Q ( G , v , r ) ∣ ]
Technicality of distinct ranks. In Definition 2.3 , we assume that the ranks r : V ( G ) → [ 0 , 1 ) r : V(G) \to[0,1) r : V ( G ) → [ 0 , 1 ) are sampled uniformly and independently for each vertex v ∈ V ( G ) v \in V(G) v ∈ V ( G ) . However, Algorithm 1 requires that the ranks are distinct for each vertex. In our analysis we will assume that r r r is distinct for all vertices, which is an almost sure event. Hence, our analysis also applies to the version of RGMIS that samples a uniform permutation π \pi π and sets the rank as r ( u ) = π ( u ) / n r(u) = \pi(u)/n r ( u ) = π ( u ) / n where π ( u ) ∈ { 0 , 1 , … n − 1 } \pi(u) \in\{0,1,\ldots n-1\} π ( u ) ∈ { 0 , 1 , … n − 1 } .
Counting the number of query paths
In this section, we give the proof of Theorem 1.1 assuming a technical lemma (Lemma 3.12 ). We prove Lemma 3.12 in § 4 . We start by introducing some definitions and explaining the intuition behind them.
Setup and notation. Consider a rooted tree T \mathcal{T} T and let u 0 u_0 u 0 be its root. Consider the execution of RGMIS( T , u 0 , r ) (\mathcal{T}, u_0, r) ( T , u 0 , r ) over uniformly sampled rank r : V ( T ) → [ 0 , 1 ) r: V(\mathcal{T}) \to[0,1) r : V ( T ) → [ 0 , 1 ) . We denote by T v \mathcal{T}_v T v , the sub-tree beneath vertex v v v in the rooted tree. We denote by Γ ( v ) \Gamma(v) Γ ( v ) the set of children of v v v in the rooted tree T \mathcal{T} T . More formally, Γ ( v ) \Gamma(v) Γ ( v ) is the set of neighbors of v v v that are farther than v v v from u 0 u_0 u 0 .
We show that the expected number of query paths starting at the root is at most poly ( Δ ) \operatorname{poly}(\Delta) poly ( Δ ) , where Δ \Delta Δ is the maximum number of children of any vertex in the tree when rooted at u 0 u_0 u 0 . Observe that the maximum degree is at most Δ + 1 \Delta+ 1 Δ + 1 and hence the poly ( Δ ) \operatorname{poly}(\Delta) poly ( Δ ) claim also holds with Δ \Delta Δ being the maximum degree in the tree. Our strategy will be to partition the interval [ 0 , 1 ) [0,1) [ 0 , 1 ) into sub-intervals with geometrically decreasing sizes.
For an integer j j j , let τ ( j ) = 2 − j \tau(j) = 2^{-j} τ ( j ) = 2 − j . We partition the interval [ 0 , 1 ) [0,1) [ 0 , 1 ) into infinitely many intervals [ τ ( j ) , τ ( j − 1 ) ) [\tau(j),\tau(j-1)) [ τ ( j ) , τ ( j − 1 )) , for j ∈ Z > 0 j \in\mathbb{Z}_{>0} j ∈ Z > 0 . Every number x ∈ ( 0 , 1 ) x \in(0,1) x ∈ ( 0 , 1 ) , and in particular (w.p. 1), the rank of every vertex, belongs to exactly one such interval. Thus, for every query path P = ( u 0 , u 1 , … , u L − 1 ) P = (u_0,u_1,\ldots,u_{L-1}) P = ( u 0 , u 1 , … , u L − 1 ) , there exists a unique choice of numbers s 0 , … , s L − 1 ∈ Z > 0 s_0,\ldots,s_{L-1} \in\mathbb{Z}_{>0} s 0 , … , s L − 1 ∈ Z > 0 such that,
r ( u i ) ∈ [ τ ( s i ) , τ ( s i − 1 ) ) for all i ∈ { 0 , 1 , … , L − 1 } . (1) r(u_i) \in[\tau(s_i),\tau(s_i-1)) \qquad\text{for all } i \in\{0,1,\ldots,L-1\}. \tag*{(1)} r ( u i ) ∈ [ τ ( s i ) , τ ( s i − 1 )) for all i ∈ { 0 , 1 , … , L − 1 } . (1)
Here r ( u ) r(u) r ( u ) denotes the rank of vertex u u u . If a path P = ( u 0 , … , u L − 1 ) P = (u_0,\ldots,u_{L-1}) P = ( u 0 , … , u L − 1 ) satisfies (1) , then we say that P P P agrees with s s s . Note that for every query path P P P we have r ( u 0 ) > r ( u 1 ) > ⋯ > r ( u L − 1 ) r(u_0) > r(u_1) > \cdots> r(u_{L-1}) r ( u 0 ) > r ( u 1 ) > ⋯ > r ( u L − 1 ) , and therefore the corresponding sequence satisfies s 0 ≤ s 1 ≤ ⋯ ≤ s L − 1 s_0 \leq s_1 \leq\cdots\leq s_{L-1} s 0 ≤ s 1 ≤ ⋯ ≤ s L − 1 .
Let m = ⌈ log 2 Δ ⌉ m = \lceil\log_2 \Delta\rceil m = ⌈ log 2 Δ ⌉ . The suffix of the path with s i > m s_i > m s i > m have ranks smaller than 1 / Δ 1/\Delta 1/Δ . For such vertices, pruning has negligible effect and the number of monotone paths is in itself small enough. In Section A.1, we show that the contribution by such vertices can only increase the expected value by a constant factor. Hence, in this main technical portion of the paper, we count only those paths ending at vertices with rank at least τ ( m ) \tau(m) τ ( m ) . Thus, we are mainly interested in paths that agree with non-decreasing sequences s s s containing integers in [ m ] [m] [ m ] . We use [ k ] [k] [ k ] to denote the set { 1 , 2 , … , k } \{1,2,\ldots,k\} { 1 , 2 , … , k } . The relevant sequences of length L L L are:
S ( L ) = { s ∈ [ m ] L : s 0 ≤ s 1 ≤ ⋯ ≤ s L − 1 } . S(L) = \{s \in[m]^L : s_0 \leq s_1 \leq\cdots\leq s_{L-1}\}. S ( L ) = { s ∈ [ m ] L : s 0 ≤ s 1 ≤ ⋯ ≤ s L − 1 } .
We denote by S \mathcal{S} S the union of S ( L ) S(L) S ( L ) over all L ≥ 0 L \geq0 L ≥ 0 . To upper bound the expected number of query paths, we separately bound the number of query paths that agree with each s ∈ S ( L ) s \in S(L) s ∈ S ( L ) and then sum these bounds over all s ∈ S ( L ) s \in S(L) s ∈ S ( L ) and all L ≥ 1 L \geq1 L ≥ 1 .
We now introduce some notation. We denote the depth of a vertex u u u in the tree by δ ( u ) \delta(u) δ ( u ) , where the depth of the root is 0. Note that if u 0 , … , u L − 1 u_0,\ldots,u_{L-1} u 0 , … , u L − 1 is a query path starting at the root, then δ ( u i ) = i \delta(u_i) = i δ ( u i ) = i . The interpretation of (1) is that the rank of a vertex u u u on a downward path from the root that agrees with s s s must lie in the interval [ τ ( s δ ( u ) ) , τ ( s δ ( u ) − 1 ) ) [\tau(s_{\delta(u)}),\tau(s_{\delta(u)}-1)) [ τ ( s δ ( u ) ) , τ ( s δ ( u ) − 1 )) . We will denote the maximal independent set (MIS) obtained by the RGMIS algorithm by I \mathcal{I} I . This set is random and depends on the choice of ranks of vertices in the tree. We now give two key definitions. These definitions form the crux of our proof and will enable us to expose and reveal required randomness to prove our claims.
Definition of Promising Vertices
The first definition is the notion of a promising vertex . The reader should carefully note the specific way in which it is defined and the randomness that it depends on.
Definition 3.1 (Promising vertices). We say that a vertex v v v is promising at threshold θ \theta θ if no child w ∈ Γ ( v ) w \in\Gamma(v) w ∈ Γ ( v ) with r ( w ) < θ r(w) < \theta r ( w ) < θ satisfies,
RGMIS ( T w , w , r ) = Y E S \operatorname{RGMIS}(\mathcal{T}_w,w,r) = \mathrm{YES} RGMIS ( T w , w , r ) = YES That is, in the execution of RGMIS in the sub-tree T w \mathcal{T}_w T w beneath w w w using the same rank function r r r , the vertex w w w is added to the independent set.
The event Prom ( v , θ ) \operatorname{Prom}(v,\theta) Prom ( v , θ ) ≔ \coloneqq : = “v v v is promising at threshold θ \theta θ ” is random and is determined by the random ranks of the vertices in the tree. Note however that Prom ( v , θ ) \operatorname{Prom}(v,\theta) Prom ( v , θ ) is intentionally defined to be independent of r ( v ) r(v) r ( v ) itself, but rather depends only on the ranks in the strict sub-forest T v − v \mathcal{T}_v-v T v − v . The next crucial observation is that although Prom ( v , θ ) \operatorname{Prom}(v,\theta) Prom ( v , θ ) inspects only ranks in T v − v \mathcal{T}_v-v T v − v , all the vertices w ∈ T v − v w\in\mathcal{T}_v-v w ∈ T v − v that are actually queried by the RGMIS algorithm have the same output in the sub-tree T w \mathcal{T}_w T w as the global tree T \mathcal{T} T , which we prove below in Observation 3.2 . In particular, for our purposes, we may assume5 that Prom ( v , θ ) \operatorname{Prom}(v,\theta) Prom ( v , θ ) implies that v v v does not contain a child w w w with r ( w ) < θ r(w)<\theta r ( w ) < θ and w ∈ I w\in\mathcal{I} w ∈ I . We prove this in Lemma 3.3.
Observation 3.2 (Local-Global execution equivalence). Suppose RGMIS( T , u 0 , r ) (\mathcal{T},u_0,r) ( T , u 0 , r ) invokes, either directly or indirectly, RGMIS( T , v , r ) (\mathcal{T},v,r) ( T , v , r ) for some vertex v ∈ T v\in\mathcal{T} v ∈ T . It holds that,
RGMIS ( T , v , r ) = RGMIS ( T v , v , r ) \operatorname{RGMIS}(\mathcal{T},v,r)=\operatorname{RGMIS}(\mathcal{T}_v,v,r) RGMIS ( T , v , r ) = RGMIS ( T v , v , r ) That is, the output of the execution of vertex v v v in the global tree T \mathcal{T} T is equivalent to the output of v v v in the sub-tree T v \mathcal{T}_v T v beneath vertex v v v in T \mathcal{T} T .
Proof. We prove the stronger statement that the RGMIS recursion trees generated by the two executions are identical. It follows from the rule of RGMIS, i.e., output at v v v is the NOR of the outputs of all neighbors of v v v in the query tree (with NOR of an empty set being YES), that the outputs are identical.
First if v = u v=u v = u , then the statement is trivial. Henceforth we may assume that v ≠ u v\ne u v = u and hence p v p_v p v , the parent of v v v in the rooted tree T \mathcal{T} T exists and is unique. Since RGMIS( T , v , r ) (\mathcal{T},v,r) ( T , v , r ) is invoked, it holds that r ( p v ) > r ( v ) r(p_v)>r(v) r ( p v ) > r ( v ) . Hence RGMIS( T , v , r ) (\mathcal{T},v,r) ( T , v , r ) does not invoke RGMIS( T , w , r ) (\mathcal{T},w,r) ( T , w , r ) for any w ∈ T − V ( T v ) w\in\mathcal{T}-V(\mathcal{T}_v) w ∈ T − V ( T v ) . A consequence of this is that all the recursive calls generated directly or indirectly by RGMIS( T , v , r ) (\mathcal{T},v,r) ( T , v , r ) are of the form RGMIS( T , w , r ) (\mathcal{T},w,r) ( T , w , r ) for some w ∈ T v w\in\mathcal{T}_v w ∈ T v . All of these vertices are also present in T v \mathcal{T}_v T v and hence this is a valid RGMIS query tree for the call RGMIS( T v , v , r ) (\mathcal{T}_v,v,r) ( T v , v , r ) which is unique and hence must also be identical to the query tree for that call. It follows that,
RGMIS ( T , v , r ) = RGMIS ( T v , v , r ) \operatorname{RGMIS}(\mathcal{T},v,r)=\operatorname{RGMIS}(\mathcal{T}_v,v,r) RGMIS ( T , v , r ) = RGMIS ( T v , v , r )
as desired.
Lemma 3.3 (Promising definition motivation). Consider an arbitrary vertex v v v in the tree that is queried by RGMIS( T , u 0 , r ) (\mathcal{T},u_0,r) ( T , u 0 , r ) . If v v v is promising at threshold θ \theta θ and r ( v ) < θ r(v)<\theta r ( v ) < θ , then v v v belongs to the global independent set I \mathcal{I} I (w.p. 1).
Proof. Consider all the vertices w w w with r ( w ) < r ( v ) r(w)<r(v) r ( w ) < r ( v ) that is queried by the recursive call RGMIS( T , v , r ) (\mathcal{T},v,r) ( T , v , r ) . From Observation 3.2 , it holds that
RGMIS ( T , w , r ) = RGMIS ( T w , w , r ) \operatorname{RGMIS}(\mathcal{T},w,r)=\operatorname{RGMIS}(\mathcal{T}_w,w,r) RGMIS ( T , w , r ) = RGMIS ( T w , w , r ) As r ( w ) < r ( v ) < θ r(w)<r(v)<\theta r ( w ) < r ( v ) < θ , the definition of promising gives, RGMIS( T w , w , r ) = (\mathcal{T}_w,w,r)= ( T w , w , r ) = NO. Combining with the equation above, we get RGMIS( T , w , r ) = (\mathcal{T},w,r)= ( T , w , r ) = NO. From the pseudo-code of the RGMIS algorithm (See Algorithm 1), it follows that RGMIS( T , v , r ) = (\mathcal{T},v,r)= ( T , v , r ) = YES, i.e., v ∈ I v\in\mathcal{I} v ∈ I .
Definition of Candidate Paths and Candidate Sets
The second key ingredient will be the definition of Candidate Paths and closely related notion of Candidate Sets . Given a path P = ( u 0 , u 1 , … , u L − 1 ) P=(u_0,u_1,\ldots,u_{L-1}) P = ( u 0 , u 1 , … , u L − 1 ) and a sequence s s s , we say that P P P is a candidate path for s s s if for each valid i i i , (i) r ( u i ) r(u_i) r ( u i ) belongs to [ τ ( s i ) , τ ( s i − 1 ) ) [\tau(s_i),\tau(s_i-1)) [ τ ( s i ) , τ ( s i − 1 )) and more crucially, (ii) u i u_i u i is promising at threshold τ ( s i + 1 ) \tau(s_{i+1}) τ ( s i + 1 ) . The event (ii) captures the effect of pruning in the algorithm. It guarantees that in the local tree T u i T_{u_i} T u i , the vertex u i u_i u i has not terminated execution by finding an MIS vertex with rank smaller than τ ( s i + 1 ) \tau(s_{i+1}) τ ( s i + 1 ) . By the intuition presented in the previous sub-section, this implies that if u i u_i u i is queried by the algorithm, then the recursive call RGMIS(T , u i , r T,u_i,r T , u i , r ) cannot have terminated execution before querying a vertex with rank smaller than τ ( s i + 1 ) ≤ r ( u i + 1 ) \tau(s_{i+1})\leq r(u_{i+1}) τ ( s i + 1 ) ≤ r ( u i + 1 ) , which is a conservative condition to be satisfied if u i u_i u i is to query u i + 1 u_{i+1} u i + 1 after implementing pruning. We next formally state this definition.
Definition 3.4 (Candidate Path). A downward path u 0 , … , u L − 1 u_0,\ldots,u_{L-1} u 0 , … , u L − 1 starting at the root is a candidate path agreeing with s s s if, (i) it agrees with s s s and, (ii) for all i < L − 1 i<L-1 i < L − 1 , u i u_i u i is promising at threshold τ ( s i + 1 ) \tau(s_{i+1}) τ ( s i + 1 ) .
From the observations in the previous sub-section it is not hard to show that a query path P P P with ranks agreeing with s s s must also be a candidate path for s s s . We shall defer the proof for now (See Lemmas 3.9 ,3.8). We next define candidate sets for vertices u i u_i u i that contain all possible choices for u i + 1 u_{i+1} u i + 1 assuming that the prefix ( u 0 , u 1 , u 2 , … , u i ) (u_0,u_1,u_2,\ldots,u_i) ( u 0 , u 1 , u 2 , … , u i ) is a potential prefix of a candidate path for s s s .
Definition 3.5 (Candidate Set). Let s ∈ S ( L ) s\in S(L) s ∈ S ( L ) and θ ∈ ( 0 , 1 ) \theta\in(0,1) θ ∈ ( 0 , 1 ) . For every vertex u u u , we define the candidate set A θ ( u ) A_\theta(u) A θ ( u ) as follows. If u u u is not promising at θ \theta θ , then we set A θ ( u ) = ∅ A_\theta(u)=\varnothing A θ ( u ) = ∅ . Otherwise,
A θ ( u ) = { v ∈ Γ ( u ) : r ( v ) ∈ [ τ ( s δ ( v ) ) , τ ( s δ ( v ) − 1 ) ) and v is promising at threshold θ } . A_\theta(u)=\{v\in\Gamma(u):r(v)\in[\tau(s_{\delta(v)}),\tau(s_{\delta(v)}-1))\text{ and }v\text{ is promising at threshold }\theta\}. A θ ( u ) = { v ∈ Γ ( u ) : r ( v ) ∈ [ τ ( s δ ( v ) ) , τ ( s δ ( v ) − 1 )) and v is promising at threshold θ } .
Observation 3.6 (Candidate paths can be encoded by candidate sets). If ( u 0 , u 1 , … , u L − 1 ) (u_0,u_1,\ldots,u_{L-1}) ( u 0 , u 1 , … , u L − 1 ) is a candidate path for sequence s s s , then for each i < L − 2 i<L-2 i < L − 2 and θ ≤ τ ( s i + 2 ) \theta\leq\tau(s_{i+2}) θ ≤ τ ( s i + 2 ) ,
u i + 1 ∈ A θ ( u i ) u_{i+1}\in A_\theta(u_i) u i + 1 ∈ A θ ( u i ) That is, the prefix ( u 0 , u 1 , … , u L − 2 ) (u_0,u_1,\ldots,u_{L-2}) ( u 0 , u 1 , … , u L − 2 ) of the path may be encoded by an integer sequence ( a 1 , a 2 , … , a L − 2 ) (a_1,a_2,\ldots,a_{L-2}) ( a 1 , a 2 , … , a L − 2 ) where a i + 1 a_{i+1} a i + 1 is the position of u i + 1 u_{i+1} u i + 1 in the set A θ ( u i ) A_\theta(u_i) A θ ( u i ) for any θ ≤ τ ( s i + 2 ) \theta\leq\tau(s_{i+2}) θ ≤ τ ( s i + 2 )
Proof. Since u i u_i u i is promising at threshold τ ( s i + 1 ) \tau(s_{i+1}) τ ( s i + 1 ) , A θ ( u i ) A_\theta(u_i) A θ ( u i ) it is not forcibly set to ∅ \varnothing ∅ by Definition 3.5 for any θ ≤ τ ( s i + 1 ) \theta\leq\tau(s_{i+1}) θ ≤ τ ( s i + 1 ) which includes all θ ≤ τ ( s i + 2 ) \theta\leq\tau(s_{i+2}) θ ≤ τ ( s i + 2 ) . Now, u i + 1 ∈ A θ ( u i ) u_{i+1}\in A_\theta(u_i) u i + 1 ∈ A θ ( u i ) for θ ≤ τ ( s i + 2 ) \theta\leq\tau(s_{i+2}) θ ≤ τ ( s i + 2 ) now holds from (i) P P P agreeing with s s s and (ii) u i + 1 u_{i+1} u i + 1 being promising at threshold τ ( s i + 2 ) \tau(s_{i+2}) τ ( s i + 2 ) and hence also θ \theta θ . □ \square □
Observation 3.7 (Membership in A θ ( u ) A_\theta(u) A θ ( u ) is monotone in θ \theta θ ). For any vertex u u u and any θ , θ ′ \theta,\theta' θ , θ ′ with θ ′ ≤ θ \theta'\leq\theta θ ′ ≤ θ we have,
A θ ( u ) ⊆ A θ ′ ( u ) A_\theta(u)\subseteq A_{\theta'}(u) A θ ( u ) ⊆ A θ ′ ( u )
Proof. If a vertex v v v is promising at threshold θ ∈ ( 0 , 1 ) \theta\in(0,1) θ ∈ ( 0 , 1 ) , then it is also promising at any threshold θ ′ < θ \theta'<\theta θ ′ < θ . First, we consider the case A θ ′ ( u ) = ∅ A_{\theta'}(u)=\varnothing A θ ′ ( u ) = ∅ due to u u u not being promising at θ ′ \theta' θ ′ . It follows that u u u is not promising at θ \theta θ and hence A θ ( u ) = A θ ′ ( u ) = ∅ A_\theta(u)=A_{\theta'}(u)=\varnothing A θ ( u ) = A θ ′ ( u ) = ∅ . Henceforth, we assume u u u is promising at θ ′ \theta' θ ′ .
Next, for an arbitrary v ∈ A θ ( u ) v\in A_\theta(u) v ∈ A θ ( u ) , suppose v v v is promising at θ \theta θ . It holds that v v v is also promising at θ ′ \theta' θ ′ . Hence v ∈ A θ ′ ( u ) v\in A_{\theta'}(u) v ∈ A θ ′ ( u ) . We have A θ ( u ) ⊆ A θ ′ ( u ) A_\theta(u)\subseteq A_{\theta'}(u) A θ ( u ) ⊆ A θ ′ ( u ) as desired. □ \square □
We now show that, for a query path agreeing with s s s , each next vertex v v v belongs to the candidate set of the preceding vertex u u u at threshold τ ( s δ ( v ) ) \tau(s_{\delta(v)}) τ ( s δ ( v ) ) , with the exception of the last two vertices. We begin by proving that every vertex v v v on such a query path, except possibly the last one, is promising at threshold τ ( s δ ( v ) ) \tau(s_{\delta(v)}) τ ( s δ ( v ) ) .
Claim 3.8. Consider a path u 0 , … , u L − 1 u_0,\ldots,u_{L-1} u 0 , … , u L − 1 and s ∈ S ( L ) s \in S(L) s ∈ S ( L ) . If this path is a query path agreeing with s s s , then each u i u_i u i with i < L − 1 i < L-1 i < L − 1 is promising at threshold τ ( s i + 1 ) \tau(s_{i+1}) τ ( s i + 1 ) .
Proof. Suppose P = u 0 , … , u L − 1 P = u_0,\ldots,u_{L-1} P = u 0 , … , u L − 1 is a query path agreeing with s s s , and fix i < L − 1 i < L-1 i < L − 1 . Since P P P is a query path, vertex u i u_i u i queries u i + 1 u_{i+1} u i + 1 . Because P P P agrees with s s s , the rank of u i + 1 u_{i+1} u i + 1 lies in [ τ ( s i + 1 ) , τ ( s i + 1 − 1 ) ) [\tau(s_{i+1}),\tau(s_{i+1}-1)) [ τ ( s i + 1 ) , τ ( s i + 1 − 1 )) and, in particular, τ ( s i + 1 ) ≤ r ( u i + 1 ) \tau(s_{i+1}) \le r(u_{i+1}) τ ( s i + 1 ) ≤ r ( u i + 1 ) .
Suppose, for contradiction, that there exists a child w ∈ Γ ( u i ) w \in\Gamma(u_i) w ∈ Γ ( u i ) such that r ( w ) < τ ( s i + 1 ) r(w) < \tau(s_{i+1}) r ( w ) < τ ( s i + 1 ) and RGMIS( T w , w , r ) = YES (T_w,w,r) = \text{YES} ( T w , w , r ) = YES . Since r ( w ) < r ( u i + 1 ) r(w) < r(u_{i+1}) r ( w ) < r ( u i + 1 ) and u i u_i u i queries u i + 1 u_{i+1} u i + 1 , from the pseudocode of RGMIS it follows that w w w is called by u i u_i u i . Now, Observation 3.2 applies to w w w , giving RGMIS( T , w , r ) = YES (T,w,r) = \text{YES} ( T , w , r ) = YES , i.e., w ∈ I w \in\mathcal{I} w ∈ I . Since RGMIS queries children in increasing order of rank and stops once it encounters a child in I \mathcal{I} I , vertex u i u_i u i would stop querying its children upon reaching w w w . As r ( w ) < τ ( s i + 1 ) ≤ r ( u i + 1 ) r(w) < \tau(s_{i+1}) \le r(u_{i+1}) r ( w ) < τ ( s i + 1 ) ≤ r ( u i + 1 ) , this would prevent u i u_i u i from querying u i + 1 u_{i+1} u i + 1 , contradicting the assumption that P P P is a query path. Therefore, no such vertex w w w exists, and u i u_i u i is promising at threshold τ ( s i + 1 ) \tau(s_{i+1}) τ ( s i + 1 ) .
Lemma 3.9. If P = ( u 0 , … , u L − 1 ) P = (u_0,\ldots,u_{L-1}) P = ( u 0 , … , u L − 1 ) is a query path agreeing with s s s , then for every i < L − 2 i < L-2 i < L − 2 and θ ≤ τ ( s i + 2 ) \theta\le\tau(s_{i+2}) θ ≤ τ ( s i + 2 ) it holds that,
u i + 1 ∈ A θ ( u i ) . u_{i+1} \in A_\theta(u_i). u i + 1 ∈ A θ ( u i ) .
Proof. Fix an index i < L − 2 i < L-2 i < L − 2 and consider the vertex u i u_i u i . We first show that the first case in the definition of A θ ( u i ) A_\theta(u_i) A θ ( u i ) does not occur. Suppose, for contradiction, that u i u_i u i is not promising at threshold θ \theta θ . As u i u_i u i is queried, this implies that u i u_i u i contains a child w w w with r ( w ) < θ r(w) < \theta r ( w ) < θ and RGMIS( T w , w , r ) = YES (T_w,w,r) = \text{YES} ( T w , w , r ) = YES . As r ( w ) < r ( u i + 1 ) r(w) < r(u_{i+1}) r ( w ) < r ( u i + 1 ) , w w w must be queried. Since w w w is queried, then by Observation 3.2 , RGMIS( T , w , r ) = YES (T,w,r) = \text{YES} ( T , w , r ) = YES . From the pseudocode of RGMIS, u i u_i u i must terminate before it can query any vertex with rank at least θ \theta θ (either by terminating at w w w or an even earlier vertex) which includes u i + 1 u_{i+1} u i + 1 as r ( u i + 1 ) ≥ τ ( s i + 1 ) ≥ τ ( s i + 2 ) ≥ θ r(u_{i+1}) \ge\tau(s_{i+1}) \ge\tau(s_{i+2}) \ge\theta r ( u i + 1 ) ≥ τ ( s i + 1 ) ≥ τ ( s i + 2 ) ≥ θ . This contradicts the assumption that P P P is a query path.
It remains to show that (i) r ( u i + 1 ) ∈ [ τ ( s i + 1 ) , τ ( s i + 1 − 1 ) ) r(u_{i+1}) \in[\tau(s_{i+1}),\tau(s_{i+1}-1)) r ( u i + 1 ) ∈ [ τ ( s i + 1 ) , τ ( s i + 1 − 1 )) and (ii) u i + 1 u_{i+1} u i + 1 is promising at threshold θ \theta θ . Condition (i) is guaranteed by the assumption that P P P agrees with s s s . To prove condition (ii) we show that u i + 1 u_{i+1} u i + 1 is promising at threshold τ ( s i + 2 ) ≥ θ \tau(s_{i+2}) \ge\theta τ ( s i + 2 ) ≥ θ which is stronger.
Consider an arbitrary child w ∈ Γ ( u i + 1 ) w \in\Gamma(u_{i+1}) w ∈ Γ ( u i + 1 ) with r ( w ) < τ ( s i + 2 ) ≤ r ( u i + 2 ) r(w) < \tau(s_{i+2}) \le r(u_{i+2}) r ( w ) < τ ( s i + 2 ) ≤ r ( u i + 2 ) . Since P P P is a query path, u i + 1 u_{i+1} u i + 1 queries u i + 2 u_{i+2} u i + 2 . From the pseudocode of RGMIS this implies that u i + 1 u_{i+1} u i + 1 also queries w w w as it has higher priority during the recursive calls. Using Observation 3.2 , since w w w is queried by the algorithm, we have RGMIS( T , w , r ) = RGMIS ( T w , w , r ) (T,w,r) = \text{RGMIS}(T_w,w,r) ( T , w , r ) = RGMIS ( T w , w , r ) . Since u i + 1 u_{i+1} u i + 1 does not terminate at w w w , RGMIS( T , w , r ) = NO (T,w,r) = \text{NO} ( T , w , r ) = NO . It follows that RGMIS( T w , w , r ) = NO (T_w,w,r) = \text{NO} ( T w , w , r ) = NO and that w w w is promising at threshold τ ( s i + 2 ) \tau(s_{i+2}) τ ( s i + 2 ) and hence also θ ≤ τ ( s i + 2 ) \theta\le\tau(s_{i+2}) θ ≤ τ ( s i + 2 ) .
The above lemmas imply that every query path agreeing with s s s is also a candidate path agreeing with s s s . Importantly, the converse does not hold, and the conditional probability that a path is a query path given that it is a candidate path is relatively small. The following lemma provides an upper bound on this probability.
Lemma 3.10 (Conditional probability of query paths given candidate path). Fix s ∈ S ( L ) s \in S(L) s ∈ S ( L ) . Let k 1 , … , k m k_1,\ldots,k_m k 1 , … , k m denote the number of indices i i i such that s i = 1 , … , m s_i = 1,\ldots,m s i = 1 , … , m , respectively. Then, for every fixed path P P P , we have
Pr ( P is a query path ∣ P is a candidate path agreeing with s ) ≤ 1 k 1 ! k 2 ! … k m ! . \Pr(P\text{ is a query path}\mid P\text{ is a candidate path agreeing with }s) \le\frac{1}{k_1!k_2!\ldots k_m!}. Pr ( P is a query path ∣ P is a candidate path agreeing with s ) ≤ k 1 ! k 2 ! … k m ! 1 .
We now prove the lemma. The key step is to justify the following observation. The proof of Lemma 3.10 then follows as the ranks of vertices in the query paths must be montone.
Lemma 3.11. Fix a downward path P = u 0 , … , u L − 1 P = u_0,\ldots,u_{L-1} P = u 0 , … , u L − 1 and a sequence s ∈ S ( L ) s \in\mathcal{S}(L) s ∈ S ( L ) . Conditioned on the event that P P P is a candidate path agreeing with s s s , the random variables r ( u 0 ) , … , r ( u L − 1 ) r(u_0),\ldots,r(u_{L-1}) r ( u 0 ) , … , r ( u L − 1 ) are mutually independent, and for each i i i the rank r ( u i ) r(u_i) r ( u i ) is uniformly distributed over [ τ ( s i ) , τ ( s i − 1 ) ) [\tau(s_i),\tau(s_i-1)) [ τ ( s i ) , τ ( s i − 1 )) .
Proof. It is sufficient to show that if P P P is a candidate path agreeing with s s s under ranks r r r , then P P P is also a candidate path for any set of ranks r ′ r' r ′ such that (i) r ′ ( u i ) ∈ [ τ ( s i ) , τ ( s i − 1 ) ) r'(u_i) \in[\tau(s_i),\tau(s_i-1)) r ′ ( u i ) ∈ [ τ ( s i ) , τ ( s i − 1 )) for all i i i , and (ii) r ′ ( v ) = r ( v ) r'(v)=r(v) r ′ ( v ) = r ( v ) for all v ∉ P v \notin P v ∈ / P .
To establish this, it suffices to prove that under r ′ r' r ′ , for each i < L − 1 i < L-1 i < L − 1 , u i + 1 u_{i+1} u i + 1 is promising at threshold τ ( s i + 1 ) \tau(s_{i+1}) τ ( s i + 1 ) . The other condition is that r ′ ( u i ) ∈ J s i r'(u_i) \in J_{s_i} r ′ ( u i ) ∈ J s i which holds by construction. Consider the two sets
W = { w ∈ Γ ( u i ) : r ( w ) < τ ( s i + 1 ) } , W ′ = { w ∈ Γ ( u i ) : r ′ ( w ) < τ ( s i + 1 ) } . W = \{w \in\Gamma(u_i) : r(w) < \tau(s_{i+1})\}, \qquad
W' = \{w \in\Gamma(u_i) : r'(w) < \tau(s_{i+1})\}. W = { w ∈ Γ ( u i ) : r ( w ) < τ ( s i + 1 )} , W ′ = { w ∈ Γ ( u i ) : r ′ ( w ) < τ ( s i + 1 )} .
We first argue that W = W ′ W = W' W = W ′ . If w ∈ W w \in W w ∈ W , then w ∉ P w \notin P w ∈ / P , since its depth is i + 1 i+1 i + 1 , while the only vertex on P P P at depth i + 1 i+1 i + 1 is u i + 1 u_{i+1} u i + 1 , which satisfies r ( u i + 1 ) ∈ [ τ ( s i + 1 ) , τ ( s i + 1 − 1 ) ) r(u_{i+1}) \in[\tau(s_{i+1}),\tau(s_{i+1}-1)) r ( u i + 1 ) ∈ [ τ ( s i + 1 ) , τ ( s i + 1 − 1 )) , whereas r ( w ) < τ ( s i + 1 ) r(w) < \tau(s_{i+1}) r ( w ) < τ ( s i + 1 ) . Hence assumption (ii) implies r ′ ( w ) = r ( w ) r'(w)=r(w) r ′ ( w ) = r ( w ) , so w ∈ W ′ w \in W' w ∈ W ′ . The converse direction is identical, giving W = W ′ W = W' W = W ′ .
Next observe that since every w ∈ W w \in W w ∈ W lies outside the path P P P , every vertex in the subtree rooted at w w w also lies outside P P P . Therefore, by assumption (ii), all ranks in this subtree are identical under r r r and r ′ r' r ′ , and hence the behavior of RGMIS within this subtree is the same under r r r and r ′ r' r ′ . It follows that RGMIS ( T w , w , r ) = N O \operatorname{RGMIS}(T_w,w,r)=\mathrm{NO} RGMIS ( T w , w , r ) = NO for each w ∈ W w \in W w ∈ W which suffices to prove that u i u_i u i is promising at threshold τ ( s i + 1 ) \tau(s_{i+1}) τ ( s i + 1 ) under rank r ′ r' r ′ as desired. □
We have shown that, for any fixed sequence s ∈ S ( L ) s \in\mathcal{S}(L) s ∈ S ( L ) , the probability that a given downward path P P P is a query path agreeing with s s s , conditioned on the event that it is a candidate path agreeing with s s s , is small. Specifically, Lemma 3.10 bounds this conditional probability by a factor depending only on the multiplicities of the values appearing in s s s . Thus, in order to bound the expected number of query paths, it suffices to control the expected number of candidate paths.
The main technical step of the analysis is therefore to bound the expected number of candidate paths of length L L L agreeing with a fixed sequence s s s . In the next subsection, we prove the following key result.
Lemma 3.12. There exists absolute constants C 1 > 0 C_1 > 0 C 1 > 0 , C 2 > 0 C_2 > 0 C 2 > 0 such that for every s ∈ S ( L ) s \in\mathcal{S}(L) s ∈ S ( L ) , the expected number of candidate paths of length L L L agreeing with s s s is at most f ( L , Δ ) = C 1 ⋅ Δ C 2 f(L,\Delta)=C_1 \cdot\Delta^{C_2} f ( L , Δ ) = C 1 ⋅ Δ C 2 .
Given Lemma 3.12 Theorem 1.1 follows by an application of linearity of expectation over query paths agreeing with all sequences in S \mathcal{S} S . We restate the theorem here for convenience and give its proof assuming Lemma 3.12 .
Theorem 1.1. There exists an absolute constant C > 0 C > 0 C > 0 such that for every integer Δ ≥ 2 \Delta\ge2 Δ ≥ 2 , every tree T T T with maximum degree Δ \Delta Δ and every vertex u u u in T T T , the expected size of the query tree Q ( T , u , r ) Q(T,u,r) Q ( T , u , r ) from u u u over uniformly assigned random ranks r r r is at most Δ C \Delta^C Δ C , i.e.,
E r [ ∣ Q ( T , u , r ) ∣ ] ≤ Δ C . \mathbb{E}_r[|Q(T,u,r)|] \le\Delta^C. E r [ ∣ Q ( T , u , r ) ∣ ] ≤ Δ C .
Proof of Theorem 1.1 given Lemma 3.12 . Fix L ≥ 1 L \ge1 L ≥ 1 and a sequence s ∈ S ( L ) s \in\mathcal{S}(L) s ∈ S ( L ) , and let k 1 , … , k m k_1,\ldots,k_m k 1 , … , k m denote the number of indices i i i such that s i = 1 , … , m s_i=1,\ldots,m s i = 1 , … , m , respectively. By Lemma 3.10 , the expected number of query paths of length L L L agreeing with s s s is at most
f ( L , Δ ) ⋅ 1 k 1 ! ⋯ k m ! . f(L,\Delta) \cdot\frac{1}{k_1! \cdots k_m!}. f ( L , Δ ) ⋅ k 1 ! ⋯ k m ! 1 .
Summing over all L ≥ 1 L \ge1 L ≥ 1 and all admissible multiplicity vectors ( k 1 , … , k m ) (k_1,\ldots,k_m) ( k 1 , … , k m ) with k 1 + ⋯ + k m = L k_1+\cdots+k_m=L k 1 + ⋯ + k m = L , we obtain the following upper bound on the expected number of query paths:
∑ L ≥ 1 ∑ k ∈ Z ≥ 0 m k 1 + ⋯ + k m = L f ( L , Δ ) ⋅ 1 k 1 ! ⋯ k m ! = ∑ L ≥ 1 f ( L , Δ ) ⋅ ∑ k ∈ Z ≥ 0 m k 1 + ⋯ + k m = L 1 k 1 ! ⋯ k m ! . \sum_{L\ge1}\ \sum_{\substack{\boldsymbol{k}\in\mathbb{Z}_{\ge0}^{m}\\ k_1+\cdots+k_m=L}} f(L,\Delta)\cdot\frac{1}{k_1!\cdots k_m!}
=
\sum_{L\ge1}f(L,\Delta)\cdot\sum_{\substack{\boldsymbol{k}\in\mathbb{Z}_{\ge0}^{m}\\ k_1+\cdots+k_m=L}}\frac{1}{k_1!\cdots k_m!}. L ≥ 1 ∑ k ∈ Z ≥ 0 m k 1 + ⋯ + k m = L ∑ f ( L , Δ ) ⋅ k 1 ! ⋯ k m ! 1 = L ≥ 1 ∑ f ( L , Δ ) ⋅ k ∈ Z ≥ 0 m k 1 + ⋯ + k m = L ∑ k 1 ! ⋯ k m ! 1 .
We now show that the inner sum on the right-hand side equals m L / L ! m^L/L! m L / L ! .
Claim 3.13. For any pair of integers m ≥ 1 m\ge1 m ≥ 1 and L ≥ 0 L\ge0 L ≥ 0 ,
∑ k ∈ Z ≥ 0 m k 1 + ⋯ + k m = L 1 k 1 ! ⋯ k m ! = m L L ! . \sum_{\substack{\boldsymbol{k}\in\mathbb{Z}_{\ge0}^{m}\\ k_1+\cdots+k_m=L}}\frac{1}{k_1!\cdots k_m!}=\frac{m^L}{L!}. k ∈ Z ≥ 0 m k 1 + ⋯ + k m = L ∑ k 1 ! ⋯ k m ! 1 = L ! m L . Proof. Consider the multivariate generating function
G ( x 1 , … , x m ) = e x 1 ⋯ e x m . G(x_1,\ldots,x_m)=e^{x_1}\cdots e^{x_m}. G ( x 1 , … , x m ) = e x 1 ⋯ e x m . On the one hand, writing each exponential as its Taylor expansion and taking the product, we obtain
G ( x 1 , … , x m ) = ∏ j = 1 m ( ∑ k j ≥ 0 x j k j k j ! ) = ∑ k 1 , … , k m ≥ 0 x 1 k 1 ⋯ x m k m k 1 ! ⋯ k m ! . G(x_1,\ldots,x_m)=\prod_{j=1}^{m}\left(\sum_{k_j\ge0}\frac{x_j^{k_j}}{k_j!}\right)=\sum_{k_1,\ldots,k_m\ge0}\frac{x_1^{k_1}\cdots x_m^{k_m}}{k_1!\cdots k_m!}. G ( x 1 , … , x m ) = j = 1 ∏ m k j ≥ 0 ∑ k j ! x j k j = k 1 , … , k m ≥ 0 ∑ k 1 ! ⋯ k m ! x 1 k 1 ⋯ x m k m . Therefore, the sum of the coefficients of all monomials of total degree L L L in this expansion is exactly
∑ k ∈ Z ≥ 0 m k 1 + ⋯ + k m = L 1 k 1 ! ⋯ k m ! . \sum_{\substack{\boldsymbol{k}\in\mathbb{Z}_{\ge0}^{m}\\ k_1+\cdots+k_m=L}}\frac{1}{k_1!\cdots k_m!}. k ∈ Z ≥ 0 m k 1 + ⋯ + k m = L ∑ k 1 ! ⋯ k m ! 1 . On the other hand, since e x 1 ⋯ e x m = e x 1 + ⋯ + x m e^{x_1}\cdots e^{x_m}=e^{x_1+\cdots+x_m} e x 1 ⋯ e x m = e x 1 + ⋯ + x m , substituting x 1 = ⋯ = x m = x x_1=\cdots=x_m=x x 1 = ⋯ = x m = x yields
G ( x , … , x ) = e m x . G(x,\ldots,x)=e^{mx}. G ( x , … , x ) = e m x . The coefficient of x L x^L x L in the Taylor expansion of e m x e^{mx} e m x is m L / L ! m^L/L! m L / L ! . This coefficient is exactly the sum of the coefficients of all monomials of total degree L L L in the multivariate expansion of G G G , since each such monomial becomes x L x^L x L under the substitution x 1 = ⋯ = x m = x x_1=\cdots=x_m=x x 1 = ⋯ = x m = x . Combining the two expressions for this coefficient completes the proof.
Using Claim 3.13 , we bound the expected number of query paths agreeing with some s ∈ S s\in\mathcal{S} s ∈ S by,
∑ L ≥ 1 f ( L , Δ ) ⋅ m L L ! = Δ C 2 ⋅ ∑ L ≥ 1 ( C 1 ) L ⋅ m L L ! = Δ C 2 ⋅ ∑ L ≥ 1 ( C 1 ⋅ m ) L L ! = Δ C 2 ⋅ ( e C 1 ⋅ m − 1 ) < ( Δ ) ( log 2 e ) ⋅ C 1 + C 2 . \begin{aligned}
\sum_{L\ge1}f(L,\Delta)\cdot\frac{m^L}{L!}
=
\Delta^{C_2}\cdot\sum_{L\ge1}(C_1)^L\cdot\frac{m^L}{L!}
=
\Delta^{C_2}\cdot\sum_{L\ge1}\frac{(C_1\cdot m)^L}{L!} \\
&=\Delta^{C_2}\cdot\left(e^{C_1\cdot m}-1\right)<(\Delta)^{(\log_2 e)\cdot C_1+C_2}.
\end{aligned} L ≥ 1 ∑ f ( L , Δ ) ⋅ L ! m L = Δ C 2 ⋅ L ≥ 1 ∑ ( C 1 ) L ⋅ L ! m L = Δ C 2 ⋅ L ≥ 1 ∑ L ! ( C 1 ⋅ m ) L = Δ C 2 ⋅ ( e C 1 ⋅ m − 1 ) < ( Δ ) ( l o g 2 e ) ⋅ C 1 + C 2 .
and obtain the desired upper bound on the expected number of query paths agreeing with sequences s ∈ S s\in\mathcal{S} s ∈ S . It remains to argue about paths to vertices with rank smaller than τ ( m ) \tau(m) τ ( m ) . For such vertices, the probability that the rank falls in the range [ 0 , τ ( m ) ) [0,\tau(m)) [ 0 , τ ( m )) is at most Δ − 1 \Delta^{-1} Δ − 1 , so by linearity of expectation, the expected number of such monotone paths from every vertex is at most ∑ L ≥ 0 Δ L ⋅ Δ − L / L ! = e \sum_{L\ge0}\Delta^L\cdot\Delta^{-L}/L!=e ∑ L ≥ 0 Δ L ⋅ Δ − L / L ! = e .
One can consider these paths to be independent of whether the root of the path is queried by RGMIS as Algorithm 1 is essentially a depth-first search on the tree and when a vertex v v v is visited for the first time, none of its descendants have been visited and their ranks uninspected. In Section A.1, Lemma A.2 we show formally that such paths can only increase the expected value by a factor of e e e . Finally, observe that for every vertex v v v in the query tree, the unique path from u 0 u_0 u 0 to v v v is a query path. Conversely for every query path P P P , the end of the path P P P is a vertex in the query tree. Thus the number of query paths is equivalent to the size of the query tree.
Upper bound on the number of candidate paths
In this section we prove Lemma 3.12 which is the most technical part of the paper. Recall that Lemma 3.12 bounds the expected number of candidate paths agreeing with a fixed s ∈ S ( L ) s \in S(L) s ∈ S ( L ) . At a high level, the argument is as follows. We show that the probability that the size of the candidate set A θ ( u ) A_\theta(u) A θ ( u ) exceeds a constant is small. Thus, for a typical vertex u u u , the set A θ ( u ) A_\theta(u) A θ ( u ) contains only a constant number of children of u u u . If we had ∣ A θ ( u ) ∣ ≤ O ( 1 ) |A_\theta(u)| \le O(1) ∣ A θ ( u ) ∣ ≤ O ( 1 ) for all vertices u u u , then we could upper bound the number of candidate paths by exp ( O ( L ) ) \exp(O(L)) exp ( O ( L )) , which would conclude the proof.
Unfortunately, for some vertices u u u the size ∣ A θ ( u ) ∣ |A_\theta(u)| ∣ A θ ( u ) ∣ may be large, and moreover the sizes of A θ ( u ′ ) A_\theta(u') A θ ( u ′ ) and A θ ( u ′ ′ ) A_\theta(u'') A θ ( u ′′ ) are not necessarily independent for u ′ ≠ u ′ ′ u' \ne u'' u ′ = u ′′ . In this subsection, we show how to nevertheless upper bound the expected number of candidate paths agreeing with s s s .
We begin by upper bounding the probability that ∣ A θ ( u ) ∣ |A_\theta(u)| ∣ A θ ( u ) ∣ is large. The bound holds even if the ranks of some children of u u u are partially revealed.
Lemma 4.1. Let s ∈ S ( L ) s \in S(L) s ∈ S ( L ) . For every vertex u u u in the tree with δ ( u ) < L − 1 \delta(u) < L-1 δ ( u ) < L − 1 , every θ ≤ τ ( s δ ( u ) + 2 ) / 2 \theta\le\tau(s_{\delta(u)+2})/2 θ ≤ τ ( s δ ( u ) + 2 ) /2 , and every T > 1 T > 1 T > 1 , the following holds. We define T θ ( u ) \mathcal{T}_\theta(u) T θ ( u ) to be the set of the following random variables.
T θ ( u ) = { r ( v ) ∣ v ∈ T w for some w ∈ Γ ( u ) with r ( w ) < θ } \mathcal{T}_\theta(u) = \{r(v) \mid v \in\mathcal{T}_w \text{ for some } w \in\Gamma(u) \text{ with } r(w) < \theta\} T θ ( u ) = { r ( v ) ∣ v ∈ T w for some w ∈ Γ ( u ) with r ( w ) < θ } Let E \mathcal{E} E be any event that depends only on the ranks in T θ ( u ) \mathcal{T}_\theta(u) T θ ( u ) . Note that this implies that every child w ∈ Γ ( u ) ∖ T θ ( u ) w \in\Gamma(u) \setminus\mathcal{T}_\theta(u) w ∈ Γ ( u ) ∖ T θ ( u ) has r ( w ) ≥ θ r(w) \ge\theta r ( w ) ≥ θ and that no other information about the ranks of vertices in T w \mathcal{T}_w T w is needed to determine E \mathcal{E} E . Then it holds that,
Pr ( ∣ A 2 θ ( u ) ∣ ≥ T ∣ E ) ≤ exp ( − T τ ( s δ ( u ) + 1 ) θ + 1 ) . (2) \Pr\left(|A_{2\theta}(u)| \ge T \mid\mathcal{E}\right) \le\exp\left(-\frac{T}{\frac{\tau(s_{\delta(u)+1})}{\theta}+1}\right). \tag*{(2)} Pr ( ∣ A 2 θ ( u ) ∣ ≥ T ∣ E ) ≤ exp ( − θ τ ( s δ ( u ) + 1 ) + 1 T ) . (2)
In Lemma 4.1, T T T is an arbitrary positive number. However, we may assume without loss of generality that T T T is an integer by replacing it with ⌈ T ⌉ \lceil T\rceil ⌈ T ⌉ . Indeed, this does not change the probability on the left-hand side, since ∣ A 2 θ ( u ) ∣ |A_{2\theta}(u)| ∣ A 2 θ ( u ) ∣ is always integral, while the expression on the right-hand side only decreases. Hence, from now on we assume that T ∈ Z ≥ 0 T \in\mathbb{Z}_{\ge0} T ∈ Z ≥ 0 .
To prove this lemma, we first detour through a small probabilistic puzzle. Imagine a game in which a player repeatedly draws (with replacement) from a bag containing three types of tokens labeled 1, 2, and 3. Each draw is independent: the probability of drawing a 1 is p 1 p_1 p 1 , of drawing a 2 is p 2 p_2 p 2 , and of drawing a 3 is p 3 p_3 p 3 , with p 1 + p 2 + p 3 = 1 p_1 + p_2 + p_3 = 1 p 1 + p 2 + p 3 = 1 . The player makes n n n draws.
We are interested in the probability that, among these n n n draws, the player observes at least T T T tokens labeled 1 and no tokens labeled 2. This probability clearly depends on T T T , n n n , and the parameters p 1 , p 2 , p 3 p_1,p_2,p_3 p 1 , p 2 , p 3 . However, we would like a clean upper bound that depends only on T T T and on the ratio λ = p 1 / ( p 1 + p 2 ) \lambda= p_1/(p_1+p_2) λ = p 1 / ( p 1 + p 2 ) . Thus, the question is: for fixed T T T and λ \lambda λ , and arbitrary p 1 , p 2 , p 3 p_1,p_2,p_3 p 1 , p 2 , p 3 satisfying λ = p 1 / ( p 1 + p 2 ) \lambda= p_1/(p_1+p_2) λ = p 1 / ( p 1 + p 2 ) and n ≥ T n \ge T n ≥ T , how large can this probability be?
It is not hard to see (and we will prove formally) that the probability is maximized when there are no 3’s and we take exactly n = T n=T n = T draws; that is, when p 1 = λ p_1=\lambda p 1 = λ , p 2 = 1 − λ p_2=1-\lambda p 2 = 1 − λ , p 3 = 0 p_3=0 p 3 = 0 , and n = T n=T n = T . In this case, the event “at least T T T ones and no twos” simply means “all T T T draws are 1”, which has probability λ T \lambda^T λ T . In the remainder of the argument, we show that λ T \lambda^T λ T is indeed an upper bound for every admissible choice of p 1 , p 2 , p 3 p_1,p_2,p_3 p 1 , p 2 , p 3 and every n ≥ T n \ge T n ≥ T . There are several ways to derive this inequality—for example, via a standard martingale or stopping-time argument—but here we present a more elementary probabilistic proof.
Claim 4.2. Let X 1 , … , X n X_1,\ldots,X_n X 1 , … , X n be i.i.d. random variables taking values in { 1 , 2 , 3 } \{1,2,3\} { 1 , 2 , 3 } with Pr ( X = 1 ) = p 1 \Pr(X=1)=p_1 Pr ( X = 1 ) = p 1 , Pr ( X = 2 ) = p 2 \Pr(X=2)=p_2 Pr ( X = 2 ) = p 2 , and Pr ( X = 3 ) = p 3 \Pr(X=3)=p_3 Pr ( X = 3 ) = p 3 , where p 1 + p 2 + p 3 = 1 p_1+p_2+p_3=1 p 1 + p 2 + p 3 = 1 . Then for any positive integer T T T ,
Pr ( ∣ { i : X i = 1 } ∣ ≥ T and ∣ { i : X i = 2 } ∣ = 0 ) ≤ ( p 1 p 1 + p 2 ) T \Pr\left(\left|\{i:X_i=1\}\right|\ge T\ \text{and}\ \left|\{i:X_i=2\}\right|=0\right)\le\left(\frac{p_1}{p_1+p_2}\right)^T Pr ( ∣ { i : X i = 1 } ∣ ≥ T and ∣ { i : X i = 2 } ∣ = 0 ) ≤ ( p 1 + p 2 p 1 ) T
Proof. Let X = { i : X i ∈ { 1 , 2 } } \mathcal{X}=\{i:X_i\in\{1,2\}\} X = { i : X i ∈ { 1 , 2 }} . Then the event
∣ { i : X i = 1 } ∣ ≥ T and ∣ { i : X i = 2 } ∣ = 0 \left|\{i:X_i=1\}\right|\ge T\quad\text{and}\quad\left|\{i:X_i=2\}\right|=0 ∣ { i : X i = 1 } ∣ ≥ T and ∣ { i : X i = 2 } ∣ = 0
is equivalent to the event that ∣ X ∣ ≥ T |\mathcal{X}|\ge T ∣ X ∣ ≥ T and X i = 1 X_i=1 X i = 1 for all i ∈ X i\in\mathcal{X} i ∈ X .
We condition on the random set X \mathcal{X} X . Conditional on X \mathcal{X} X , the random variables { X i : i ∈ X } \{X_i:i\in\mathcal{X}\} { X i : i ∈ X } are i.i.d. with
Pr ( X i = 1 ∣ i ∈ X ) = p 1 p 1 + p 2 . \Pr(X_i=1\mid i\in\mathcal{X})=\frac{p_1}{p_1+p_2}. Pr ( X i = 1 ∣ i ∈ X ) = p 1 + p 2 p 1 .
Therefore, the conditional probability that X i = 1 X_i=1 X i = 1 for all i ∈ X i\in\mathcal{X} i ∈ X and ∣ X ∣ ≥ T |\mathcal{X}|\ge T ∣ X ∣ ≥ T is
( p 1 p 1 + p 2 ) ∣ X ∣ 1 { ∣ X ∣ ≥ T } ≤ ( p 1 p 1 + p 2 ) T . \left(\frac{p_1}{p_1+p_2}\right)^{|\mathcal{X}|}\mathbf{1}\{|\mathcal{X}|\ge T\}\le\left(\frac{p_1}{p_1+p_2}\right)^T. ( p 1 + p 2 p 1 ) ∣ X ∣ 1 { ∣ X ∣ ≥ T } ≤ ( p 1 + p 2 p 1 ) T .
Taking expectation over X \mathcal{X} X completes the proof. □
Proof of Lemma 4.1. Let Y u Y_u Y u denote the set of all children of u u u that are promising at threshold 2 θ 2\theta 2 θ . This is a random set. Observe that Y u Y_u Y u is independent of the ranks of the children of u u u , since the event that a vertex v v v is promising at threshold 2 θ 2\theta 2 θ is completely determined by the ranks of vertices in the subtree rooted at v v v , excluding the rank of v v v itself.
The candidate set A 2 θ ( u ) A_{2\theta}(u) A 2 θ ( u ) is empty if there exists a vertex v ∈ Y u v\in Y_u v ∈ Y u whose rank lies in the interval [ 0 , 2 θ ) [0,2\theta) [ 0 , 2 θ ) . If A 2 θ ( u ) A_{2\theta}(u) A 2 θ ( u ) is non-empty then,
A 2 θ ( u ) = { v ∈ Y u : r ( v ) ∈ [ τ ( s δ ( u ) + 1 ) , τ ( s δ ( u ) + 1 − 1 ) ) } . A_{2\theta}(u)=\{v\in Y_u:r(v)\in[\tau(s_{\delta(u)+1}),\tau(s_{\delta(u)+1}-1))\}. A 2 θ ( u ) = { v ∈ Y u : r ( v ) ∈ [ τ ( s δ ( u ) + 1 ) , τ ( s δ ( u ) + 1 − 1 ))} .
Hence the event ∣ A 2 θ ( u ) ∣ ≥ T |A_{2\theta}(u)|\ge T ∣ A 2 θ ( u ) ∣ ≥ T for T > 0 T>0 T > 0 implies that there are at least T T T vertices v ∈ Y u v\in Y_u v ∈ Y u with
r ( v ) ∈ [ τ ( s δ ( u ) + 1 ) , τ ( s δ ( u ) + 1 − 1 ) ) , r(v)\in[\tau(s_{\delta(u)+1}),\tau(s_{\delta(u)+1}-1)), r ( v ) ∈ [ τ ( s δ ( u ) + 1 ) , τ ( s δ ( u ) + 1 − 1 )) ,
and no vertices v ∈ Y u v\in Y_u v ∈ Y u with
r ( v ) ∈ [ 0 , 2 θ ) . r(v)\in[0,2\theta). r ( v ) ∈ [ 0 , 2 θ ) .
We condition on the set Y u Y_u Y u . If there exists a vertex v ∈ Y u v\in Y_u v ∈ Y u whose rank is fixed by the event E \mathcal{E} E and satisfies r ( v ) < θ r(v)<\theta r ( v ) < θ , then r ( v ) ∈ [ 0 , 2 θ ) r(v)\in[0,2\theta) r ( v ) ∈ [ 0 , 2 θ ) , and hence A 2 θ ( u ) = ∅ A_{2\theta}(u)=\varnothing A 2 θ ( u ) = ∅ . Otherwise, if no such vertex exists, then, conditioned on T θ ( u ) ∪ Y u \mathcal{T}_{\theta}(u)\cup Y_u T θ ( u ) ∪ Y u , the ranks { r ( v ) : v ∈ Y u } \{r(v):v\in Y_u\} { r ( v ) : v ∈ Y u } are i.i.d. uniformly distributed over [ θ , 1 ) [\theta,1) [ θ , 1 ) . Note that E \mathcal{E} E is determined by T θ ( u ) \mathcal{T}_{\theta}(u) T θ ( u ) , so the above conditioning is stronger than the conditioning on E \mathcal{E} E and any bound we derive holds for the conditioning E ∪ Y u \mathcal{E}\cup Y_u E ∪ Y u as well.
We now apply Claim 4.2 . For each v ∈ Y u v\in Y_u v ∈ Y u , define
X v = { 1 , if r ( v ) ∈ [ τ ( s δ ( u ) + 1 ) , τ ( s δ ( u ) + 1 − 1 ) ) , 2 , if r ( v ) ∈ [ θ , 2 θ ) , 3 , otherwise. X_v=
\begin{cases}
1, & \text{if }r(v)\in[\tau(s_{\delta(u)+1}),\tau(s_{\delta(u)+1}-1)),\\
2, & \text{if }r(v)\in[\theta,2\theta),\\
3, & \text{otherwise.}
\end{cases} X v = ⎩ ⎨ ⎧ 1 , 2 , 3 , if r ( v ) ∈ [ τ ( s δ ( u ) + 1 ) , τ ( s δ ( u ) + 1 − 1 )) , if r ( v ) ∈ [ θ , 2 θ ) , otherwise.
Conditional on the set Y u Y_u Y u , the random variables { X v : v ∈ Y u } \{X_v : v \in Y_u\} { X v : v ∈ Y u } are i.i.d. in [ θ , 1 ) [\theta,1) [ θ , 1 ) , with
p 1 = Pr ( X v = 1 ) = τ ( s δ ( u ) + 1 ) ⋅ ( 1 − θ ) − 1 , p 2 = Pr ( X v = 2 ) = θ ⋅ ( 1 − θ ) − 1 , p_1 = \Pr(X_v = 1) = \tau(s_{\delta(u)}+1)\cdot(1-\theta)^{-1}, \qquad p_2 = \Pr(X_v = 2) = \theta\cdot(1-\theta)^{-1}, p 1 = Pr ( X v = 1 ) = τ ( s δ ( u ) + 1 ) ⋅ ( 1 − θ ) − 1 , p 2 = Pr ( X v = 2 ) = θ ⋅ ( 1 − θ ) − 1 ,
and p 3 = 1 − p 1 − p 2 p_3 = 1-p_1-p_2 p 3 = 1 − p 1 − p 2 .
By Claim 4.2 , we have
Pr ( ∣ { v ∈ Y u : X v = 1 } ∣ > T and ∣ { v ∈ Y u : X v = 2 } ∣ = 0 ∣ Y u ) ≤ ( p 1 p 1 + p 2 ) T . \Pr\left(\left|\{v\in Y_u:X_v=1\}\right|>T\text{ and }\left|\{v\in Y_u:X_v=2\}\right|=0\mathrel{\Big|}Y_u\right)\leq\left(\frac{p_1}{p_1+p_2}\right)^T. Pr ( ∣ { v ∈ Y u : X v = 1 } ∣ > T and ∣ { v ∈ Y u : X v = 2 } ∣ = 0 Y u ) ≤ ( p 1 + p 2 p 1 ) T .
Since
p 1 p 1 + p 2 = τ ( s δ ( u ) + 1 ) τ ( s δ ( u ) + 1 ) + θ = 1 − 1 τ ( s δ ( u ) + 1 ) θ + 1 , \frac{p_1}{p_1+p_2}=\frac{\tau(s_{\delta(u)}+1)}{\tau(s_{\delta(u)}+1)+\theta}=1-\frac{1}{\frac{\tau(s_{\delta(u)}+1)}{\theta}+1}, p 1 + p 2 p 1 = τ ( s δ ( u ) + 1 ) + θ τ ( s δ ( u ) + 1 ) = 1 − θ τ ( s δ ( u ) + 1 ) + 1 1 ,
it follows that
( p 1 p 1 + p 2 ) T = ( 1 − 1 τ ( s δ ( u ) + 1 ) θ + 1 ) T ≤ exp ( − T τ ( s δ ( u ) + 1 ) θ + 1 ) . \left(\frac{p_1}{p_1+p_2}\right)^T=\left(1-\frac{1}{\frac{\tau(s_{\delta(u)}+1)}{\theta}+1}\right)^T\leq\exp\left(-\frac{T}{\frac{\tau(s_{\delta(u)}+1)}{\theta}+1}\right). ( p 1 + p 2 p 1 ) T = ( 1 − θ τ ( s δ ( u ) + 1 ) + 1 1 ) T ≤ exp ( − θ τ ( s δ ( u ) + 1 ) + 1 T ) .
This bound holds uniformly over all realizations of Y u Y_u Y u . Removing the conditioning on Y u Y_u Y u , we conclude that
Pr ( ∣ A 2 θ ( u ) ∣ ≥ T ∣ E ) ≤ Pr ( ∣ A 2 θ ( u ) ∣ ≥ T ∣ T θ ( u ) ) ≤ exp ( − T τ ( s δ ( u ) + 1 ) θ + 1 ) , \Pr\left(|A_{2\theta}(u)|\geq T\mid\mathcal{E}\right)\leq\Pr\left(|A_{2\theta}(u)|\geq T\mid\mathcal{T}_\theta(u)\right)\leq\exp\left(-\frac{T}{\frac{\tau(s_{\delta(u)}+1)}{\theta}+1}\right), Pr ( ∣ A 2 θ ( u ) ∣ ≥ T ∣ E ) ≤ Pr ( ∣ A 2 θ ( u ) ∣ ≥ T ∣ T θ ( u ) ) ≤ exp ( − θ τ ( s δ ( u ) + 1 ) + 1 T ) ,
as claimed.
Path Encoding
We now define a path encoding. To this end, we first introduce some notation. We begin by fixing an arbitrary but consistent ordering of the children of each vertex. Specifically, for every vertex u u u , we assume that the children in Γ ( u ) \Gamma(u) Γ ( u ) are numbered from 0 0 0 to ∣ Γ ( u ) ∣ − 1 |\Gamma(u)|-1 ∣Γ ( u ) ∣ − 1 . While the particular ordering is not important, we require it to be fixed once and for all.
Next, for the fixed sequence s s s , we define the scale ratio at level i i i by
ρ s ( i ) = τ ( s i ) τ ( s i + 1 ) = 2 s i + 1 − s i . \rho_s(i)=\frac{\tau(s_i)}{\tau(s_{i+1})}=2^{s_{i+1}-s_i}. ρ s ( i ) = τ ( s i + 1 ) τ ( s i ) = 2 s i + 1 − s i .
Since s s s is non-decreasing, we have s i ≤ s i + 1 s_i\leq s_{i+1} s i ≤ s i + 1 for all i i i , and consequently ρ s ( i ) ≥ 1 \rho_s(i)\geq1 ρ s ( i ) ≥ 1 .
We also define a sequence { κ z } z ≥ 0 \{\kappa_z\}_{z\geq0} { κ z } z ≥ 0 by
κ z = 5 ⋅ ( z + 1 ) ⋅ 2 z + 1 . \kappa_z=5\cdot(z+1)\cdot2^{z+1}. κ z = 5 ⋅ ( z + 1 ) ⋅ 2 z + 1 .
The encoding describes how to traverse a candidate path by specifying, at each step, how the next vertex is selected from an appropriate candidate set. For each step i i i , the encoding includes three parameters: z i z_i z i , which determines the threshold used to define the candidate set; a i a_i a i , which selects a particular child from this set; and f i f_i f i , which serves as an auxiliary flag used to control steps where the candidate set is unusually large.
Intuition. In the encoding, we use a sequence of candidate sets corresponding to decreasing values of the threshold θ i \theta_i θ i . The candidate set indexed by z z z is defined using the threshold θ i = τ ( s i + 2 + z ) \theta_i = \tau(s_{i+2} + z) θ i = τ ( s i + 2 + z ) . We use the candidate set with index z z z only if its size is bounded by approximately κ z \kappa^z κ z (more precisely, κ z ρ s ( i + 1 ) \kappa^z\rho_s(i + 1) κ z ρ s ( i + 1 ) ). In particular, if we use the candidate set with z = 0 z = 0 z = 0 , then the number of options for a i a_i a i is bounded by κ 0 = 10 \kappa^0 = 10 κ 0 = 10 (up to the factor ρ s ( i + 1 ) \rho_s(i + 1) ρ s ( i + 1 ) ). This choice of z z z is therefore preferable for the encoding. However, it is not always feasible: if the candidate set at this threshold is too large, we must increase z z z and decrease the threshold in order to satisfy the required size bound. Lowering the threshold enlarges the candidate set, and thus increases the number of possible values of a i a_i a i , but allows the construction to proceed.
To control such events, we later apply Lemma 4.1 to argue that, in a κ \kappa κ -bounded encoding representing at least one candidate path, it is unlikely that the sum of the values z i z_i z i is large. To facilitate this analysis, we use the flags f i f_i f i to mark positions where the threshold must be decreased. More precisely, f i = 1 f_i = 1 f i = 1 indicates that the threshold θ i \theta_i θ i cannot be increased (i.e., z i z_i z i cannot be reduced) without violating the size bound on the candidate set. This corresponds to the condition ∣ A 2 θ i ( u i ) ∣ > κ z i − 1 ρ s ( i + 1 ) \lvert A_{2\theta_i}(u_i)\rvert> \kappa^{z_i-1}\rho_s(i + 1) ∣ A 2 θ i ( u i )∣ > κ z i − 1 ρ s ( i + 1 ) (when z i ≥ 1 z_i \ge1 z i ≥ 1 ).
Definition 4.3 (κ \kappa κ -bounded path encoding). A κ \kappa κ -bounded path encoding of length L L L is a sequence of triplets
( z 0 , a 0 , f 0 ) , … , ( z L − 3 , a L − 3 , f L − 3 ) , (z_0, a_0, f_0), \ldots, (z_{L-3}, a_{L-3}, f_{L-3}), ( z 0 , a 0 , f 0 ) , … , ( z L − 3 , a L − 3 , f L − 3 ) , where z i ∈ Z ≥ 0 z_i \in\mathbb{Z}_{\ge0} z i ∈ Z ≥ 0 , a i ∈ Z ≥ 0 a_i \in\mathbb{Z}_{\ge0} a i ∈ Z ≥ 0 , and f i ∈ { 0 , 1 } f_i \in\{0,1\} f i ∈ { 0 , 1 } . For each i < L − 2 i < L - 2 i < L − 2 , define
θ i = τ ( s i + 2 + z i ) . \theta_i = \tau(s_{i+2} + z_i). θ i = τ ( s i + 2 + z i ) . The triplets must satisfy the following conditions:
For each i i i , we have
a i ≤ κ z i ρ s ( i + 1 ) . a_i \le\kappa^{z_i}\rho_s(i + 1). a i ≤ κ z i ρ s ( i + 1 ) . If f i = 1 f_i = 1 f i = 1 , then z i > 0 z_i > 0 z i > 0 .
If f i = 1 f_i = 1 f i = 1 and i ≥ 1 i \ge1 i ≥ 1 , then θ i − 1 ≤ θ i \theta_{i-1} \le\theta_i θ i − 1 ≤ θ i and f i − 1 = 0 f_{i-1} = 0 f i − 1 = 0 .
For all i ≤ L − 3 i \le L - 3 i ≤ L − 3 , if z i > 0 z_i > 0 z i > 0 , then at least one of the following holds:
(a) f i = 1 f_i = 1 f i = 1 ;
(b) f i − 1 = 1 f_{i-1} = 1 f i − 1 = 1 and z i ≤ z i − 1 z_i \le z_{i-1} z i ≤ z i − 1 ; or
(c) f i + 1 = 1 f_{i+1} = 1 f i + 1 = 1 and z i ≤ z i + 1 + s i + 3 − s i + 2 z_i \le z_{i+1} + s_{i+3} - s_{i+2} z i ≤ z i + 1 + s i + 3 − s i + 2 .
To simplify the treatment of boundary conditions, we set f − 1 = 0 f_{-1} = 0 f − 1 = 0 and f L − 2 = 0 f_{L-2} = 0 f L − 2 = 0 .
Remark. If f i + 1 = 1 f_{i+1} = 1 f i + 1 = 1 , then by condition (C) we have θ i ≤ θ i + 1 \theta_i \le\theta_{i+1} θ i ≤ θ i + 1 , and hence s i + 2 + z i ≥ s i + 3 + z i + 1 s_{i+2} + z_i \ge s_{i+3} + z_{i+1} s i + 2 + z i ≥ s i + 3 + z i + 1 . This implies that in item D.c. the inequality can be replaced by equality, i.e., z i = z i + 1 + s i + 3 − s i + 2 z_i = z_{i+1} + s_{i+3} - s_{i+2} z i = z i + 1 + s i + 3 − s i + 2 .
Definition 4.4. We say that a κ \kappa κ -bounded path encoding { ( z i , a i , f i ) } \{(z_i, a_i, f_i)\} {( z i , a i , f i )} represents the candidate path u 0 , … , u L − 1 u_0, \ldots, u_{L-1} u 0 , … , u L − 1 agreeing with a sequence s s s if, for every i < L − 2 i < L - 2 i < L − 2 , the following conditions hold:
u i + 1 u_{i+1} u i + 1 is the a i a_i a i -th element of A θ i ( u i ) A_{\theta_i}(u_i) A θ i ( u i ) , where the set is ordered according to the fixed ordering of the children, with indices starting from 1;
if f i = 1 f_i = 1 f i = 1 , then
∣ A 2 θ i ( u i ) ∣ > κ z i − 1 ρ s ( i + 1 ) , \lvert A_{2\theta_i}(u_i)\rvert> \kappa_{z_{i-1}}\rho_s(i + 1), ∣ A 2 θ i ( u i )∣ > κ z i − 1 ρ s ( i + 1 ) ,
where θ i = τ ( s i + 2 + z i ) \theta_i = \tau(s_{i+2} + z_i) θ i = τ ( s i + 2 + z i ) .
We prove that every candidate path is represented by at least one κ \kappa κ -bounded path encoding, and that each encoding represents at most Δ \Delta Δ candidate paths. The Δ \Delta Δ factor appears because the Decode&Verify procedure decodes all vertices except for the last. We then show that the probability that a fixed encoding { ( z i , a i , f i ) } \{(z_i, a_i, f_i)\} {( z i , a i , f i )} corresponds to a candidate path is at most poly ( Δ ) ⋅ exp ( − ∑ z i ) \operatorname{poly}(\Delta) \cdot\exp(-\sum z_i) poly ( Δ ) ⋅ exp ( − ∑ z i ) .
Lemma 4.5. Every candidate path is represented by at least one κ \kappa κ -bounded path encoding.
Proof. Consider a candidate path u 0 , … , u L − 1 u_0, \ldots, u_{L-1} u 0 , … , u L − 1 . For every i < L − 2 i < L - 2 i < L − 2 , let z i ⋆ z_i^\star z i ⋆ be the smallest integer such that for every z ≥ z i ⋆ z \ge z_i^\star z ≥ z i ⋆ , the following bound holds:
∣ A τ ( s i + 2 + z ) ( u i ) ∣ ≤ κ z ρ s ( i + 1 ) . (3) \lvert A_{\tau(s_{i+2}+z)}(u_i)\rvert\le\kappa_z\rho_s(i + 1). \tag*{(3)} ∣ A τ ( s i + 2 + z ) ( u i )∣ ≤ κ z ρ s ( i + 1 ) . (3) Note that such z i ⋆ z_i^\star z i ⋆ exists, since for sufficiently large z z z we have κ z ≥ Δ \kappa_z \ge\Delta κ z ≥ Δ , while ∣ A τ ( s i + 2 ) + z ( u i ) ∣ ≤ Δ \lvert A_{\tau(s_{i+2})+z}(u_i)\rvert\le\Delta ∣ A τ ( s i + 2 ) + z ( u i )∣ ≤ Δ , as u i u_i u i has at most Δ \Delta Δ children.
We construct a subset F ⊆ { 0 , 1 , … , L − 2 } F \subseteq\{0, 1, \ldots, L - 2\} F ⊆ { 0 , 1 , … , L − 2 } satisfying the following properties:
if i ∈ F i \in F i ∈ F , then z i ⋆ > 0 z_i^\star> 0 z i ⋆ > 0 and i + 1 ∉ F i + 1 \notin F i + 1 ∈ / F ;
if z i ⋆ > 0 z_i^\star> 0 z i ⋆ > 0 , then at least one of the following holds: (1) i ∈ F i \in F i ∈ F ; (2) i − 1 ∈ F i - 1 \in F i − 1 ∈ F and z i − 1 ⋆ ≥ z i ⋆ z_{i-1}^\star\ge z_i^\star z i − 1 ⋆ ≥ z i ⋆ ; or (3) i + 1 ∈ F i + 1 \in F i + 1 ∈ F and z i + 1 ⋆ ≥ z i ⋆ z_{i+1}^\star\ge z_i^\star z i + 1 ⋆ ≥ z i ⋆ .
Claim 4.6. There exists a set F F F satisfying the above properties.
Proof. We construct F F F greedily as follows. Consider all indices i i i with z i ⋆ > 0 z_i^\star> 0 z i ⋆ > 0 , sorted in non-increasing order of z i ⋆ z_i^\star z i ⋆ . Process these indices one by one, and add i i i to F F F if neither of its neighbors, i − 1 i - 1 i − 1 nor i + 1 i + 1 i + 1 , has already been added to F F F .
By construction, F F F is an independent set, so if i ∈ F i \in F i ∈ F , then i + 1 ∉ F i + 1 \notin F i + 1 ∈ / F , establishing the first property. For the second property, fix i i i with z i ⋆ > 0 z_i^\star> 0 z i ⋆ > 0 . If i ∈ F i \in F i ∈ F , we are done. Otherwise, i i i was not added because at least one of its neighbors was already in F F F ; let j ∈ { i − 1 , i + 1 } j \in\{i - 1, i + 1\} j ∈ { i − 1 , i + 1 } be such a neighbor. Since j j j was processed no later than i i i , we have z j ⋆ ≥ z i ⋆ z_j^\star\ge z_i^\star z j ⋆ ≥ z i ⋆ , establishing the claim.
We now construct an encoding ( z 0 , a 0 , f 0 ) , … , ( z L − 3 , a L − 3 , f L − 3 ) (z_0, a_0, f_0), \ldots, (z_{L-3}, a_{L-3}, f_{L-3}) ( z 0 , a 0 , f 0 ) , … , ( z L − 3 , a L − 3 , f L − 3 ) using a set F F F as above. For every i ∈ F i \in F i ∈ F , we set f i = 1 f_i = 1 f i = 1 and let z i = z i ⋆ z_i = z_i^\star z i = z i ⋆ . For i ∉ F i \notin F i ∈ / F , we set f i = 0 f_i = 0 f i = 0 . If i ∉ F i \notin F i ∈ / F and i + 1 ∉ F i + 1 \notin F i + 1 ∈ / F , we let z i = z i ⋆ z_i = z_i^\star z i = z i ⋆ ; otherwise, if i ∉ F i \notin F i ∈ / F and i + 1 ∈ F i + 1 \in F i + 1 ∈ F , we let z i = max ( z i ⋆ , z i + 1 ⋆ + s i + 3 − s i + 2 ) z_i = \max(z_i^\star, z_{i+1}^\star+ s_{i+3} - s_{i+2}) z i = max ( z i ⋆ , z i + 1 ⋆ + s i + 3 − s i + 2 ) . As in the definition of a κ \kappa κ -bounded path encoding, we set θ i = τ ( s i + 2 + z i ) \theta_i = \tau(s_{i+2} + z_i) θ i = τ ( s i + 2 + z i ) . Finally, we let a i a_i a i be the index of vertex u i + 1 u_{i+1} u i + 1 in the candidate set A θ i ( u i ) A_{\theta_i}(u_i) A θ i ( u i ) according to the fixed ordering of the children of u i u_i u i .
We now verify that the constructed encoding is valid and that it represents the candidate path ( u 0 , … , u L − 2 ) (u_0, \ldots, u_{L-2}) ( u 0 , … , u L − 2 ) . We begin by checking that the size constraints are satisfied. First observe that z i ≥ z i ⋆ z_i \ge z_i^\star z i ≥ z i ⋆ for all i i i . Thus, by the definition of z i ⋆ z_i^\star z i ⋆ , we have
∣ A θ i ( u i ) ∣ ≤ ∣ A τ ( s i + 2 + z i ) ( u i ) ∣ ≤ κ z i ρ s ( i + 1 ) . \lvert A_{\theta_i}(u_i)\rvert\le\lvert A_{\tau(s_{i+2}+z_i)}(u_i)\rvert\le\kappa_{z_i}\rho_s(i + 1). ∣ A θ i ( u i )∣ ≤ ∣ A τ ( s i + 2 + z i ) ( u i )∣ ≤ κ z i ρ s ( i + 1 ) .
Consequently,
a i ≤ κ z i ρ s ( i + 1 ) . a_i \le\kappa_{z_i}\rho_s(i + 1). a i ≤ κ z i ρ s ( i + 1 ) .
Next, we verify the monotonicity condition on the thresholds. Suppose that f i = 1 f_i = 1 f i = 1 and i ≥ 1 i \ge1 i ≥ 1 . Then f i − 1 = 0 f_{i-1} = 0 f i − 1 = 0 by the properties of F F F . Moreover,
z i − 1 = max ( z i − 1 ⋆ , z i ⋆ + s i + 2 − s i + 1 ) ≥ z i ⋆ + s i + 2 − s i + 1 = z i + s i + 2 − s i + 1 . z_{i-1} = \max(z_{i-1}^\star, z_i^\star+ s_{i+2} - s_{i+1}) \ge z_i^\star+ s_{i+2} - s_{i+1} = z_i + s_{i+2} - s_{i+1}. z i − 1 = max ( z i − 1 ⋆ , z i ⋆ + s i + 2 − s i + 1 ) ≥ z i ⋆ + s i + 2 − s i + 1 = z i + s i + 2 − s i + 1 .
It follows that s i + 1 + z i − 1 ≥ z i + s i + 2 s_{i+1}+z_{i-1}\ge z_i+s_{i+2} s i + 1 + z i − 1 ≥ z i + s i + 2 and hence
θ i − 1 = τ ( s i + 1 + z i − 1 ) ≤ τ ( s i + 2 + z i ) = θ i . \theta_{i-1}=\tau(s_{i+1}+z_{i-1})\le\tau(s_{i+2}+z_i)=\theta_i. θ i − 1 = τ ( s i + 1 + z i − 1 ) ≤ τ ( s i + 2 + z i ) = θ i .
We now verify the third property of a κ \kappa κ -bounded encoding. Fix i ≤ L − 3 i\le L-3 i ≤ L − 3 with z i > 0 z_i>0 z i > 0 . If f i = 1 f_i=1 f i = 1 , the property holds by definition. Otherwise, assume f i = 0 f_i=0 f i = 0 . If z i = z i ∗ z_i=z_i^* z i = z i ∗ , then by the properties of the set F F F , either f i − 1 = 1 f_{i-1}=1 f i − 1 = 1 and z i ≤ z i − 1 ∗ = z i − 1 z_i\le z_{i-1}^*=z_{i-1} z i ≤ z i − 1 ∗ = z i − 1 , or f i + 1 = 1 f_{i+1}=1 f i + 1 = 1 and z i ≤ z i + 1 ∗ = z i + 1 z_i\le z_{i+1}^*=z_{i+1} z i ≤ z i + 1 ∗ = z i + 1 . In either case, the required inequality holds. On the other hand, if z i = z i + 1 ∗ + s i + 3 − s i + 2 z_i=z_{i+1}^*+s_{i+3}-s_{i+2} z i = z i + 1 ∗ + s i + 3 − s i + 2 , then i + 1 ∈ F i+1\in F i + 1 ∈ F , and hence f i + 1 = 1 f_{i+1}=1 f i + 1 = 1 , so the property holds in this case as well.
It remains to verify that the encoding represents the path ( u 0 , … , u L − 1 ) (u_0,\ldots,u_{L-1}) ( u 0 , … , u L − 1 ) . By construction, each u i + 1 u_{i+1} u i + 1 is the a i a_i a i -th element of A θ i ( u i ) A_{\theta_i}(u_i) A θ i ( u i ) , so the first condition of Definition 4.4 is satisfied. Finally, if f i = 1 f_i=1 f i = 1 , then z i = z i ∗ z_i=z_i^* z i = z i ∗ . By the minimality of z i ∗ z_i^* z i ∗ (see (3) ), we have for z i − 1 z_i-1 z i − 1 that
∣ A τ ( s i + 2 + z i − 1 ) ( u i ) ∣ > κ z i − 1 ρ s ( i + 1 ) . \left|A_{\tau(s_{i+2}+z_i-1)}(u_i)\right|>\kappa z_{i-1}\rho_s(i+1). A τ ( s i + 2 + z i − 1 ) ( u i ) > κ z i − 1 ρ s ( i + 1 ) .
Observe that τ ( s i + 2 + z i − 1 ) = 2 θ i \tau(s_{i+2}+z_i-1)=2\theta_i τ ( s i + 2 + z i − 1 ) = 2 θ i . Hence, A τ ( s i + 2 + z i − 1 ) ( u i ) = A 2 θ i ( u i ) A_{\tau(s_{i+2}+z_i-1)}(u_i)=A_{2\theta_i}(u_i) A τ ( s i + 2 + z i − 1 ) ( u i ) = A 2 θ i ( u i ) , and the second condition in Definition 4.4 is satisfied. □
Decoding and verification procedure. We now describe a procedure that, given an encoding { ( z i , a i , f i ) } \{(z_i,a_i,f_i)\} {( z i , a i , f i )} and the ranks of all vertices in the tree, attempts to reconstruct a candidate path represented by this encoding. If no such path exists, the procedure fails. We will later show that the probability that the procedure succeeds is at most poly ( Δ ) ⋅ exp ( − ∑ i = 0 L − 3 z i ) \operatorname{poly}(\Delta)\cdot\exp\left(-\sum_{i=0}^{L-3}z_i\right) poly ( Δ ) ⋅ exp ( − ∑ i = 0 L − 3 z i ) . This bound is sufficient to show that the sum of the probabilities of all encodings converges to poly ( Δ ) ⋅ exp ( O ( L ) ) \operatorname{poly}(\Delta)\cdot\exp(O(L)) poly ( Δ ) ⋅ exp ( O ( L )) as desired.
The Decode & Verify procedure starts at the root of the tree, setting u 0 u_0 u 0 to be the root. It then iteratively constructs the path, while simultaneously verifying that the constructed sequence is indeed a candidate path. At each iteration i < L − 1 i<L-1 i < L − 1 , the procedure determines u i + 1 u_{i+1} u i + 1 using the triplet ( z i , a i , f i ) (z_i,a_i,f_i) ( z i , a i , f i ) from the κ \kappa κ -bounded path encoding. Specifically, it proceeds as follows.
Procedure Decode & Verify
Input: The root u 0 u_0 u 0 , parameter κ \kappa κ , a κ \kappa κ -bounded path encoding { ( z i , a i , f i ) } i = 0 L − 3 \{(z_i,a_i,f_i)\}_{i=0}^{L-3} {( z i , a i , f i ) } i = 0 L − 3 (See Definition 4.3 ), a sequence s ∈ S ( L ) s \in\mathcal{S}(L) s ∈ S ( L ) , and vertex ranks r r r .
Let u 0 u_0 u 0 be the root of the tree.
For each i = 0 , 1 , 2 , … , L − 3 i = 0,1,2,\ldots,L-3 i = 0 , 1 , 2 , … , L − 3 : (a) Compute θ i = τ ( s i + 2 + z i ) \theta_i = \tau(s_{i+2}+z_i) θ i = τ ( s i + 2 + z i ) .
(b) If f i = 1 f_i = 1 f i = 1 : compute
A 2 θ i ( u i ) = Find_Candidate_Set ( u i , 2 θ i ) , A_{2\theta_i}(u_i)=\operatorname{Find\_Candidate\_Set}(u_i,2\theta_i), A 2 θ i ( u i ) = Find_Candidate_Set ( u i , 2 θ i ) ,
and if ∣ A 2 θ i ( u i ) ∣ ≤ κ z i − 1 ρ s ( i + 1 ) |A_{2\theta_i}(u_i)| \leq\kappa_{z_i-1}\rho_s(i+1) ∣ A 2 θ i ( u i ) ∣ ≤ κ z i − 1 ρ s ( i + 1 ) , then terminate the algorithm with failure (since a “large candidate set” was expected but not found).
(c) Find the candidate set
A θ i ( u i ) = Find_Candidate_Set ( u i , θ i ) , A_{\theta_i}(u_i)=\operatorname{Find\_Candidate\_Set}(u_i,\theta_i), A θ i ( u i ) = Find_Candidate_Set ( u i , θ i ) ,
and set u i + 1 u_{i+1} u i + 1 to be the a i a_i a i -th element of A θ i ( u i ) A_{\theta_i}(u_i) A θ i ( u i ) with respect to the fixed ordering of children. If a i > ∣ A θ i ( u i ) ∣ a_i > |A_{\theta_i}(u_i)| a i > ∣ A θ i ( u i ) ∣ , then terminate with failure.
(d) Finally, verify that
r ( u i + 1 ) ∈ [ τ ( s i + 1 ) , τ ( s i + 1 − 1 ) ) . r(u_{i+1}) \in[\tau(s_{i+1}),\tau(s_{i+1}-1)). r ( u i + 1 ) ∈ [ τ ( s i + 1 ) , τ ( s i + 1 − 1 )) .
If not, terminate with failure.
Return the obtained path u 0 , … , u L − 2 u_0,\ldots,u_{L-2} u 0 , … , u L − 2 .
We now describe the procedure Find_Candidate_Set ( u , θ ) \operatorname{Find\_Candidate\_Set}(u,\theta) Find_Candidate_Set ( u , θ ) , used in the Decode & Verify \operatorname{Decode\ \&\ Verify} Decode & Verify procedure. Conceptually, this routine inspects the neighborhood of u u u just enough to determine which children of u u u are promising, and which of those belong to the candidate set A θ ( u ) A_\theta(u) A θ ( u ) . Crucially, it reveals ranks only of those vertices whose ranks must be examined in order to decide membership in A θ ( u ) A_\theta(u) A θ ( u ) .
Procedure Find_Candidate_Set
Input: a vertex u u u and threshold θ \theta θ .
For each child v ∈ Γ ( u ) v \in\Gamma(u) v ∈ Γ ( u ) do: (a) Inspect the ranks of the children w ∈ Γ ( v ) w \in\Gamma(v) w ∈ Γ ( v ) . For each such w w w , if r ( w ) < θ r(w) < \theta r ( w ) < θ , reveal the value of r ( w ) r(w) r ( w ) ; otherwise, reveal only that r ( w ) ≥ θ r(w) \ge\theta r ( w ) ≥ θ .
(b) For each child w ∈ Γ ( v ) w \in\Gamma(v) w ∈ Γ ( v ) with r ( w ) < θ r(w) < \theta r ( w ) < θ , compute RGMIS(T w , w , r \mathcal{T}_w,w,r T w , w , r ). The requires revealing the ranks of all vertices in the subtree T w \mathcal{T}_w T w rooted at w w w , and then simulating RGMIS on T w \mathcal{T}_w T w to determine whether w w w belongs to the independent set. (We emphasize that the RGMIS decision for w w w that we compute here depends only on the ranks within the subtree rooted at w w w , T w \mathcal{T}_w T w , so no additional information outside this subtree is exposed. In particular, the execution above does not answer whether w w w belongs to the independent set output by Algorithm 1 on w w w .)
(c) If RGMIS(T w , w , r \mathcal{T}_w,w,r T w , w , r ) = NO for each inspected w w w in the above step, then mark v v v as promising .
Let Y u Y_u Y u be the set of vertices v ∈ Γ ( u ) v \in\Gamma(u) v ∈ Γ ( u ) that are marked as promising.
If there exists a child v ∈ Γ ( u ) v \in\Gamma(u) v ∈ Γ ( u ) with r ( v ) < θ r(v) < \theta r ( v ) < θ and RGMIS(T v , v , r \mathcal{T}_v,v,r T v , v , r ) = YES, then set A θ ( u ) = ∅ A_\theta(u) = \varnothing A θ ( u ) = ∅ . Note that the condition being checked here is whether “u u u is promising at threshold θ \theta θ ” and per Definition 3.5 , A θ ( u ) A_\theta(u) A θ ( u ) is set to ∅ \varnothing ∅ if this condition does not hold.
Otherwise, define the candidate set
A θ ( u ) = { v ∈ Y u : r ( v ) ∈ [ τ ( s δ ( v ) ) , τ ( s δ ( v ) − 1 ) ) } . A_\theta(u) = \left\{v \in Y_u : r(v) \in[\tau(s_{\delta(v)}),\tau(s_{\delta(v)}-1))\right\}. A θ ( u ) = { v ∈ Y u : r ( v ) ∈ [ τ ( s δ ( v ) ) , τ ( s δ ( v ) − 1 )) } .
Observe that conditioned on u u u being promising at θ \theta θ , the above is the definition of A θ ( u ) A_\theta(u) A θ ( u ) per Definition 3.5 .
Return A θ ( u ) A_\theta(u) A θ ( u ) .
Lemma 4.7. If a κ \kappa κ -bounded path encoding z = { ( z i , a i , f i ) } i = 0 L − 3 z = \{(z_i,a_i,f_i)\}_{i=0}^{L-3} z = {( z i , a i , f i ) } i = 0 L − 3 represents a candidate path ( u 0 , … , u L − 1 ) (u_0,\ldots,u_{L-1}) ( u 0 , … , u L − 1 ) , then the Decode & Verify procedure succeeds on this encoding and returns the path ( u 0 , … , u L − 2 ) (u_0,\ldots,u_{L-2}) ( u 0 , … , u L − 2 ) .
Proof. Consider a candidate path P = ( u 0 , u 1 , … , u L − 1 ) P = (u_0,u_1,\ldots,u_{L-1}) P = ( u 0 , u 1 , … , u L − 1 ) agreeing with sequence s ∈ S ( L ) s \in\mathcal{S}(L) s ∈ S ( L ) and z z z be a κ \kappa κ -bounded encoding of P P P (see Definitions 3.4 and 4.4 ). We prove that for i ≤ L − 3 i \le L-3 i ≤ L − 3 , given u i u_i u i , executing steps 2a,2c,2b,2d computes the vertex u i + 1 u_{i+1} u i + 1 correctly without failure. It follows by induction that Decode & Verify computes the desired prefix to the path, i.e., ( u 0 , u 1 , … , u L − 2 ) (u_0,u_1,\ldots,u_{L-2}) ( u 0 , u 1 , … , u L − 2 ) correctly. Step 2a of Decode & Verify is identical for every call as θ i \theta_i θ i is set from the sequence s s s and encoding. At Step 2c of Decode & Verify, if the set A θ ( u i ) A_{\theta}(u_i) A θ ( u i ) is found correctly by procedure Find_Candidate_Set, then the vertex u i + 1 u_{i+1} u i + 1 is found correctly by Item 1 of Definition 4.4 . We next argue that Find_Candidate_Set(u i , θ u_i,\theta u i , θ ) correctly returns the candidate set for each u i , θ u_i,\theta u i , θ .
Claim 4.8. Procedure Find_Candidate_Set(u i , θ u_i,\theta u i , θ ) correctly outputs the candidate set at u i u_i u i for threshold θ \theta θ .
Proof. Let A θ ′ ( u i ) A'_{\theta}(u_i) A θ ′ ( u i ) denote the output of Find_Candidate_Set(u i , θ u_i,\theta u i , θ ). Consider an arbitrary child v v v of u i u_i u i . We show that v ∈ A θ ( u i ) v \in A_{\theta}(u_i) v ∈ A θ ( u i ) if and only if v ∈ A θ ′ ( u i ) v \in A'_{\theta}(u_i) v ∈ A θ ′ ( u i ) . First observe that if A θ ( u i ) A_{\theta}(u_i) A θ ( u i ) is forcibly set to ∅ \emptyset ∅ due “u i u_i u i not being promising at threshold θ \theta θ ”, then there exists a child v ∈ Γ ( u i ) v \in\Gamma(u_i) v ∈ Γ ( u i ) with r ( v ) < θ r(v) < \theta r ( v ) < θ satisfying RGMIS ( T v , v , r ) = Y E S \operatorname{RGMIS}(T_v,v,r) = \mathrm{YES} RGMIS ( T v , v , r ) = YES , this implies that A θ ′ ( u i ) A'_{\theta}(u_i) A θ ′ ( u i ) is set to ∅ \emptyset ∅ as well due to Step 3 of Find Candidate Set. Henceforth, we may assume that u i u_i u i is promising at threshold θ \theta θ .
( ⇒ ) (\Rightarrow) ( ⇒ ) If v ∈ A θ ( u i ) v \in A_{\theta}(u_i) v ∈ A θ ( u i ) , then (i) v v v is a child of u i u_i u i that has no neighbor w w w with r ( w ) < θ r(w) < \theta r ( w ) < θ that belongs to the MIS in the execution of RGMIS ( T w , w , r ) \operatorname{RGMIS}(T_w,w,r) RGMIS ( T w , w , r ) and (ii) r ( v ) ∈ [ τ ( s δ ( v ) ) , τ ( s δ ( v ) − 1 ) ) r(v) \in[\tau(s_{\delta(v)}),\tau(s_{\delta(v)}-1)) r ( v ) ∈ [ τ ( s δ ( v ) ) , τ ( s δ ( v ) − 1 )) . During Step 1, RGMIS ( T w , w , r ) \operatorname{RGMIS}(T_w,w,r) RGMIS ( T w , w , r ) is executed for all the neighbors w w w of v v v with r ( w ) < θ r(w) < \theta r ( w ) < θ and by choice of v v v , w w w does not belong to the MIS during this execution. Consequently v v v is marked promising and since r ( v ) r(v) r ( v ) lies in the expected interval is added to the candidate set in Step 4.
( ⇐ ) (\Leftarrow) ( ⇐ ) On the other hand if v ∉ A θ ( u i ) v \notin A_{\theta}(u_i) v ∈ / A θ ( u i ) , then either the rank verification step at step 4 fails or v v v is not a promising vertex. If v v v is not a promising vertex, then v v v contains at least one child, say w w w with r ( w ) < θ r(w) < \theta r ( w ) < θ that belongs to the MIS in the execution of RGMIS ( T w , w , r ) \operatorname{RGMIS}(T_w,w,r) RGMIS ( T w , w , r ) . Each such vertex w w w and the simulation of RGMIS ( T w , w , r ) \operatorname{RGMIS}(T_w,w,r) RGMIS ( T w , w , r ) is carried out during step 1b attesting that v v v is not a promising vertex and that v v v does not belong to the set returned by Find Candidate Set. □
At Step 2b, if f i = 1 f_i = 1 f i = 1 then computed set ∣ A 2 θ i ( u i ) ∣ \lvert A_{2\theta_i}(u_i)\rvert ∣ A 2 θ i ( u i )∣ must be large enough by Item 2 of Definition 4.4 . At Step 2d, the condition r ( u i + 1 ) ∈ [ τ ( s i + 1 ) , τ ( s i + 1 − 1 ) ) r(u_{i+1}) \in[\tau(s_{i+1}),\tau(s_{i+1}-1)) r ( u i + 1 ) ∈ [ τ ( s i + 1 ) , τ ( s i + 1 − 1 )) holds by the definition of candidate path. Thus, the call to Decode & Verify when executed with an encoding of the path P P P correctly computes u i + 1 u_{i+1} u i + 1 given that u i u_i u i is found correctly, for every i ≤ L − 3 i \leq L-3 i ≤ L − 3 . □
We now proceed to analyze the probability that Decode & Verify succeeds on a given κ \kappa κ -bounded path encoding. The high-level idea underlying the analysis is as follows. Whenever the flag f i f_i f i is set (i.e., f i = 1 f_i = 1 f i = 1 ), the procedure verifies that a low-probability event, namely { ∣ A 2 θ ( u i ) ∣ > κ z i − 1 ρ s ( i + 1 ) } \{\lvert A_{2\theta}(u_i)\rvert> \kappa z_{i-1}\rho_{s(i+1)}\} {∣ A 2 θ ( u i )∣ > κ z i − 1 ρ s ( i + 1 ) } , has occurred. We use Lemma 4.1 to show that the probability of this event (conditioned on the first i − 1 i-1 i − 1 steps of Decode & Verify) is approximately exp ( − Θ ( z i ) ) \exp(-\Theta(z_i)) exp ( − Θ ( z i )) . Consequently, the probability that the procedure does not fail at step i i i is at most exp ( − Θ ( z i ) ) \exp(-\Theta(z_i)) exp ( − Θ ( z i )) , and the probability that Decode & Verify succeeds at every step is at most exp ( − Θ ( ∑ i : f i = 1 z i ) ) \exp\left(-\Theta\left(\sum_{i:f_i=1} z_i\right)\right) exp ( − Θ ( ∑ i : f i = 1 z i ) ) . We formalize this intuition in Lemma 4.10 , but first carefully examine the randomness revealed during the first i i i steps of Decode & Verify.
Lemma 4.9. Let i ∈ { 0 , 1 , … , L − 2 } i \in\{0,1,\ldots,L-2\} i ∈ { 0 , 1 , … , L − 2 } with f i = 1 f_i = 1 f i = 1 . During steps 0 , … , i − 1 0,\ldots,i-1 0 , … , i − 1 of the execution of the Decode & Verify procedure on a valid κ \kappa κ -bounded encoding, for every child v v v of u i u_i u i with r ( v ) ≥ θ i r(v) \geq\theta_i r ( v ) ≥ θ i , no information about the ranks of vertices in the sub-tree T v T_v T v is revealed. For the rank r ( v ) r(v) r ( v ) , it is only revealed completely if r ( v ) < θ ′ r(v) < \theta' r ( v ) < θ ′ and otherwise, conditioned on the execution of Decode & Verify so far, r ( v ) r(v) r ( v ) is uniformly distributed in [ θ ′ , 1 ) [\theta',1) [ θ ′ , 1 ) for some θ ′ ≤ θ \theta' \leq\theta θ ′ ≤ θ .
Proof. We examine which ranks may be revealed during iterations 0 , … , i − 1 0,\ldots,i-1 0 , … , i − 1 of the Decode & Verify procedure. The only operations that may reveal the ranks of vertices other than the path vertices u 0 , … , u i u_0,\ldots,u_i u 0 , … , u i are calls to Find Candidate Set. During iteration j j j , the procedure invokes Find Candidate Set once with arguments ( u j , θ j ) (u_j,\theta_j) ( u j , θ j ) if f j = 0 f_j = 0 f j = 0 , and twice with arguments ( u j , θ j ) (u_j,\theta_j) ( u j , θ j ) and ( u j , 2 θ j ) (u_j,2\theta_j) ( u j , 2 θ j ) if f j = 1 f_j = 1 f j = 1 .
First, fix a step j ≤ i − 1 j \leq i-1 j ≤ i − 1 and consider a call to Find Candidate Set( u j , θ j ) (u_j,\theta_j) ( u j , θ j ) . By definition of this procedure, for each child v ∈ Γ ( u j ) v \in\Gamma(u_j) v ∈ Γ ( u j ) it inspects children w ′ ∈ Γ ( v ) w' \in\Gamma(v) w ′ ∈ Γ ( v ) and completely reveals r ( w ′ ) r(w') r ( w ′ ) only if r ( w ′ ) < θ j r(w') < \theta_j r ( w ′ ) < θ j , where θ j \theta_j θ j is the threshold used at step j j j . If this condition holds, the procedure simulates the RGMIS rule inside the subtree T w ′ T_{w'} T w ′ rooted at w ′ w' w ′ and reveals all the ranks of vertices in this subtree. Observe that the rank of vertex u j + 2 u_{j+2} u j + 2 satisfies
r ( u j + 2 ) ≥ τ ( s j + 2 ) ≥ τ ( s j + 2 + z j ) = θ j . r(u_{j+2}) \geq\tau(s_{j+2}) \geq\tau(s_{j+2}+z_j) = \theta_j. r ( u j + 2 ) ≥ τ ( s j + 2 ) ≥ τ ( s j + 2 + z j ) = θ j .
Moreover, if the flag f j = 1 f_j = 1 f j = 1 , then z j ≥ 1 z_j \ge1 z j ≥ 1 and
r ( u j + 2 ) ≥ τ ( s j + 2 ) ≥ τ ( s j + 2 + z j − 1 ) = 2 θ j . r(u_{j+2}) \ge\tau(s_{j+2}) \ge\tau(s_{j+2} + z_j - 1) = 2\theta_j. r ( u j + 2 ) ≥ τ ( s j + 2 ) ≥ τ ( s j + 2 + z j − 1 ) = 2 θ j .
Thus, in both cases, the calls to Find Candidate Set at u j u_j u j do not reveal ranks of vertices beneath any grandchild w w w of u j u_j u j with r ( w ) ≥ θ j r(w) \ge\theta_j r ( w ) ≥ θ j when f j ≠ 1 f_j \ne1 f j = 1 and r ( w ) ≥ 2 θ j r(w) \ge2\theta_j r ( w ) ≥ 2 θ j when f j = 1 f_j = 1 f j = 1 . In both cases u j + 2 u_{j+2} u j + 2 is included as desired.
Thus, when j < i − 1 j < i - 1 j < i − 1 , the rank of every vertex in T u j + 2 T_{u_{j+2}} T u j + 2 except u j + 2 u_{j+2} u j + 2 has not been queried. If the calls to Find Candidate Set at u j u_j u j inspected the rank of some grandchild w w w of u j u_j u j with r ( w ) ≥ θ j ( 1 + f j ) r(w) \ge\theta_j(1 + f_j) r ( w ) ≥ θ j ( 1 + f j ) , then it only inspects whether r ( w ) ≥ ( 1 + f j ) θ j r(w) \ge(1 + f_j)\theta_j r ( w ) ≥ ( 1 + f j ) θ j .
We next consider the case j = i − 1 j = i - 1 j = i − 1 . Note that i ≥ 1 i \ge1 i ≥ 1 . Since f i = 1 f_i = 1 f i = 1 , f i − 1 = 0 f_{i-1} = 0 f i − 1 = 0 and therefore the calls to Find Candidate Set at u i − 1 u_{i-1} u i − 1 only tests whether r ( v ) ≥ θ i − 1 ( 1 + f i − 1 ) = θ i − 1 r(v) \ge\theta_{i-1}(1 + f_{i-1}) = \theta_{i-1} r ( v ) ≥ θ i − 1 ( 1 + f i − 1 ) = θ i − 1 . If the condition passes, then no vertex beneath T v T_v T v is queried. The requirement f i = 1 f_i = 1 f i = 1 enforces that θ i − 1 ≤ θ i \theta_{i-1} \le\theta_i θ i − 1 ≤ θ i by Item 3 of Definition 4.3 and thus r ( v ) ≥ θ i ≥ θ i − 1 r(v) \ge\theta_i \ge\theta_{i-1} r ( v ) ≥ θ i ≥ θ i − 1 , so the test passes and no vertex beneath T v T_v T v is queried. This completes the proof.
Lemma 4.10. The probability that a given κ \kappa κ -bounded path encoding { ( z i , a i , f i ) } \{(z_i, a_i, f_i)\} {( z i , a i , f i )} represents a candidate path is at most
Pr ( Decode & Verify succeeds ) ≤ exp ( − 3 ∑ i : f i = 1 z i ) . \Pr(\text{Decode \& Verify succeeds}) \le\exp\left(-3\sum_{i:f_i=1} z_i\right). Pr ( Decode & Verify succeeds ) ≤ exp − 3 i : f i = 1 ∑ z i .
Proof. We run the Decode & Verify procedure step by step and, for each i i i , bound the probability that step i i i succeeds conditioned on all previous steps having succeeded. We then multiply these bounds. If f i = 0 f_i = 0 f i = 0 , we use the trivial upper bound 1 1 1 for the conditional success probability at step i i i .
Now fix a step i i i with f i = 1 f_i = 1 f i = 1 . Before bounding the probability that step i i i succeeds, we first argue that Lemma 4.1 applies to the random set A 2 θ i ( u i ) A_{2\theta_i}(u_i) A 2 θ i ( u i ) . By Lemma 4.9 , during steps 0 , … , i − 2 0,\ldots,i-2 0 , … , i − 2 the procedure does not reveal any ranks in the subtree T u i T_{u_i} T u i except possibly r ( u i ) r(u_i) r ( u i ) itself. Moreover, at step i − 1 i-1 i − 1 , it may only
reveal the ranks of vertices in subtrees T v T_v T v for v ∈ Γ ( u i ) v \in\Gamma(u_i) v ∈ Γ ( u i ) with r ( v ) < θ i r(v) < \theta_i r ( v ) < θ i ;
partially reveal the ranks of vertices v ∈ Γ ( u i ) v \in\Gamma(u_i) v ∈ Γ ( u i ) with r ( v ) ≥ θ i r(v) \ge\theta_i r ( v ) ≥ θ i , i.e., reveal only that r ( v ) ≥ θ i r(v) \ge\theta_i r ( v ) ≥ θ i . It does not reveal any ranks of vertices in T v T_v T v other than possibly v v v itself.
Thus, the revealed randomness immediately before step i i i satisfies the conditions of Lemma 4.1. Moreover, since f i = 1 f_i = 1 f i = 1 , by Definition 4.3 we have z i ≥ 1 z_i \ge1 z i ≥ 1 , and hence
θ i = τ ( s i + 2 + z i ) ≤ τ ( s i + 2 + 1 ) = τ ( s i + 2 ) / 2. \theta_i = \tau(s_{i+2} + z_i) \le\tau(s_{i+2} + 1) = \tau(s_{i+2})/2. θ i = τ ( s i + 2 + z i ) ≤ τ ( s i + 2 + 1 ) = τ ( s i + 2 ) /2.
Therefore, the assumptions of Lemma 4.1 are satisfied, and by this lemma, for every T > 0 T > 0 T > 0 , we have
Pr ( ∣ A 2 θ i ( u i ) ∣ ≥ T ) ≤ exp ( − T τ ( s δ ( u i ) + 1 ) θ i + 1 ) . \Pr\left(\lvert A_{2\theta_i}(u_i)\rvert\ge T\right) \le\exp\left(-\frac{T}{\frac{\tau(s_{\delta(u_i)}+1)}{\theta_i}+1}\right). Pr ( ∣ A 2 θ i ( u i )∣ ≥ T ) ≤ exp − θ i τ ( s δ ( u i ) + 1 ) + 1 T .
We apply this bound with T = ⌈ κ z i − 1 ρ s ( i + 1 ) ⌉ T = \lceil\kappa z_{i-1}\rho_s(i+1)\rceil T = ⌈ κ z i − 1 ρ s ( i + 1 )⌉ to upper bound the probability that the Decode & Verify procedure does not fail at step i i i :
Pr ( ∣ A 2 θ i ( u i ) ∣ ≥ κ z i − 1 ρ s ( i + 1 ) ) ≤ exp ( − κ z i − 1 ρ s ( i + 1 ) τ ( s i + 1 ) τ ( s i + 2 + z i ) + 1 ) . \Pr\left(\lvert A_{2\theta_i}(u_i)\rvert\ge\kappa z_{i-1}\rho_s(i+1)\right) \le\exp\left(-\frac{\kappa z_{i-1}\rho_s(i+1)}{\frac{\tau(s_{i+1})}{\tau(s_{i+2}+z_i)}+1}\right). Pr ( ∣ A 2 θ i ( u i )∣ ≥ κ z i − 1 ρ s ( i + 1 ) ) ≤ exp − τ ( s i + 2 + z i ) τ ( s i + 1 ) + 1 κ z i − 1 ρ s ( i + 1 ) .
Then,
τ ( s i + 1 ) τ ( s i + 2 + z i ) = 2 s i + 2 − s i + 1 ⋅ 2 z i = ρ s ( i + 1 ) ⋅ 2 z i . \frac{\tau(s_{i+1})}{\tau(s_{i+2}+z_i)}=2^{s_{i+2}-s_{i+1}}\cdot2^{z_i}=\rho_s(i+1)\cdot2^{z_i}. τ ( s i + 2 + z i ) τ ( s i + 1 ) = 2 s i + 2 − s i + 1 ⋅ 2 z i = ρ s ( i + 1 ) ⋅ 2 z i .
Substituting into the bound, we obtain
Pr ( ∣ A 2 θ i ( u i ) ∣ ≥ κ z i − 1 ρ s ( i + 1 ) ) ≤ exp ( − κ z i − 1 ρ s ( i + 1 ) ρ s ( i + 1 ) ⋅ 2 z i + 1 ) . \Pr\left(\lvert A_{2\theta_i}(u_i)\rvert\geq\kappa_{z_i-1}\rho_s(i+1)\right)\leq\exp\left(-\frac{\kappa_{z_i-1}\rho_s(i+1)}{\rho_s(i+1)\cdot2^{z_i}+1}\right). Pr ( ∣ A 2 θ i ( u i )∣ ≥ κ z i − 1 ρ s ( i + 1 ) ) ≤ exp ( − ρ s ( i + 1 ) ⋅ 2 z i + 1 κ z i − 1 ρ s ( i + 1 ) ) .
Since ρ s ( i + 1 ) ≥ 1 \rho_s(i+1)\geq1 ρ s ( i + 1 ) ≥ 1 and z i ≥ 1 z_i\geq1 z i ≥ 1 , we have
ρ s ( i + 1 ) ⋅ 2 z i + 1 ≤ 3 2 ρ s ( i + 1 ) ⋅ 2 z i . \rho_s(i+1)\cdot2^{z_i}+1\leq\frac{3}{2}\rho_s(i+1)\cdot2^{z_i}. ρ s ( i + 1 ) ⋅ 2 z i + 1 ≤ 2 3 ρ s ( i + 1 ) ⋅ 2 z i .
Since κ z i − 1 = 5 ⋅ z i ⋅ 2 z i \kappa_{z_i-1}=5\cdot z_i\cdot2^{z_i} κ z i − 1 = 5 ⋅ z i ⋅ 2 z i , we get
κ z i − 1 ρ s ( i + 1 ) ρ s ( i + 1 ) ⋅ 2 z i + 1 ≥ 5 ⋅ z i ⋅ 2 z i ⋅ ρ s ( i + 1 ) 3 2 ρ s ( i + 1 ) ⋅ 2 z i = 10 z i 3 . \frac{\kappa_{z_i-1}\rho_s(i+1)}{\rho_s(i+1)\cdot2^{z_i}+1}\geq\frac{5\cdot z_i\cdot2^{z_i}\cdot\rho_s(i+1)}{\frac{3}{2}\rho_s(i+1)\cdot2^{z_i}}=\frac{10z_i}{3}. ρ s ( i + 1 ) ⋅ 2 z i + 1 κ z i − 1 ρ s ( i + 1 ) ≥ 2 3 ρ s ( i + 1 ) ⋅ 2 z i 5 ⋅ z i ⋅ 2 z i ⋅ ρ s ( i + 1 ) = 3 10 z i .
It follows that
Pr ( ∣ A 2 θ i ( u i ) ∣ ≥ κ z i − 1 ρ s ( i + 1 ) ) ≤ e − 10 / 3 z i . \Pr\left(\lvert A_{2\theta_i}(u_i)\rvert\geq\kappa_{z_i-1}\rho_s(i+1)\right)\leq e^{-10/3\,z_i}. Pr ( ∣ A 2 θ i ( u i )∣ ≥ κ z i − 1 ρ s ( i + 1 ) ) ≤ e − 10/3 z i .
Thus, the conditional probability that step i i i succeeds, given that all previous steps have succeeded, is at most e − 10 / 3 z i e^{-10/3\,z_i} e − 10/3 z i whenever f i = 1 f_i=1 f i = 1 , while for f i = 0 f_i=0 f i = 0 we use the trivial bound 1. Multiplying these bounds yields
\Pr(\textsc{Decode \& Verify succeeds})\leq\prod_{i:f_i=1}e^{-10/3\,z_i}\leq\prod_{i:f_i=1}e^{-3z_i},
as claimed.
Lemma 4.10 establishes a strong upper bound on the probability that a bounded encoding corresponds to a candidate path, which we will use to estimate the expected number of candidate paths of length L L L . However, the bound depends on the sum ∑ i : f i = 1 z i \sum_{i:f_i=1}z_i ∑ i : f i = 1 z i , which is not convenient to work with directly. We thus show how to replace this term with the more tractable expression 1 3 ( ∑ i z i ) − m 3 \frac{1}{3}\left(\sum_i z_i\right)-\frac{m}{3} 3 1 ( ∑ i z i ) − 3 m .
Lemma 4.11. For every valid κ \kappa κ -bounded encoding, it holds that
∑ i = 0 L − 3 z i ≤ m + 3 ⋅ ∑ i : f i = 1 z i . \sum_{i=0}^{L-3}z_i\leq m+3\cdot\sum_{i:f_i=1}z_i. i = 0 ∑ L − 3 z i ≤ m + 3 ⋅ i : f i = 1 ∑ z i .
Proof. We upper bound the sum ∑ i = 0 L − 3 z i \sum_{i=0}^{L-3}z_i ∑ i = 0 L − 3 z i by bounding each term individually. We ignore indices i i i with z i = 0 z_i=0 z i = 0 , since they do not affect the sum, and upper bound each z i z_i z i with f i = 1 f_i=1 f i = 1 by itself. We now consider indices with z i > 0 z_i>0 z i > 0 and f i = 0 f_i=0 f i = 0 . By Item 4 of Definition 4.3 , each such z i z_i z i is upper bounded by either z i − 1 z_{i-1} z i − 1 or z i + 1 + s i + 3 − s i + 2 z_{i+1}+s_{i+3}-s_{i+2} z i + 1 + s i + 3 − s i + 2 . Moreover, in the former case f i − 1 = 1 f_{i-1}=1 f i − 1 = 1 , and in the latter case f i + 1 = 1 f_{i+1}=1 f i + 1 = 1 . Replacing each such z i z_i z i by its corresponding upper bound, we obtain an upper bound on the total sum.
The resulting expression consists of terms of the form z i z_i z i and z i + s i + 2 − s i + 1 z_i+s_{i+2}-s_{i+1} z i + s i + 2 − s i + 1 for indices with f i = 1 f_i=1 f i = 1 . Observe that each z i z_i z i appears with coefficient at most 3, depending on whether it is used to upper bound only itself, itself and one of z i − 1 z_{i-1} z i − 1 or z i + 1 z_{i+1} z i + 1 , or all three of z i z_i z i , z i − 1 z_{i-1} z i − 1 , and z i + 1 z_{i+1} z i + 1 . For each $i nkarhi with f i = 1 f_i=1 f i = 1 , the term s i + 2 − s i + 1 s_{i+2}-s_{i+1} s i + 2 − s i + 1 may appear with coefficient 1, or not appear at all, depending on whether z i z_i z i is used to upper bound z i − 1 z_{i-1} z i − 1 . Thus,
∑ i = 0 L − 3 z i ≤ ∑ i : f i = 1 3 z i + ∑ i : f i = 1 ( s i + 2 − s i + 1 ) . \sum_{i=0}^{L-3} z_i \le\sum_{i:f_i=1} 3z_i+\sum_{i:f_i=1}(s_{i+2}-s_{i+1}). i = 0 ∑ L − 3 z i ≤ i : f i = 1 ∑ 3 z i + i : f i = 1 ∑ ( s i + 2 − s i + 1 ) .
Since ( s i ) (s_i) ( s i ) is a non-decreasing sequence, we have s i + 2 − s i + 1 ≥ 0 s_{i+2}-s_{i+1}\ge0 s i + 2 − s i + 1 ≥ 0 for all i i i , and hence the second sum is upper bounded by
∑ i = 0 L − 3 ( s i + 2 − s i + 1 ) = s L − 1 − s 1 ≤ m . \sum_{i=0}^{L-3}(s_{i+2}-s_{i+1})=s_{L-1}-s_1\le m. i = 0 ∑ L − 3 ( s i + 2 − s i + 1 ) = s L − 1 − s 1 ≤ m .
This completes the proof.
Corollary 4.12. The probability that a κ \kappa κ -bounded path encoding { ( z i , a i , f i ) } \{(z_i,a_i,f_i)\} {( z i , a i , f i )} represents at least one candidate path is at most
e ⋅ Δ log 2 e ⋅ exp ( − ∑ i = 0 L − 3 z i ) . e\cdot\Delta^{\log_2 e}\cdot\exp\left(-\sum_{i=0}^{L-3}z_i\right). e ⋅ Δ l o g 2 e ⋅ exp ( − i = 0 ∑ L − 3 z i ) . Moreover, it represents at most Δ \Delta Δ candidate paths.
Proof. If a κ \kappa κ -bounded path encoding represents a candidate path, then the Decode & Verify procedure must be able to successfully decode and verify the encoding (see Lemma 4.7 ). By Lemmas 4.10 and 4.11 , we have that for every κ \kappa κ -bounded encoding { ( z i , a i , f i ) } \{(z_i,a_i,f_i)\} {( z i , a i , f i )} :
Pr ( Decode & Verify succeeds ) ≤ exp ( − 3 ∑ i : f i = 1 z i ) ≤ exp ( − 3 ( − m 3 + 1 3 ∑ i = 0 L − 3 z i ) ) = exp ( m ) ⋅ exp ( − ∑ i = 0 L − 3 z i ) . \begin{aligned}
\Pr(\text{Decode \& Verify succeeds})\le\exp\left(-3\sum_{i:f_i=1}z_i\right) \\
&\le\exp\left(-3\left(-\frac{m}{3}+\frac{1}{3}\sum_{i=0}^{L-3}z_i\right)\right) \\
&=\exp(m)\cdot\exp\left(-\sum_{i=0}^{L-3}z_i\right).
\end{aligned} Pr ( Decode & Verify succeeds ) ≤ exp − 3 i : f i = 1 ∑ z i ≤ exp ( − 3 ( − 3 m + 3 1 i = 0 ∑ L − 3 z i ) ) = exp ( m ) ⋅ exp ( − i = 0 ∑ L − 3 z i ) .
Substituting m ≤ log 2 Δ + 1 m\le\log_2\Delta+1 m ≤ log 2 Δ + 1 completes the proof of the probability bound.
From Lemma 4.7 , the Decode & Verify procedure executed with z = { ( z i , a i , f i ) } z=\{(z_i,a_i,f_i)\} z = {( z i , a i , f i )} constructs a prefix ( u 0 , u 1 , … , u L − 2 ) (u_0,u_1,\ldots,u_{L-2}) ( u 0 , u 1 , … , u L − 2 ) such that every candidate path encoded by z z z has the same prefix. There are at most Δ \Delta Δ choices for u L − 1 u_{L-1} u L − 1 as a neighbor of u L − 2 u_{L-2} u L − 2 , and thus the encoding can represent at most Δ \Delta Δ such paths.
We now prove Lemma 3.12 with a specific choice of constants C 1 C_1 C 1 and C 2 C_2 C 2 .
Lemma 4.13. For every s ∈ S ( L ) s\in S(L) s ∈ S ( L ) , the expected number of candidate paths of length L L L agreeing with s s s is at most
f ( L , Δ ) = ( 2 e ) ⋅ Δ 2 + log 2 e ⋅ 290 max ( 0 , L − 2 ) . f(L,\Delta)=(2e)\cdot\Delta^{2+\log_2 e}\cdot290^{\max(0,L-2)}. f ( L , Δ ) = ( 2 e ) ⋅ Δ 2 + l o g 2 e ⋅ 29 0 m a x ( 0 , L − 2 ) .
Proof. Note that when L ≤ 2 L\le2 L ≤ 2 , the bound in the lemma is trivial, as there are at most Δ L − 1 \Delta^{L-1} Δ L − 1 paths of L L L vertices starting from u 0 u_0 u 0 . Henceforth, we assume L ≥ 3 L\ge3 L ≥ 3 .
We first give a high-level overview of the proof. We first bound the expected number of encodings z = { ( z i , a i , f i ) } z=\{(z_i,a_i,f_i)\} z = {( z i , a i , f i )} that pass the Decode & Verify procedure. Each encoding can refer to multiple candidate paths. If P P P is a candidate path for some encoding z z z , then from Lemma 4.7 , all the vertices of P P P except the last vertex can be determined by executing the Decode & Verify procedure which is deterministic for a fixed rank r r r . Hence the candidate paths encoded by z \boldsymbol{z} z can only differ in the last vertex of the path. This implies that there are at most Δ \Delta Δ paths encoded by z \boldsymbol{z} z . The expected number of encodings is bound in a straightforward way, i.e., sum the probability bound by Corollary 4.12 over all possible encodings. The number of encodings for a fixed set ( z 0 , z 1 , … , z L − 3 ) (z_0,z_1,\ldots,z_{L-3}) ( z 0 , z 1 , … , z L − 3 ) is, poly ( Δ ) ∏ i = 0 L − 3 O ( z i 2 z i ) \operatorname{poly}(\Delta)\prod_{i=0}^{L-3}O(z_i2^{z_i}) poly ( Δ ) ∏ i = 0 L − 3 O ( z i 2 z i ) . The probability of any such encoding passing the Decode & Verify test is exp ( − ∑ z i ) \exp\left(-\sum z_i\right) exp ( − ∑ z i ) , which is exponentially smaller than ∏ z i 2 z i \prod z_i2^{z_i} ∏ z i 2 z i . Thus, the weighted sum of all encodings where the weights are the probabilities converges to poly ( Δ ) ⋅ exp ( O ( L ) ) \operatorname{poly}(\Delta)\cdot\exp(O(L)) poly ( Δ ) ⋅ exp ( O ( L )) .
Fix the sequence ( z 0 , … , z L − 3 ) (z_0,\ldots,z_{L-3}) ( z 0 , … , z L − 3 ) . For every i i i , once z i z_i z i is fixed, the number of possible values of a i a_i a i is at most
κ z i ρ s ( i + 1 ) . \kappa_{z_i}\rho_s(i+1). κ z i ρ s ( i + 1 ) .
Hence, for this fixed sequence ( z i ) (z_i) ( z i ) , the total number of possible choices of the indices ( a i ) (a_i) ( a i ) is at most
∏ i = 0 L − 3 κ z i ρ s ( i + 1 ) = ∏ i = 0 L − 3 ρ s ( i + 1 ) ⋅ ∏ i = 0 L − 3 κ z i . \prod_{i=0}^{L-3}\kappa_{z_i}\rho_s(i+1)=\prod_{i=0}^{L-3}\rho_s(i+1)\cdot\prod_{i=0}^{L-3}\kappa_{z_i}. i = 0 ∏ L − 3 κ z i ρ s ( i + 1 ) = i = 0 ∏ L − 3 ρ s ( i + 1 ) ⋅ i = 0 ∏ L − 3 κ z i .
Using the definition of ρ s ( i ) \rho_s(i) ρ s ( i ) , we obtain
∏ i = 0 L − 3 κ z i ρ s ( i + 1 ) = τ ( s 1 ) τ ( s L − 1 ) ⋅ ∏ i = 0 L − 3 κ z i ≤ 2 Δ ⋅ ∏ i = 0 L − 3 κ z i . \prod_{i=0}^{L-3}\kappa_{z_i}\rho_s(i+1)=\frac{\tau(s_1)}{\tau(s_{L-1})}\cdot\prod_{i=0}^{L-3}\kappa_{z_i}\le2\Delta\cdot\prod_{i=0}^{L-3}\kappa_{z_i}. i = 0 ∏ L − 3 κ z i ρ s ( i + 1 ) = τ ( s L − 1 ) τ ( s 1 ) ⋅ i = 0 ∏ L − 3 κ z i ≤ 2Δ ⋅ i = 0 ∏ L − 3 κ z i .
The number of possible flag sequences ( f i ) (f_i) ( f i ) is at most 2 L − 2 2^{L-2} 2 L − 2 . Therefore, the total number of κ \kappa κ -bounded path encodings with a prescribed sequence ( z 0 , … , z L − 3 ) (z_0,\ldots,z_{L-3}) ( z 0 , … , z L − 3 ) is at most
Δ ⋅ 2 L − 1 ⋅ ∏ i = 0 L − 3 κ z i . \Delta\cdot2^{L-1}\cdot\prod_{i=0}^{L-3}\kappa_{z_i}. Δ ⋅ 2 L − 1 ⋅ i = 0 ∏ L − 3 κ z i .
By Corollary 4.12 , the probability that such an encoding represents a candidate path is at most
e Δ log 2 e exp ( − ∑ i = 0 L − 3 z i ) . e^{\Delta\log_2 e}\exp\left(-\sum_{i=0}^{L-3}z_i\right). e Δ l o g 2 e exp ( − i = 0 ∑ L − 3 z i ) .
It follows that the expected number of encodings with prescribed values ( z 0 , … , z L − 3 ) (z_0,\ldots,z_{L-3}) ( z 0 , … , z L − 3 ) that represent a candidate path is at most
e ⋅ Δ 1 + log 2 e ⋅ 2 L − 1 ⋅ ∏ i = 0 L − 3 ( κ z i e − z i ) . e\cdot\Delta^{1+\log_2 e}\cdot2^{L-1}\cdot\prod_{i=0}^{L-3}\left(\kappa_{z_i}e^{-z_i}\right). e ⋅ Δ 1 + l o g 2 e ⋅ 2 L − 1 ⋅ i = 0 ∏ L − 3 ( κ z i e − z i ) .
Summing over all possible choices of ( z i ) (z_i) ( z i ) , we obtain
e ⋅ Δ 1 + log 2 e ⋅ 2 L − 1 ⋅ ∑ z 0 , … , z L − 3 ∈ Z ≥ 0 ∏ i = 0 L − 3 κ z i e − z i = e ⋅ Δ 1 + log 2 e ⋅ 2 L − 1 ⋅ ( ∑ z ∈ Z ≥ 0 κ z e − z ) L − 2 . e\cdot\Delta^{1+\log_2 e}\cdot2^{L-1}\cdot\sum_{z_0,\ldots,z_{L-3}\in\mathbb{Z}_{\ge0}}\prod_{i=0}^{L-3}\kappa_{z_i}e^{-z_i}
=e\cdot\Delta^{1+\log_2 e}\cdot2^{L-1}\cdot\left(\sum_{z\in\mathbb{Z}_{\ge0}}\kappa_z e^{-z}\right)^{L-2}. e ⋅ Δ 1 + l o g 2 e ⋅ 2 L − 1 ⋅ z 0 , … , z L − 3 ∈ Z ≥ 0 ∑ i = 0 ∏ L − 3 κ z i e − z i = e ⋅ Δ 1 + l o g 2 e ⋅ 2 L − 1 ⋅ z ∈ Z ≥ 0 ∑ κ z e − z L − 2 .
The sum on the right-hand side is upper bounded as follows:
∑ z ∈ Z ≥ 0 κ z e − z = ∑ z ∈ Z ≥ 0 5 ( z + 1 ) 2 z + 1 e − z = 10 ∑ z ∈ Z ≥ 0 ( z + 1 ) ( 2 e ) z . \sum_{z\in\mathbb{Z}_{\ge0}}\kappa_z e^{-z}
=\sum_{z\in\mathbb{Z}_{\ge0}}5(z+1)2^{z+1}e^{-z}
=10\sum_{z\in\mathbb{Z}_{\ge0}}(z+1)\left(\frac{2}{e}\right)^z. z ∈ Z ≥ 0 ∑ κ z e − z = z ∈ Z ≥ 0 ∑ 5 ( z + 1 ) 2 z + 1 e − z = 10 z ∈ Z ≥ 0 ∑ ( z + 1 ) ( e 2 ) z .
Using the Taylor series of 1 ( 1 − x ) 2 \frac{1}{(1-x)^2} ( 1 − x ) 2 1 and substituting x = 2 e x=\frac{2}{e} x = e 2 , we obtain
∑ z ∈ Z ≥ 0 κ z e − z = 10 e 2 ( e − 2 ) 2 ≤ 145. \sum_{z\in\mathbb{Z}_{\ge0}} \kappa_z e^{-z} = \frac{10e^2}{(e-2)^2} \le145. z ∈ Z ≥ 0 ∑ κ z e − z = ( e − 2 ) 2 10 e 2 ≤ 145.
Each encoding can correspond to at most Δ \Delta Δ candidate paths, since u L − 1 u_{L-1} u L − 1 is the only vertex that is not identified by the Decode&Verify procedure and there are Δ \Delta Δ choices for u L − 1 u_{L-1} u L − 1 as a child of u L − 2 u_{L-2} u L − 2 . Therefore, the expected number of encodings that represent a candidate path is at most
e ⋅ Δ 2 + log 2 e ⋅ 2 L − 1 ⋅ 145 L − 2 = 2 e ⋅ Δ 2 + log 2 e ⋅ 290 L − 2 . e\cdot\Delta^{2+\log_2 e}\cdot2^{L-1}\cdot145^{L-2}=2e\cdot\Delta^{2+\log_2 e}\cdot290^{L-2}. e ⋅ Δ 2 + l o g 2 e ⋅ 2 L − 1 ⋅ 14 5 L − 2 = 2 e ⋅ Δ 2 + l o g 2 e ⋅ 29 0 L − 2 .
as desired. □ \square □
Finally each κ \kappa κ -bounded path encoding represents at most Δ \Delta Δ candidate paths. The desired constants C 1 , C 2 C_1,C_2 C 1 , C 2 for Lemma 3.12 are bounded by C 1 ≤ 290 C_1\le290 C 1 ≤ 290 and C 2 ≤ 3 + ( 1 / ln 2 ) < 4.5 C_2\le3+(1/\ln2)<4.5 C 2 ≤ 3 + ( 1/ ln 2 ) < 4.5 . Hence, we obtain a bound of O ( Δ 4.25 ) O(\Delta^{4.25}) O ( Δ 4.25 ) on the expected size of the query tree generated by Algorithm 1.
Deferred proofs
Bounding low-rank paths
Consider a tree T \mathcal{T} T , a vertex u ∈ T u \in T u ∈ T and the execution of RGMIS(T , u , r \mathcal{T},u,r T , u , r ) over uniformly random r r r . We show that the expected number of query paths to vertices with rank [ τ ( m ) , 1 ) [\tau(m),1) [ τ ( m ) , 1 ) is at least a constant factor of the total expected number of query paths.
Lemma A.1 (Bounding expected low-rank paths). For an arbitrary vertex v v v in an arbitrary tree T \mathcal{T} T of degree at most Δ \Delta Δ , let Q l o w ( T , v ) Q_{\mathrm{low}}(T,v) Q low ( T , v ) denote the set of query paths P P P in the execution of RGMIS(T , v \mathcal{T},v T , v ) such that every vertex w ∈ P − v w \in P-v w ∈ P − v has r ( w ) < 1 / Δ r(w)<1/\Delta r ( w ) < 1/Δ . It holds that,
E r [ ∣ Q l o w ( T , v ) ∣ ∣ r ( v ) ] ≤ e \mathbb{E}_{r}[|Q_{\mathrm{low}}(T,v)| \mid r(v)] \le e E r [ ∣ Q low ( T , v ) ∣ ∣ r ( v )] ≤ e
Proof. The number of paths with L L L edges is at most Δ L \Delta^{L} Δ L . For each such path, the probability that the ranks of all the vertices in it except for v v v lie in [ 0 , τ ( m ) ) [0,\tau(m)) [ 0 , τ ( m )) is at most Δ − L \Delta^{-L} Δ − L . Given that all ranks lie in [ 0 , τ ( m ) ) [0,\tau(m)) [ 0 , τ ( m )) , the probability that the path is r r r -monotone is 1 / L ! 1/L! 1/ L ! . Thus, the expected number of such paths is at most ∑ L ≥ 0 Δ L ⋅ Δ − L ⋅ 1 / L ! = e \sum_{L\ge0}\Delta^{L}\cdot\Delta^{-L}\cdot1/L!=e ∑ L ≥ 0 Δ L ⋅ Δ − L ⋅ 1/ L ! = e .
Lemma A.2 (Reduction to high-rank paths). Consider an arbitrary tree T \mathcal{T} T and vertex u ∈ T u \in\mathcal{T} u ∈ T . Let X X X be the expected number of query paths in the execution of RGMIS ( T , u ) \operatorname{RGMIS}(\mathcal{T},u) RGMIS ( T , u ) that agree with some sequence s ∈ S s \in\mathcal{S} s ∈ S . In particular, this implies that each vertex on the path has rank at least τ ( m ) \tau(m) τ ( m ) . It holds that the total expected number of query paths in RGMIS ( T , u ) \operatorname{RGMIS}(\mathcal{T},u) RGMIS ( T , u ) is at most e ( X + 1 ) e(X+1) e ( X + 1 ) .
Proof. For convenience, we add an imaginary vertex ⊥ \perp ⊥ to the tree T ⊥ \mathcal{T}_{\perp} T ⊥ whose only neighbor is u u u and root the new tree T ⊥ \mathcal{T}_{\perp} T ⊥ at ⊥ \perp ⊥ . We consider r ( ⊥ ) = 1 ≥ τ ( m ) r(\perp)=1\geq\tau(m) r ( ⊥ ) = 1 ≥ τ ( m ) . We make this change so that every query path in RGMIS ( T ⊥ , ⊥ , r ) \operatorname{RGMIS}(\mathcal{T}_{\perp},\perp,r) RGMIS ( T ⊥ , ⊥ , r ) begins at a vertex with rank at least τ ( m ) \tau(m) τ ( m ) with probability 1 1 1 . At the same time, the size of the query tree produced by RGMIS ( T ⊥ , ⊥ , r ) \operatorname{RGMIS}(\mathcal{T}_{\perp},\perp,r) RGMIS ( T ⊥ , ⊥ , r ) is same as the size of the desired query tree RGMIS ( T , u , r ) \operatorname{RGMIS}(\mathcal{T},u,r) RGMIS ( T , u , r ) after ignoring the vertex ⊥ \perp ⊥ .
To prove the lemma, consider an arbitrary vertex v ∈ T ⊥ v \in\mathcal{T}_{\perp} v ∈ T ⊥ . Let path ( v ) \operatorname{path}(v) path ( v ) denote the unique path from ⊥ \perp ⊥ to v v v in T ⊥ \mathcal{T}_{\perp} T ⊥ . Let E v E_v E v denote the event that RGMIS ( T ⊥ , u ) \operatorname{RGMIS}(\mathcal{T}_{\perp},u) RGMIS ( T ⊥ , u ) queries v v v and r ( v ) ≥ τ ( m ) r(v)\geq\tau(m) r ( v ) ≥ τ ( m ) . Let p ( v ) = Pr [ E v ] p(v)=\Pr[E_v] p ( v ) = Pr [ E v ] .
E v : RGMIS ( T ⊥ , ⊥ , r ) queries v ∧ r ( v ) ≥ τ ( m ) E_v:\ \operatorname{RGMIS}(\mathcal{T}_{\perp},\perp,r)\text{ queries }v\wedge r(v)\geq\tau(m) E v : RGMIS ( T ⊥ , ⊥ , r ) queries v ∧ r ( v ) ≥ τ ( m )
p ( v ) = Pr [ E v ] p(v)=\Pr[E_v] p ( v ) = Pr [ E v ]
Note that E ⊥ E_{\perp} E ⊥ is a sure event, i.e., p ( ⊥ ) = 1 p(\perp)=1 p ( ⊥ ) = 1 . Note that E v E_v E v is independent of the ranks of vertices in the sub-tree T v \mathcal{T}_v T v excluding v v v . To see this, observe that in the procedure RGMIS ( T ⊥ , ⊥ , r ) \operatorname{RGMIS}(\mathcal{T}_{\perp},\perp,r) RGMIS ( T ⊥ , ⊥ , r ) when v v v is visited for the first time, the entire sub-tree beneath v v v has been unexplored, and hence their ranks have not been read.
Observe that by linearity of expectation,
X = ∑ v ∈ T p ( v ) . (4) X=\sum_{v\in\mathcal{T}}p(v). \tag*{(4)} X = v ∈ T ∑ p ( v ) . (4)
Let Q l o w ( v ) Q_{\mathrm{low}}(v) Q low ( v ) denote the set of query paths in RGMIS ( T v , v ) \operatorname{RGMIS}(\mathcal{T}_v,v) RGMIS ( T v , v ) such that all of the vertices in the path have rank in [ 0 , τ ( m ) ) [0,\tau(m)) [ 0 , τ ( m )) except v v v . We have, E [ ∣ Q l o w ( v ) ∣ ∣ r ( v ) ] ≤ e \mathbb{E}[|Q_{\mathrm{low}}(v)|\mid r(v)]\leq e E [ ∣ Q low ( v ) ∣ ∣ r ( v )] ≤ e by Lemma A.1 and the independence of ranks in T v \mathcal{T}_v T v . Finally, the expected total number of paths Q ( T ⊥ , ⊥ ) Q(\mathcal{T}_{\perp},\perp) Q ( T ⊥ , ⊥ ) is given by,
E r [ ∣ Q ( T ⊥ , ⊥ ) ∣ ] = ∑ v ∈ T ⊥ Pr [ E v ] ⋅ E r [ ∣ Q l o w ( T v , v ) ∣ ∣ E v ] [Using linearity of expectation] = ∑ v ∈ T ⊥ Pr [ E v ] ⋅ E r [ ∣ Q l o w ( T v , v ) ∣ ∣ r ( v ) ] [Using independence of E v from T v − v ] ≤ e ∑ v ∈ T ⊥ Pr [ E v ] [Using Lemma A.1] = e ( X + 1 ) [By Equation 4, with + 1 accounting for ⊥ ] \begin{aligned}
\mathbb{E}_{r}[|Q(\mathcal{T}_{\perp},\perp)|]
&=\sum_{v\in\mathcal{T}_{\perp}}\Pr[E_v]\cdot\mathbb{E}_{r}[|Q_{\mathrm{low}}(\mathcal{T}_v,v)|\mid E_v] && \text{[Using linearity of expectation]}\\
&=\sum_{v\in\mathcal{T}_{\perp}}\Pr[E_v]\cdot\mathbb{E}_{r}[|Q_{\mathrm{low}}(\mathcal{T}_v,v)|\mid r(v)] && \text{[Using independence of } E_v \text{ from } \mathcal{T}_v-v\text{]}\\
&\leq e\sum_{v\in\mathcal{T}_{\perp}}\Pr[E_v] && \text{[Using Lemma A.1]}\\
&=e(X+1) && \text{[By Equation 4, with } +1 \text{ accounting for } \perp\text{]}
\end{aligned} E r [ ∣ Q ( T ⊥ , ⊥ ) ∣ ] = v ∈ T ⊥ ∑ Pr [ E v ] ⋅ E r [ ∣ Q low ( T v , v ) ∣ ∣ E v ] = v ∈ T ⊥ ∑ Pr [ E v ] ⋅ E r [ ∣ Q low ( T v , v ) ∣ ∣ r ( v )] ≤ e v ∈ T ⊥ ∑ Pr [ E v ] = e ( X + 1 ) [Using linearity of expectation] [Using independence of E v from T v − v ] [Using Lemma A.1] [By Equation 4, with + 1 accounting for ⊥ ]
as desired.