Pierre Fraigniaud
email: pierre.fraigniaud@irif.fr.

Amos Korman
email: amos.korman@irif.fr.

Yoav Rodeh
email: yoav.rodeh@gmail.com.

Parallel Bayesian Search with no Coordination

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Introduction

BOINC [22] (Berkeley Open Infrastructure for Network Computing) is a platform for volunteer computing supporting dozens of projects including the famous SETI@home analyzing radio signals for identifying signs of extra terrestrial intelligence. Most projects maintained at BOINC use parallel search mechanisms where a central server controls, and distributes the work to volunteers. The framework in this paper is an abstraction for projects operated at platforms similar to BOINC with hundreds of thousands distributed searchers. We address the following question: how to distribute the work among the searchers with respect to the amount of coordination between them provided by the central server? This paper drives to the conclusion that no coordination might actually be a quite viable strategy, both efficient and robust. Specifically, we consider a parallel variant of the classical Bayesian search problem, typically attributed to Blackwell [START_REF] Blackwell | Notes on dynamic programming[END_REF]. A treasure is placed according to some distribution p in one of infinitely many boxes, indexed by the positive integers. The search for the treasure is performed in parallel by k ≥ 1 agents, also called searchers, which means that at each time step each searcher can "peek" into a box to check whether the treasure is present there. The goal is to minimize the expected time until the first searcher finds the treasure. We assume that the number k of searchers is known to the algorithm. We will consider two cases, whether p is given to the algorithm, or not. However, in the latter case, we assume that the algorithm is aware of the relative likelihood of the boxes. In both cases, we can assume, w.l.o.g., that the boxes B x , x ≥ 1, are ordered so that p is non-increasing, i.e., p(x + 1) ≤ p(x) for every x ≥ 1.

Let s 1 , . . . , s k be the k searchers at hand. If coordination is allowed, let A coord be the algorithm that lets searcher s i peek into box B (t-1)k+i at time t. A simple application of the rearrangement inequality shows that A coord is an optimal algorithm, that is, it minimizes the expected time until one searcher finds the treasure. This time is x≥1 p(x) x/k since the box B x is opened at time x/k in A coord , and this box has probability p(x) to contain the treasure. In particular, the optimal expected time to find the treasure with a single searcher is x≥1 x p(x). Therefore, if coordination is allowed, k searchers essentially allow to find the treasure k times faster than one searcher alone, in expectation. (Specifically, the speedup resulting from using k searchers approaches k when the expectation of the distribution p grows to infinity). However, as simple as this algorithm is, A coord is very sensitive to faults of all sorts. For example, if one searcher crashes at some point during the execution then the searchers may completely miss the treasure, unless the protocol employs some mechanism for detecting such faults. Indeed, in A coord , each box is eventually opened by just one searcher. Namely, box B (t-1)k+i is opened only by searcher s i , for every t ≥ 1 and 1 ≤ i ≤ k.

In this paper, we highlight the usefulness of a class of search algorithms, called non-coordinating, which is inherently robust. In such algorithms, all searchers operate independently, executing the same protocol, differing only in the outcome of the flips of their private random coins. A canonical example is the case of multiple random walkers that search a graph [START_REF] Alon | Many Random Walks Are Faster Than One[END_REF]. Although many search problems cannot be efficiently parallelized without coordination, when such parallelization can be achieved, the benefit can potentially be high, not only in terms of saving in communication and overhead in computation, but also in terms of robustness. To get some intuition, observe that when executing a non-coordinating algorithm, the correct operation as well as the running time can only improve if more searchers than planned are actually being used. Suppose for instance that an oblivious adversary is allowed to crash at most k out of the k searchers at arbitrary times during the execution. To overcome the presence of k faults, one can simply run the non-coordinating algorithm that is designed for the case of k -k searchers. If the running time of the non-coordinating algorithm for x searchers without crashes is T (x), then the running time of the new robust (non-coordinating) algorithm would be at most T (k -k ). Note that even when coordination is allowed, one cannot expect to obtain robustness at a cost less than T (k -k ) in the worst case, where T (x) denotes the cost of an optimal coordinating algorithm for x searchers 1 without crashes, since the number of searchers that remain alive is in the worst case k -k . Hence, if T (•) and T (•) are close, we get robustness almost for free by using a non-coordinating algorithm.

In this paper, we are interested in computing how much we lose in term of performance when using non-coordinating algorithms. Specifically, let k ≥ 1, and let us denote by T k (A, x) the expected time for an algorithm A to find the treasure with k searchers running in parallel if this treasure is placed at box x. Further, given a distribution p over the placement of the treasure in the boxes, let T p,k (A) denote the expected time for A to find the treasure when it is placed in one of the boxes according to p. We have

T p,k (A) = x≥1 p(x)T k (A, x). (1)
With this notation, the expected running time of the optimal coordinating algorithm is T p,k (A coord ) = x≥1 p(x) x/k . We are interested in comparing these two terms, i.e., T p,k (A) for a non-coordinating algorithm A versus T p,k (A coord ), the complexity of the best search algorithm with full coordination. For this purpose, we use competitive analysis, and say that an algorithm A is c-competitive for k searchers looking for a treasure placed according to p if there is a constant b such that

T p,k (A) ≤ c T p,k (A coord ) + b.
We show that there is a non-coordinating algorithm with small competitive ratio, hence establishing that indeed one does not lose much in using non-coordinating algorithms.

Before going into the details of our results, let us observe that although the random placement of the treasure is the common setting in Bayesian search problems, yielding Eq. ( 1) for defining the complexity of a search algorithm, there is another abstract search setting which deserves to be investigated, that we call linear search. Indeed, searching for a proper divisor of a given number n, the typical approach to solve the problem consists of enumerating the candidate divisors in increasing order, from 2 to √ n, and checking them one by one. This is because the probability that a random number is divisible by a given prime is inversely proportional to this prime. Similarly, in cryptography, an attack is better proceeded by systematically checking smaller keys than longer ones, because the time to check a key is typically exponential in its size. There are thus several contexts in which the search space can be ordered in a way such that, given that the previous trials were not successful, the next candidate according to the order is either the most preferable, or most likely to be valid, or the easiest to check. This led us to consider another measure of complexity, comparing the search time of an algorithm A to the search time of the algorithm with one searcher opening the boxes sequentially in order of their indices, namely

T k (A) = max x≥1 T k (A, x)/x. (2)
Again, we say that a search algorithm A is c-competitive for k searchers looking for a treasure arbitrarily placed in one box if there is a constant b such that

T k (A) ≤ c T k (A coord ) + b.
In the linear search setting, the aforementioned algorithm A coord is also optimal. We show that, as for Bayesian search, one does not lose much in using non-coordinating algorithms in linear search.

Our Results

First, we design and analyze an optimal non-coordinating algorithm for Bayesian search, where p is given. Our algorithm, called A , has optimal expected running time among all non-coordinating algorithms. Specifically, for every distribution p, every k ≥ 1, and every non-coordinating algorithm A,

T p,k (A ) ≤ T p,k (A).
A remarkable property satisfied by our non-coordinating algorithm A is that, at any time t > 1 during its execution, all boxes that received a positive probability to be checked at some time t < t, are now going to be checked at time t with equal probability. The design of A is complex. However, when p is the uniform distribution over a finite domain, A becomes simple to describe: at each step, each searcher running A chooses a box uniformly among those it did not check at previous step. This natural algorithm for the uniform setting is optimal among all non-coordinating algorithms, and is shown to be at most 2 times slower than A coord .

Next, we focus on the notion of order-invariant algorithms, that is, algorithms assuming only the knowledge of the relative likelihood of the boxes (and not knowing the exact probability of finding the treasure in each box). Such algorithms are appealing because they are "universal", in the sense that, once the boxes have been reordered such that B x is not less likely to contain the treasure than B x+1 , any order-invariant algorithm acts the same for all distributions. We present a very simple yet highly efficient non-coordinating order-invariant algorithm, called A order . In this algorithm, at step t, each searcher checks a box uniformly chosen among those it did not check yet in {1, . . . , t 2 (k + 1)}. The performance of A order is essentially at most 4 times the expected running time of the best fully coordinated algorithm A coord . Precisely, for every distribution p, and every k ≥ 1,

T p,k (A order ) ≤ 4 1 - 1 k + 1 2 T p,k (A coord ) + 10. ( 3
)
Ignoring the constant additive term, the aforementioned upper bound implies that the cost paid for not coordinating is just at most 16 /9 for two searchers, 9 /4 for three searchers, and approaches 4 as the number of searchers goes to infinity. In fact we show that these costs are tight in a very strong sense, as, for any given number of searchers, there is no non-coordinating order-invariant algorithm that achieves a better competitive ratio. Specifically, for every distribution p, every k ≥ 1, and every order-invariant non-coordinating algorithm A, if there exist b and c such that

T p,k (A) ≤ c T p,k (A coord ) + b, then c ≥ 4 1 - 1 k + 1 2 . ( 4
)
Algorithm A order remembers all the boxes it checked, and so each searcher needs memory linear in the running time of the algorithm. We also consider A obliv which at step t chooses one box uniformly at random in {1, . . . , k t 2 }, hence potentially choosing many times the same box at different time steps. This algorithm uses memory that is just logarithmic in its running time, but performs almost as well as A order for large number of searchers. Precisely, for every distribution p, and every k ≥ 1,

T p,k (A obliv ) ≤ 4 T p,k (A coord ) + 2. ( 5
)
All the aforementioned upper bound results on order-invariant algorithms are actually established by considering the linear search setting, where the treasure is placed at an arbitrary box, and boxes are ordered by importance, that is, when focussing on the complexity T k (A) = max x≥1 T k (A, x)/x of any algorithm A (cf. Eq. ( 2)). Indeed, it turns out that the two settings (Bayesian search and linear search) are highly related, as far as order-invariant algorithms are concerned: an order-invariant algorithm that works well against a treasure placed arbitrarily would also work well in any probabilistic setting (under the assumption that the indices of the boxes are ordered according to their relative likelihood). In fact, in the linear search setting, A order and A obliv have the same competitive ratio as those mentioned in Eq. ( 3) and (5), respectively. Moreover, the lower bound of Eq. ( 4) also holds in the linear search setting, i.e., A order has also optimal competitive ratio in this latter setting.

As mentioned earlier, since we are dealing with non-coordinating search algorithms, we immediately get robustness with respect to crashes of searchers. We point out that, in addition, our order-invariant algorithms are robust also for the case where each searcher has a possibly different, distorted, list of boxes. Such a distorted list may contain some extra boxes, and/or the order of the true boxes (those possibly containing the treasure) may be permuted. More precisely, for every box x, let σ s i (x) be the box index of B x in the "eyes" of searcher s i , and let us denote by σ(x) = 1 k k i=1 σ s i (x). We show that if σ(x) = x + o(x) for all x, then A order and A obliv still have essentially the same respective multiplicative ratios compared to A coord running on the non-distorted list. In other words, the algorithm works practically just as well even if the average placement of x is not very far from its correct placement.

All the characteristics and performances of our algorithms are summarized in Table 1 In terms of techniques, our approach uses a crucial aspect of non-coordinating algorithms: they can be represented by infinite matrices. The performance analyses of our algorithms rely on carefully analyzing the corresponding matrices, and on using known properties of the Gamma function. Not surprisingly, demonstrating the optimality of A , and establishing the optimality of the competitive ratio of A order are the hardest tasks. To establish these results, we first approximate matrices by continuous functions, and use compactness arguments. In fact, we establish a general technical lemma in the context of Measure theory, that we apply to different settings in our paper.

Related work

The case of a single searcher that searches for a randomly placed treasure received significant amount of attention from the communities of statistics, operational research and computer science (see e.g., [START_REF] Blackwell | Notes on dynamic programming[END_REF][START_REF] David | Optimal sequential search: A bayesian approach[END_REF][START_REF] Milton | A sequential search procedure[END_REF]), and has been studied under various settings, including the cases where different costs are associated with the queries to the locations where the treasure is suspected to be (in our case, a query is just opening a box, and takes one step), where queries can be noisy (e.g., responses might be unreliable), and where the target may be mobile (see the book [START_REF] Stone | Theory of optimal search[END_REF]).

When it comes to parallel search, most of the literature deals with mobile agents that search graphs of different topologies, and it is typically assumed that agents employ some form of communication. The literature on this subject is vast, and some good references can be found in, e.g., [START_REF] Alpern | Search theory: A game theoretic perspective[END_REF][START_REF] Alpern | The theory of search games and rendezvous[END_REF][START_REF] Das | Mobile agents in distributed computing: Network exploration[END_REF][START_REF] Flocchini | Distributed computing by oblivious mobile robots[END_REF][START_REF] Prencipe | Autonomous mobile robots: A distributed computing perspective[END_REF]. The major difference between our setting and the mobile agent setting, is that we allow "random access" to the different boxes. That is, our searcher can jump between different boxes at no cost. In other words, our focus is on the query complexity rather than the move complexity. Note, however, that the settings are related as the number of queries is always a lower bound on the number of moves.

Multiple random walkers are a special case of non-coordinating searchers. In a series of papers [START_REF] Alon | Many Random Walks Are Faster Than One[END_REF][START_REF] Cooper | Multiple Random Walks in Random Regular Graphs[END_REF][START_REF] Elsässer | Tight bounds for the cover time of multiple random walks[END_REF][START_REF] Efremenko | Approximation, Randomization, and Combinatorial Optimization[END_REF] several results regarding hitting time, cover time, and mixing times are established, such as a linear speedup for several graph families including expanders and random graphs.

The linear search settings, in which the boxes are linearly ordered and the objective is to find a treasure placed in a box in time that is compared to its index, are related to the cow-path problem [START_REF] Baezayates | Searching in the Plane[END_REF][START_REF] Beck | On the linear search problem[END_REF][START_REF] Kao | Searching in an Unknown Environment: An Optimal Randomized Algorithm for the Cow-path Problem[END_REF], which traditionally focused on the move complexity of a single mobile agent. In this context, it is worth pointing out [START_REF] Czyzowicz | Search on a line with faulty robots[END_REF] which considers the case of faulty agents.

Motivated by applications to central search foraging by desert ants, a parallel variant of the cowpath problem, called the ANTS problem, was introduced in [START_REF] Feinerman | Memory Lower Bounds for Randomized Collaborative Search and Implications for Biology[END_REF][START_REF] Ofer Feinerman | Collaborative search on the plane without communication[END_REF]. These latter works focus on non-coordinating searchers that start the search at a single location in a grid topology, and aim to find nearby treasures as fast as possible. In particular, it was shown therein that a speedup of O(k) can be achieved with k non-coordinating searchers, and that a linear speedup cannot be achieved unless the agents have some knowledge of k. Following [START_REF] Feinerman | Memory Lower Bounds for Randomized Collaborative Search and Implications for Biology[END_REF][START_REF] Ofer Feinerman | Collaborative search on the plane without communication[END_REF] several other aspects of the ANTS problem were studied in, e.g., [START_REF] Lenzen | Trade-offs between selection complexity and performance when searching the plane without communication[END_REF][START_REF] Cohen | Exploring an infinite space with finite memory scouts[END_REF][START_REF] Emek | Solving the ANTS problem with asynchronous finite state machines[END_REF].

Outline

The paper is organized as follows. The next section provides the formal statement of the different search problems we are interested in. This section also includes results about the robustness of non-coordinating search algorithms, hence demonstrating their interest in fault-prone environments. In Section 3, we focus on the order-invariant algorithms (i.e., algorithms which have only access to the relative order of the boxes, either in term of likelihood, or importance), and we analyse the performances of A order and A obliv . Then Section 4 focuses on the case of algorithms which are given a complete description of the distribution p as input. Algorithm A is described and analyzed in that section. The lower bound for order-invariant algorithms is established in Section 5. Finally, Section 6 includes concluding remarks, and research perspectives. The paper is complemented by an Appendix containing the proofs of technical lemmas used throughout the paper.

Model and Formalization of the Problem

Bayesian and linear search

Let us consider an infinite set of boxes B x indexed by the integers x ≥ 1, and let us assume that a treasure is hidden in one of these boxes. A searcher is an algorithm that is given the ability to query boxes sequentially, in an order that is specified by the algorithm. The trivial search algorithm consists of querying box B t at step t ≥ 1. The result of a query to box B x is a boolean b x returning whether this box contains the treasure or not (hence, there is a unique x such that b x = true).

Given k ≥ 1, a k-searcher algorithm is a parallel algorithm performed concurrently by k searchers. The algorithm A coord lets searcher s i , i ∈ {1, . . . , k}, query box B k(t-1)+i at step t ≥ 1. This algorithm assumes the capacity to fully coordinate the searchers. Instead, this paper focuses on non-coordinating algorithms, that is, parallel algorithms in which each searcher performs individually the same algorithm, obliviously to the behaviors of the other searchers. During the execution of this type of algorithm, a searcher may reopen a box that has been opened before by another searcher. This is not noticeable by the former as querying a box lets no trace visible from the other searchers. In particular, two or more searchers may query the same box at the same time, but, to the perspective of each searcher, this is as if it is querying the box alone. Given a parallel algorithm A, we denote by T k (A, x) the expected time until at least one of the k searchers executing A visits B x for the first time, that is, T k (A, x) is the expected number of steps until at least one searcher queries box B x . (The expectation is taken over all the random choices made by the searchers during their execution). From this point on, for the sake of simplifying the notations, we shall not explicitly mention the number of searchers k in the notations. So, formally,

T(A, x) = ∞ t=0 Pr[B x was not queried by time t]. (6)
In this paper, we consider two scenarios regarding the way the treasure is placed in one of the boxes.

Bayesian search. The treasure is placed according to some probability distribution p over the positive integers, i.e., p(x) ≥ 0 for every x ≥ 1, and x≥1 p(x) = 1. We consider the cases in which the algorithm may or may not be given the distribution p as input. However, we always assume that the algorithm is given the relative likelihood of the boxes as input. Hence, we systematically assume that the boxes B x , x ≥ 1, are indexed such that p(x + 1) ≤ p(x) for every x ≥ 1. In this scenario, we focus on the expected time for finding the treasure, that is, we focus on the average complexity

T avg (A) = x≥1 p(x) T(A, x).
In the context of Bayesian search, we systematically assume that the distribution p satisfies

x≥1 x p(x) < ∞.
Linear search. The treasure is placed at an arbitrary position. In this scenario, the index of a box reflects its "importance" with respect to finding the treasure in it. The performances of the non-coordinating algorithms are thus compared to the position of the box where the treasure stands because this is the time a single searcher opening boxes in increasing order of their importance would take until it queries box B x . That is, we focus on the worst-case complexity

T worst (A) = max x≥1 T(A, x)/x.
The terminology linear search comes from the fact that the boxes are linearly ordered, and must ideally be checked in that order.

The Best Coordinating Algorithm

The performances of our algorithm will be compared to the performances of the best algorithm with full coordination, i.e., the one minimizing T avg or T worst depending on the context. Recall that Algorithm A coord lets searcher s i , i ∈ {1, . . . , k}, query box B k(t-1)+i at step t ≥ 1. Note that T(A coord , x) = x k , and therefore, 1 k EX ≤ T avg (A coord ) ≤ 1 k EX +1 where X is distributed according to p, and T(A coord , x)/x → 1 k when x → +∞. These facts express that, for both settings, A coord has essentially a speed up of k compared to a single searcher opening boxes in increasing order of their indices, up to additive constants.

Lemma 1. A coord has optimal search time among coordinating algorithms, for both Bayesian search, and linear search.

Proof. Let k ≥ 1. Because we allow coordination, any randomized search algorithm is centralized, and thus can be seen as a distribution over deterministic search algorithms. It follows that it is enough to consider deterministic search algorithms. W.l.o.g, as this cannot harm the running time, one can restrict our analysis to algorithms that check each box only once, and for which there are exactly k boxes that are checked at each step. Let OPT be an optimal algorithm. The infinite sequence T(OPT, 1), T(OPT, 2), . . . contains exactly k copies of each positive integer. In the random placement scenario, let us consider a distribution p. Since p(x) is a non-increasing sequence, it follows from the Rearrangement inequality that T avg (OPT) = x p(x)T(OPT, x) is minimized when the T(OPT, x)'s are arranged in a non-decreasing order, which is exactly what algorithm A coord does. Similarly, in the importance-driven scenario, T worst (OPT) = max x≥1 T(OPT, x)/x is also minimized when the T(OPT, x)'s are arranged in a non-decreasing order.

Order-Invariance and Functional View

Order-Invariance

Among all types of search algorithms, one class of algorithms is particularly appealing in the context of non-coordinating algorithms: the class of order-invariant algorithms. We say that two distributions p and p over the positive integers have similar shapes if, for every two integers x and y, we have:

p(x) ≤ p(y) ⇐⇒ p (x) ≤ p (y).
Definition 2. A search algorithm A is order-invariant if, for any two distributions p and p over the positive integers with similar shapes, the queries performed by A for p and p are identically distributed.

By definition, order-invariant algorithms act the same for all distributions. We will show that some simple order-invariant algorithms are extremely efficient, and therefore practical.

Functional View

The notion of functional view of a search algorithm, defined below, is a central notion in our analysis. Definition 3. Given a non-coordinating search algorithm A, the functional view of A is the function

N : N + × N → [0, 1] defined as N (x, t) = Pr[B x
was not yet checked by time t by searcher s i ] where s i is an arbitrary searcher performing A.

Hence, the probability that none of the k searchers checked x by time t is N (x, t) k , and thus, by Eq. ( 6),

T(A, x) = ∞ t=0 N (x, t) k .
As we shall throughout the paper see, the information encoded in this functional view of A is all that is needed to assess its running time (both in term of lower and upper bounds).

Competitive analysis

Lemma 1 yields the following definition for analyzing the performances of non-coordinating algorithms, independently from which of the two scenarios we consider, i.e., Bayesian search and linear search.

Definition 4. Let c ≥ 1. A Bayesian search algorithm A is c-competitive if there exists a constant b ≥ 0 such that T avg (A) ≤ c T avg (A coord ) + b. Similarly, a linear search algorithm A is c-competitive if there exists a constant b ≥ 0 such that T worst (A) ≤ c T worst (A coord ) + b. Lastly, an algorithm A is pointwise c-competitive if there exists a constant b ≥ 0 such that, for every x ≥ 1, T(A, x) ≤ c T(A coord , x) + b.
The different notions of competitiveness described in Definition 4 are related as follows:

Lemma 5. For both Bayesian search and linear search, if a search algorithm is pointwise c-competitive, then it is c-competitive.

Proof. Let k ≥ 1, and let us consider any distribution p. For all x, T(A, x) ≤ c T(A coord , x) + b. Therefore, in the Bayesian search, we have

T avg (A) = x≥1 p(x)T(A, x) ≤ x≥1 p(x) (c T(A coord , x) + b) = c T avg (A coord ) + b.
Similarly, in the linear search,

T worst (A) = max x≥1 T(A, x)/x ≤ max x≥1 (c T(A coord , x)/x + b/x) ≤ c T worst (A coord ) + b,
which completes the proof.

The following section about robustness also serves as a warm up for the proof techniques in the paper.

Robustness

We conclude the section by some remarks on the robustness of non-coordinating algorithms. We have already observed that non-coordinating search algorithms are inherently robust with respect to crashes of searchers. We now point out that, for coordinating search, even a small difference in the boxes' order may be devastating to some algorithms (such as A coord ). We show that, in the case of non-coordinating algorithms, this actually has little effect, as long as the biases are not too large. For every x ≥ 1, let us denote by σ s (x) the index of box B x in the "eyes" of searcher s i , i ∈ {1, . . . , k}. We call σ the resulting disordering, and we denote by T σ (A, x) the expected time to check B x when running an algorithm A under this disordering. We denote by

σ(x) = 1 k k i=1 σ s i (x)
the average placing of x according to σ. In essence, we show that if a non-coordinating algorithm is c-competitive, then it is also c-competitive under disordering of the boxes. More specifically: Theorem 6. Assume that a non-coordinating search algorithm A is pointwise c-competitive, and let σ be some disordering of the boxes. Then, there exists a constant b such that, for every x ≥ 1,

T σ (A, x) ≤ c T (A coord , σ(x)) + b.
Proof. Since A is c-competitive, there exists a constant a such that, for every x ≥ 1, T(A, x) ≤ c T(A coord , x) + a. Recall that N denotes the functional view of A, i.e., N (x, t) denotes the probability that a fixed searcher s i running A did not check box B x by time t (when the boxes are ordered correctly). The probability that none of the searchers checked box x by time t in the disordered setting is

N (σ 1 (x), t) • • • N (σ k (x), t).
On the other hand, we have

T σ (A, x) = ∞ t=0
Pr [x was not checked by time t] .

Therefore,

T σ (A, x) = ∞ t=0 N (σ 1 (x), t) • • • N (σ k (x), t) ≤ ∞ t=0 N (σ 1 (x), t) k 1 k • • • ∞ t=0 N (σ k (x), t) k 1 k
where the inequality follows from a generalized form of Hölder's inequality [START_REF] Finner | A Generalization of Holder's Inequality and Some Probability Inequalities[END_REF]. Since

T(A, x) = ∞ t=0 N (x, t) k ,
we get from the above that

T σ (A, x) ≤ k s=1 T(A, σ s (x)) 1 k .
Using the AM-GM inequality for the second step below, it follows that

T σ (A, x) ≤ k s=1 a + c σ s (x) k 1 k ≤ 1 k k s=1 a + c σ s (x) k = a + c k k s=1 σ s (x) k ≤ a + c + c k k s=1 σ s (x) k ≤ a + c + c k σ(x) ≤ a + c + c σ(x) k = a + c + cT (A, σ(x)) .
Hence, T σ (A, x) ≤ c T (A, σ(x)) + (a + c) as claimed (with b = a + c).

Example 7. Assume that σ(x) = x + o(x), i.e., on average, the mistakes in ordering are not too large. In this case, Theorem 6 gives:

T σ (A, x) ≤ c T (A coord , σ(x)) + b = c σ(x) k + b = (c + o(1)) x k + b = (c + o(1))T (A coord , x) + b
where the o(1) term goes to 0 when x goes to infinity. So, by Lemma 5, even under reasonable disordered conditions, where the average conceived ordering of a box is not too far from its correct place, we can achieve a competitiveness that is close to the competitiveness obtained assuming the boxes are perfectly ordered.

One cannot expect this same slight deterioration in competitiveness if boxes are disordered to be at a linear distance from where they truly are, and not at a sub-linear one. This is clear since our definition of disordering allows searchers to have "fake" boxes, i.e., boxes that have no corresponding true box. For example, let A have a true pointwise competitiveness of c, i.e., there is an infinite number of x's such that T(A, x) ≥ cT(A coord , x). Take σ such that for all i and all x, σ i (x) = ax for some constant a > 1.

Then, for all these x's:

T σ (A, x) = T(A, ax) ≥ cT(A coord , ax) ≈ acT(A coord , x).
As this is true for an infinite number of x's, the linear competitiveness of A is ac.

Non-Coordinating Search in Ordered Boxes

In this section we consider the setting in which only the ordering of boxes is known to the algorithm designer. This ordering may come from an a priori ordering of the boxes according to their "importance" (like in linear search), or be induced by the relative likelihood of the boxes coming from some unknown distribution p (like in Bayesian search). We design two algorithms, A order and A obliv , and analyse their performances. Both will be shown to be highly competitive. While A order achieve better competitive ratio (in fact, this competitive ratio will be shown to be optimal in Section 5), A obliv is essentially memoryless, and its simplicity and efficiency make it an outstanding candidate for real life purposes.

Order-Invariant Algorithms

In this subsection, we study the competitiveness of the order-invariant non-coordinating algorithm A order , defined hereafter.

Algorithm A order (as performed by each searcher):

I ← ∅ for t = 1 to ∞ do pick a index x uniformly at random in {1, . . . , t 2 (k +1)}\I. I ← I ∪ {x} open box B x
Before analysing the performances of the algorithm, we first establish the following technical lemma. Asymptotically, it is a known property of the Gamma function, but we will need this inequality for small a and b as well. The technical proof is deferred to Appendix A.

T avg (A order ) ≤ 4 1 - 1 k + 1 2
T avg (A coord )+10, and T worst (A order ) ≤ 4 1 -

1 k + 1 2 T worst (A coord )+10.
Proof. Using Lemma 5, it is sufficient to show that, for every x,

T(A order , x) ≤ 4 1 - 1 k + 1 2 T(A coord , x) + 10.
For avoiding distinguishing odd and even time steps, count the time by grouping two consecutive steps, so at each step t, A order chooses two distinct new boxes in {1, . . . , t(k + 1)}. We shall double the time later in the analysis, for balancing this acceleration of A order . (Note that the speeded up A order might actually end mid-step, but this just yields an over estimation of its performances). The number of elements the algorithm chooses from at step t is (k + 1)t -2(t -1) = (k -1)t + 2. Box x starts to have some probability of being checked at time s = x/(k + 1) , and for t ≥ s the probability of x not being checked by time t is:

t i=s 1 - 2 (k -1)i + 2 k = t i=s (k -1)i (k -1)i + 2 k = t i=s i i + 2 k-1 k .
We claim that the product inside the parenthesis is at most s+1 t 2 k-1 . Two cases:

1. k ≥ 3. In this case, 2/(k -1) ≤ 1, and so by Lemma 8 the product is at most:

s t 2 k-1 ≤ s + 1 t 2 k-1 .
2. k = 2. In this case, 2/(k -1) = 2. If s = t then the claim is clearly true, as the product is at most 1, and ((s + 1)/t) 2 ≥ 1. Otherwise, the product is telescopic,

t i=s i i + 2 = s(s + 1) (t + 1)(t + 2) ≤ (s + 1) 2 t 2 .
Denoting a = 2k/(k -1), the expected running time T(A order , x) is then at most (times 2):

∞ t=0 Pr [x not checked by time t] ≤ s + 2 + ∞ t=s+2 s + 1 t a .
As ((s + 1)/t) a is decreasing with t, we can bound the sum from above by taking the integral but starting it at s + 1 and not s + 2. This gives the upper bound of:

s + 2 + ∞ s+1 s + 1 t a dt = s + 2 + (s + 1) ∞ 1 t -a dt = s + 2 + s + 1 a -1 = 1 + (s + 1) 1 + 1 2k k-1 -1 = 1 + x k + 1 + 1 1 + k -1 k + 1 ≤ 1 + x k + 1 + 2 2k k + 1 ≤ 5 + 2k (k + 1) 2 x ≤ 5 + 2k 2 (k + 1) 2 x k .
Multiplying by bound by 2 to rebalance the acceleration of A order yields the result.

Memory Efficient Version

In Algorithm A obliv , every searcher performs obliviously to what it has done at previous steps (it just has to count steps):

Algorithm A obliv (as performed by each searcher): for t = 1 to ∞ do pick one index x uniformly at random in {1, . . . , t 2 k} open box B x Theorem 10. For every distribution p, every k ≥ 1, and every non-coordinating algorithm A, T avg (A obliv ) ≤ 4 T avg (A coord ) + 2, and T worst (A obliv ) ≤ 4 T worst (A coord ) + 2.

Proof. The proof proceeds in a very similar manner to that of Theorem 9, yet is in fact a little simpler. Again, by Lemma 5, it is sufficient to show that, for every x,

T(A obliv , x) ≤ 4 T(A coord , x) + 2.
As in the proof of Theorem 9, we count time by grouping two consecutive steps, resulting in A obliv independently picking two indices i and j uniformly at random in {1, . . . , kt} at every step t. Box x starts to have some probability of being checked at time s = x/k , and for t ≥ s the probability of B x not being checked by time t is:

t i=s 1 - 1 ki 2 k ≤ t i=s 1 - 1 ki + 1 2k = t i=s i i + 1 k 2k ≤ s t 2 ,
where the last inequality is by Lemma 8. The expected running time for x is then at most (times 2):

s + 1 + ∞ t=s+1 s t 2 .
As (s/t) 2 is decreasing with t, we can bound the sum from above by taking the integral, but starting it at s and not s + 1. This gives the upper bound of:

s + 1 + ∞ s s t 2 dt = s + 1 + s ∞ 1 1 t 2 dt = 2s + 1.
Multiplying by 2 gives the result.

Bayesian search with complete knowledge

Ignoring the small additive term in Theorem 9, as k grows larger, A order is about 4 times worse than the best coordinating algorithm. In this section we show that it is possible, for some distributions, to improve on this if the exact distribution is given as input to the algorithm, by designing an optimal algorithm for this setting. We denote this algorithm A .

The Case of Uniform Distributions

The first example that comes to mind is when the treasure is uniformly placed in one of the boxes {1, . . . , M }. The most natural algorithm in this case is that each searcher, at each step, chooses uniformly between all boxes it did not check already. As we will show, this is exactly what algorithm A does, and since we will show it is optimal, then the optimality of this natural algorithm follows. The analysis is simple, and we approximate it here for the case where M k.

T avg (A ) = M t=0
Pr [treasure not found by time t]

= M t=0 t-1 i=0 1 - 1 M -i k = M t=0 t-1 i=0 M -i -1 M -i k = M t=0 M -t M k = 1 M k M i=0 i k ≈ 1 M k M k+1 k + 1 = M k + 1 .
Note that with coordination, the expected running time would be approximately M/2k, so we lose about a factor of 2 by non-coordination as opposed to 4 in the case of Algorithm A order . This algorithm is memory intensive, yet if we choose to simplify and just choose uniformly at random a box from all boxes at each step, we get that the running time is practically the same for large M :

∞ t=0 1 - 1 M kt = 1 1 -1 -1 M k ≈ M k .

Preliminaries

Let us fix some distribution p over the positive integers, and let us consider a non-coordinating algorithm A that is running on k searchers. Recall (cf. Definition 3) that the fucntional view N of A is defined by N (x, t) = Pr[B x was not already checked by time t by s] where s is an arbitrary searcher performing A.

Observation 11. The functional view N of A satisfies N (x, 0) = 1 for all x ≥ 1, and, for all x ≥ 1 and t ≥ 1, N (x, t) = N (x, t -1) • Pr[x is not checked at time t | x was not checked by time t -1].

Let us now consider such functions N on their own, possibly without a corresponding algorithm. So, let N : N + × N → [0, 1], and, for time t ≥ 0, let us consider

C N (t) = x≥1 (1 -N (x, t)).
Note that all our sums over x are only over boxes with p(x) > 0. In the case of an algorithm A, C N (t) is the expected number of elements that were checked by time t by just one of the searchers running A, and is therefore at most t. We say that N satisfies the column requirement at time t if

C N (t) ≤ t.
We define the set V of valid functions as:

V = N : N + × N → [0, 1] ∀t, C N (t) ≤ t .
So functions N corresponding to algorithms are always valid. Finally, the running time of a valid function N is

T(N ) = x≥1 p(x) t≥0 N (x, t) k = t≥0 x≥1 p(x)N (x, t) k .
The running time of N is thus defined so that T(N ) is indeed the expected running time of algorithm A when N is the functional view of A. Indeed,

T(A, x) = t≥0 Pr [x was not found by time t] = t≥0 N (x, t) k .
Example 12. Consider A order when set to run on two searchers. At t = 1 it picks uniformly from one of the boxes {1, 2, 3}, and at t = 2 chooses another one out of the two not chosen. It then picks uniformly from one of the four remaining boxes of {1, . . . 6}, and then again. The following is a functional representation corresponding to to this part of the algorithm. Note that the column requirement is satisfied with equality, owing to the fact that A order never rechecks a box.

A order = t→ x↓ 0 1 2 3 4 1 1 2 /3 1 /3 1 /4 1 /6 2 1 2 /3 1 /3 1 /4 1 /6 3 1 2 /3 1 /3 1 /4 1 /6 4 1 1 1 3 /4 1 /2 5 1 1 1 3 /4 1 /2 6 1 1 1 3 /4 1 /2
To lower bound the running time of algorithms, we find the optimal N ∈ V, in the sense that it minimizes T(N ). For that, we introduce an important lemma, that we call the Presentation Lemma for it provides a presentation of the optimal function we are looking for. At this point only a simple version of the Presentation Lemma is needed, yet we present it in its full generality, as it will be needed later in the paper. The notations adopted for the Presentation Lemma are taken from Measure theory, for two reasons at least. First, we need to apply the lemma to different settings, corresponding to different measure spaces. Second, and more importantly, our optimization methodology requires compactness arguments, which are perfectly expressed in measure theory.

Fix some k ≥ 2, and let (X, X , µ) be a measure space. For T ≥ 0, let

V (T ) = {f : X → [0, 1] measurable, such that (1 -f ) dµ ≤ T }.
For any measurable function c : X → [0, ∞), and for any real α ≥ 0, let us define the function

f c,α : X → [0, 1]
as:

f c,α (x) = 1 if c(x) = 0, min 1, α c(x) -1 k-1
otherwise.

The proof of the Presentation Lemma can be found in Appendix B.

Lemma 13.(Presentation Lemma) Let c : X → [0, ∞) be a measurable function, and let

T ≥ 0. If there is some h ∈ V (T ) such that c h k dµ < ∞, then α = min {β ≥ 0 | f c,β ∈ V (T )} exists, and, for every g ∈ V (T ), c f k c,α dµ ≤ c g k dµ. Furthermore, if α = 0 then (1 -f c,α ) dµ = T .
This lemma is quite technical, but its purpose is given the weights c(•) of the elements of X, to find the f : X → [0, 1], that minimizes x c(x)f (x) k . All this under a simple linear constraint on f . This is exactly what we need.

As intuition for the proof of the lemma, assume X is a finite set, and consider some x and y where f is not zero. Let us change f slightly, by setting f (x) = f (x) + and f (y) = f (y) -, for some small . This maintains the linear constraint, and changes the sum we wish to minimize by:

c(x) (f (x) + ) k -f (x) k + c(y) (f (y) -) k -f (y) k .
Taking the derivative w.r.t. , this is k times:

c(x)(f (x) + ) k-1 -c(y)(f (y) -) k-1 .
If f indeed minimizes the final sum, then at = 0 this is supposed to be 0. Therefore, c(x)f (x) k-1 = c(y)f (y) k-1 . Put differently, fixing one y, and taking any x, f (x) = αc(x) -1/(k-1) , where α = f (y)c(y) 1/(k-1) . Therefore, we see the form of the function as stated in the Lemma.

Towards finding the optimal N ∈ V, fix some t ≥ 0. Our aim is to minimize x≥1 p(x)N (x, t) k . This can be done for each t completely separately, where the Presentation Lemma comes into play. Let {1, . . . , M } be the support of the distribution p, where

M = max{x ≥ 1 | p(x) > 0}
if this maximum exists, and M = +∞ otherwise. Recall that a function L satisfies the column requirement at time t if C L (t) ≤ t. Lemma 14. The following function L is in V, and achieves minimal T(•) over all valid functions.

L(x, t) =      0 if t ≥ M , 1
if t < M and p(x) = 0, min{1, α(t)q(x)} otherwise, where q(x) = p(x) -1 k-1 , and, for all t < M , α(t) is such that C L (t) = t.

Proof. For t ≥ M , L satisfies the column requirement and is clearly optimal. Fix t < M . Setting X = N + with the trivial measure µ(x) = 1 for all x, T = t, and c = p, Lemma 13 gives the form of the optimal function for this specific t, which is as it appears in L. In this case α(t) = 0 because otherwise the column requirement is not satisfied, and so, by the last part of Lemma 13, C L (t) = t.

To check the condition of Lemma 13, take the constant function h(x) = 1. Clearly h ∈ V (t), and

ch k dµ = x p(x) = 1 < ∞.
Example 15. Let us consider a simple example: k = 2, p(1) = 1/2, p(2) = 1/3, and p(3) = 1/6, with M = 3. In this case, q(1) = 2, q(2) = 3 and q(3) = 6, and some quick calculations show that α(1) = 1/5, α(2) = 1/11, and α(3) = 0. This gives:

L = t→ x↓ 0 1 2 3 1 1 0.4 2 /11 0 2 1 0.6 3 /11 0 3 1 1 6 /11 0

The Optimal Algorithm A

Although it may seem that every valid function N has a corresponding algorithm, it is not at all clear, because the conditional probabilities arising from Observation 11 quickly become complicated for general N when t increases. However, it turns out that because of the specific structure of the function L in Lemma 14, there is in fact an algorithm that has L as its functional view. We next present Algorithm A , as depicted in Algorithm 1, which, given p, calculates the function L, and randomly chooses boxes so as to get L as its functional view.

Let us start with an informal explanation of Algorithm A . At step t ≥ 1, the first thing A does is to calculate the values of L(x, t) for all x, so that it can recreate them with its random choices. For that A needs to calculate α(t), which, by Lemma 14, means solving the equation:

t = C L (t) = x≥1 (1 -L(x, t)) = x≥1 (1 -min{1, α(t)q(x)}). (7)
Algorithm 1 Algorithm A for k ≥ 2 searchers, as executed by one of these searchers. I ← ∅ set of already opened boxes ac(0) ← 0 ac(t) denotes the set of boxes susceptible to be opened at step

t for t = 1 to M do M = max{x ≥ 1 | p(x) > 0} can be ∞ y ← ac(t -1)
Calculate the set ac(t) of "active" boxes at step t while y < M and y+1

x=1 (1 -q(x)/q(y)) ≤ t do y ← y + 1

q(x) = p(x) -1 k-1 ac(t) ← y
The search space is {1, . . . , ac(t)} at step t α(t) ← (ac(t) -t)/ ac(t)

x=1 q(x)
Calculate α(t) for x = 1 to ac(t) do

Set the probability of choosing x if x / ∈ I then for boxes which have not been opened at previous steps

if x ≤ ac(t -1) then ϕ(x) ← 1 -α(t)/α(t -1)
all these boxes get same chance being opened else ϕ(x) ← 1 -α(t)q(x) new active boxes get decreasing chances of being opened pick x ∈ {1, . . . , ac(t)} \ I according to the probability distribution ϕ Choose one index

I ← I ∪ {x} remember this index open box B x look for treasure
To calculate α(t), the first thing to do is to figure out which indices x actually contribute to the sum above. Say box x is active at time t if L(x, t) < 1. As L is non-decreasing in x, there is some ac(t), s.t. the set of active boxes at time t is {1, . . . , ac(t)}. To calculate ac(t), A gradually decreases α(t), while keeping the column requirement satisfied. A box x is active when α(t) < 1/q(x), and so to see which box is active, A needs only to check α(t) = 1/q(1), 1/q(2), . . .. Once ac(t) is found, solving Eq. ( 7) and finding α(t) is straightforward.

Once L(x, t) is calculated, A randomly chooses a box to check according to the functional view L, using the fact that, up to step t, the probability that box x was not checked is L(x, t -1). If a box was not active, and now is, then clearly it should be checked with probability 1 -q(x)α(t). If it was already active, then it should change from q(x)α(t -1) to q(x)α(t), which, by Observation 11, means it should be checked with probability 1 -α(t)/α(t -1).

Remark. As an interesting side note, observe that at each step, all previously active yet unchecked boxes get the same probability of being checked in A . Moreover, this probability does not depend at all at the previous choices made by the algorithm. This point sounds counter-intuitive from a Bayesian point of view, as we would expect a rescaling of the probabilities that differs according to the history we have already seen. Another important point is that A has at each step a finite set of boxes to choose from. As p goes to 0, q goes to infinity, and so if there are an infinite number of active boxes, then α must be 0, but that means that all boxes were surely checked. Lastly, note that in the case of the uniform distribution of Section 4.1, as q(x) is equal for all boxes, a searcher running A will at the first step choose among them uniformly, and continue to do so at each step, choosing from those that it did not check yet. Thus, A is indeed the natural algorithm for this distribution as analysed there.

We now show that A is well defined, and is optimal.

Theorem 17. A is well defined, and, for every distribution p, every number of searchers k ≥ 2, and every non-coordinating algorithm A, we have T avg (A ) ≤ T avg (A).

Proof. Note that y ≤ ac(t) if and only if α(t) < 1/q(y), and so, to calculate ac(t), it is enough to check values for α(t) that are equal to 1/q(y) for y > ac(t -1). Once we know ac(t), by Lemma 14:

t = 1≤x≤ac(t) (1 -α(t)q(x)).
Solving this for α(t) is what the algorithm does. To show that the next part of A is at all valid, we show that the probabilities of each step add up to at most 1. The number of boxes that were already active at step t -1, and were not checked yet at step t is ac(t -1) -(t -1). So, summing all the probabilities of the different boxes, we get (ac(t -1) -t + 1) 1 -α(t) α(t -1) + ac(t-1)<x≤ac(t)

(1 -α(t)q(x)).

Again, by Lemma 14, we get

1≤x≤ac(t-1) α(t -1)q(x) = t -1 =⇒ 1≤x≤ac(t-1) α(t -1)q(x) = ac(t -1) -t + 1.
Plugging this is Eq. ( 8), the sum of the probabilities is

ac(t-1) x=1 (α(t -1) -α(t))q(x) + ac(t) x=ac(t-1) 1 -α(t)q(x) = ac(t) x=1 (1 -α(t)q(x)) - ac(t-1)
x=1

(1 -α(t -1)q(x)).

By Lemma 14 the first sum is t, and the second is t -1, and so the sum of probabilities is indeed 1.

It remains to show that indeed the functional view of A is L. This is proved by induction on t. Let N be the functional view of A . For t = 0, L(x, 1) = N (x, 1) for all x ≥ 1. Assume equality for t -1, and we prove it for t. For x ≤ ac(t -1), we have N (x, t -1) = L(x, t -1) = α(t -1)q(x). Using Observation 11:

N (x, t) = N (x, t -1) • α(t) α(t -1) = α(t -1)q(x) • α(t) α(t -1) = L(x, t).
For ac(t -1) < x ≤ ac(t), N (x, t) = L(x, t) is straightforward. It follows that A is well defined. The optimality of A directly follows from Lemma 14.

Optimal competitiveness

The purpose of this section is to show that A order has optimal competitive ratio among order-invariant algorithms, with respect to A coord , by proving the following result:

Theorem 18. For every k ≥ 1, and every order-invariant non-coordinating algorithm A, if there exist b and c such that

T avg (A) ≤ c T avg (A coord ) + b or T worst (A) ≤ c T worst (A coord ) + b, then c ≥ 4 1 -1 k+1 2 .
The remaining of this section is entirely dedicated to the proof of Theorem 18

Preliminaries

Instead of the set of functions in V defined in Section 4.2, we consider a more general class of functions. For a measurable set X, we define

F(X) = {N : X × N → [0, 1] | N (•, t
) is measurable for every fixed t ∈ N} .

For a function N ∈ F(X), we say that N satisfies the column requirement if, for every t ≥ 0,

C N (t) = X (1 -N (x, t)) dx ≤ t.
Such a function N is called valid, and V(X) is the set of all valid functions in F(X). Given an integer k ≥ 2, and some measurable function ρ : X → [0, ∞), let us define

U(N ) = ∞ t=0 X ρ(x)N (x, t) k dx.
This definition of U for functions N is equivalent of T avg for algorithms A, but is "unnormalized", as ρ is not necessarily a distribution. The following result shows a connection between algorithms and valid functions.

Lemma 19. For every non-increasing distribution p on N + , and every algorithm A for k ≥ 2 searchers, there is a function

L ∈ V([1, ∞)) such that U(L) ≤ T avg (A), where ρ : [1, ∞] → [0, ∞)
is any nonincreasing measurable function that agrees with p on integer values.

Proof. For every x ∈ [1, +∞), and t ∈ N, let us define L(x, t) = N ( x , t) where N is the functional view of A. For any t ∈ N, we have

C L (t) = ∞ 1 (1 -N ( x , t)) dx = ∞ x=1 (1 -N (x, t)) = C N (t) ≤ t.
So L satisfies the column requirement. Next,

U(L) = t≥0 ∞ 1 ρ(x)N ( x , t) k dx ≤ t≥0 ∞ 1 p( x )N ( x , t) k dx = t≥0 ∞ x=1 p(x)N (x, t) k = T avg (A),
as claimed.

Lemma 19 shows that lower bounding the "running time" of functions in V([1, ∞)) will lower bound the running time of algorithms.

The Plan

The plan is to show that for every > 0 there is some distribution p on N + such that for any algorithm A,

lim inf →0 T avg (A) T avg (A coord ) ≥ 4 1 - 1 k + 1 2 ,
and lim →0 T avg (A coord ) = ∞. This will prove the theorem. So, let us fix some > 0, and set

I = ∞ x=1 1 x 2+ -1 and J = ∞ x=1 1 x 1+ -1
. Also set p(x) = p (x) = I/x 2+ . We have

T avg (A coord ) = ∞ x=1 I x 2+ x k ≤ ∞ x=1 I x 2+ x k + 1 = I k ∞ x=1 1 x 1+ + ∞ x=1 I x 2+ = I kJ + 1 < ∞. (9)
However, as tends to 0, I tends to some constant, and J goes to 0, hence T avg (A coord ) tends to infinity, as desired.

Define ρ : [1, ∞) → [0, ∞) by ρ(x) = I/x 2+ . So ρ agrees with p on x ∈ N + . By Lemma 19, there is some L ∈ V([1, ∞)) such that U(L) ≤ T avg (A). Therefore, it is enough to prove that for any

N ∈ V([1, ∞)), lim inf →0 kJ I U(N ) ≥ 4 1 + 1 k + 1 2 , (10)
where the +1 in Eq. ( 9) is omitted as it is insignificant in the limit. The question is then: among all functions N satisfying ∞ 1

(1 -N (x, t)) dx ≤ t for every t ∈ N, [START_REF] David | Optimal sequential search: A bayesian approach[END_REF] what is the minimal value of

U(N ) = ∞ t=0 ∞ 1 ρ(x)N (x, t) k dx ? (12)

Using the Presentation Lemma

To find the N that minimizes U(N ) as in Eq. ( 12) it is enough to find an N that minimizes the inner integral for each t separately while obeying the restriction in Eq. [START_REF] David | Optimal sequential search: A bayesian approach[END_REF]. Let us again use Lemma 13 for each t separately. Fix such a t ∈ N, set X = [1, ∞] with the standard measure, c = ρ, and T = t. By the Presentation Lemma 13, an N minimizing the inner integral is

N (x, t) = min 1, αρ(x) -1 k-1 ( 13
)
where α is a function of t (and yet, for readability, we don't write α(t)). To check the condition of the lemma, take h(x) = 1. In this case,

∞ 1 (1 -h(x)) dx = 0 ≤ t, and ∞ 1 ρ(x)h(x) k dx = ∞ 1 I x 2+ dx < ∞,
as desired. From this point onwards, N will refer to this specific function.

To calculate α, we use what we know from Eq. ( 13) about what N looks like, and we rely on the refinement of Eq. [START_REF] David | Optimal sequential search: A bayesian approach[END_REF] given by the Presentation Lemma, i.e., that for all t,

• α cannot be zero, as otherwise N (x, t) = f (x) = 0 for all x, and then the constraint of Eq. ( 11) is not satisfied (no matter what t is).

• ρ is strictly decreasing in x, and it goes to 0 as x goes to infinity. Therefore, f is strictly increasing, and goes to infinity.

• Taking α = ρ(1) 1/(k-1) , means that f (1) = 1, and, by monotonicity, N (x, t) = min {1, f (x))} = 1 for all x ≥ 1. This α clearly satisfies the constraint of Eq. ( 11), and the minimality guaranteed by Lemma 13 means that the "real" α is at most this value. So f (1) ≤ 1.

• From the above, and since f is continuous, there is some unique γ ≥ 1 (which is a function of t), where f (γ) = 1. Such a γ satisfies

αρ(γ) -1 k-1 = 1 ⇐⇒ α = ρ(γ) 1 k-1 .
Since N (x, t) = min {1, f (x)}, it follows that N (x, t) is monotonically increasing until x = γ, and it remains constant equal to 1 from that point on. By Lemma 13, the constraint of Eq. ( 11) is an equality.

That is, we have

t = ∞ 1 (1 -N (x, t)) dx = γ 1 (1 -αρ(x) -1 k-1 ) dx = γ -1 - γ 1 αρ(x) -1 k-1 dx. It follows that γ -t -1 = α γ 1 ρ(x) -1 k-1 dx (14)
= ρ(γ)

1 k-1 γ 1 ρ(x) -1 k-1 dx = γ 1 ρ(γ) ρ(x) 1 k-1 dx. ( 15
)
This restriction on γ, if solved, will give us α. Let us first simplify the inner integral of U(N ) as follows:

∞ 1 ρ(x)N (x, t) k dx = γ 1 ρ(x)α k ρ(x) -k k-1 dx + ∞ γ ρ(x) dx = α k-1 γ 1 αρ(x) -1 k-1 dx + ∞ γ ρ(x) dx = ρ(γ)(γ -t -1) -R(γ), (16)
where we use Eq. ( 14) and the fact that α k-1 = ρ(γ) for the last equality, and we denote R(γ) = ∞ γ ρ(x) dx the indefinite integral. (Note that R(∞) = 0 because of the way ρ is defined).

Approximations and Calculations

Denote a = 2 + , and let us find γ from Eq. ( 15). We have

γ -t -1 = γ 1 ρ(γ) ρ(x) 1 k-1 dx = γ 1 x γ a k-1 dx = γ 1 1 γ x a k-1 dx = γ 1 1 + a k-1 x 1+ a k-1 1 1 γ = γ k -1 a + k -1 1 -γ -a+k-1 k-1 Since γ ≥ 1, and a+k-1 k-1 > 1, it follows that 0 < γ -a+k-1 k-1 < 1 γ ,
and therefore

γ k -1 a + k -1 > γ -t -1 > γ k -1 a + k -1 1 - 1 γ .
The left hand side in the above inequality bounding can be rewritten as

γ a a + k -1 < t + 1 =⇒ γ < a + k -1 a (t + 1).
Similarly, the right hand side can be rewritten

γ -t -1 > k -1 a + k -1 (γ -1) =⇒ (γ -1) a a + k -1 > t =⇒ γ > a + k -1 a t + 1.
Now examining Eq. ( 16), we get

∞ 1 ρ(x)N (x, t) k dx = ρ(γ)(γ -t -1) -R(γ) = I γ -t -1 γ a + γ 1-a a -1 = I γ a γ -t -1 + γ a -1 = I γ a a a -1 γ -t -1 ≥ I γ a a a -1 a + k -1 a t + 1 -t -1 = I (a -1)γ a (kt + 1) = Ik a -1 • t + 1 k γ a ≥ Ik a -1 • t + 1 k a+k-1 a (t + 1) a = Ik a -1 a a + k -1 a • t + 1 k (t + 1) a .
Therefore,

U(N ) ≥ Ik a -1 a a + k -1 a ∞ t=0 t + 1 k (t + 1) a .
Focusing on the sum only, and shifting it by 1, we get:

∞ t=1 t -k-1 k t a = ∞ t=1 1 t a-1 - k -1 k ∞ t=1 1 t a ≥ 1 J - k -1 k ∞ t=1 1 t 2 = 1 -o(1) J ,
where the term o(1) goes to 0 as a → 2. (This is because the second sum converges, and 1/J goes to infinity). Plugging this back in U(N ), we get

U(N ) ≥ (1 -o(1)) Ik J(a -1) a a + k -1 a .
Coming back to Eq. ( 10), we obtain lim inf

a→2 kJ I U(N ) ≥ lim a→2 k 2 a -1 a a + k -1 a = 2k k + 1 2 = 4 1 - 1 k + 1 2 .
This concludes the proof of Theorem 18.

Conclusion

In this paper, we have solved the non-coordinating Bayesian search problem by designing the optimal non-coordinating algorithm A . Given any distribution p over the integers, and given k searchers, A executes a number of queries by these k searchers which is minimum in expectation among all noncoordinating algorithms for p. We have also designed the order-invariant non-coordinating algorithm A order . The latter is far simpler than A , and has optimal competitive ratio with respect to the best coordinating algorithm, A coord , among all non-coordinating order-invariant algorithms. This competitive ratio turns out to be at most 4, demonstrating that non-coordinating algorithms are a viable alternative to coordinating algorithms, especially in a context where searchers can crash or slightly misbehave. This also holds for linear search, where the order of importance on the boxes is given a priori, and the treasure is placed at an arbitrary position.

A few questions remain open, as far as Bayesian search is concerned. In particular, we know that A is optimal, which implies that it cannot performs worse than A order , whose running time is essentially 4(1 -1 k+1 ) 2 times the one of A coord for k searchers. However, we do not know if A is often or rarely significantly better than A order . For the uniform distribution over a finite domain, we have seen that A performs roughly twice faster than A order , but we do not know whether such a factor 2 acceleration holds for many distributions. (It does not hold for all distributions, as illustrated by the distributions p described in Section 5.2). Comparing A order and A for a given distribution p is an important issue because A is significantly more complex to implement than A order . The question whether implementing A is worth the effort in terms of performances with respect to A order is therefore an important open problem in the context of non-coordinating Bayesian search.

More generally, we have focussed our interest on non-coordinating search algorithms motivated by their inherent fault-tolerance. The price to pay in terms of performances is rather limited (again, for k searchers, at most 4(1 -1 k+1 ) 2 times the optimal performance with full coordination). An interesting, and non-trivial question is to find efficient and robust algorithms that are allowed to coordinate. Our non-coordinating algorithms fall under this category, but one may potentially improve the running time by allowing coordination. Finding tradeoffs between efficiency, robustness, and amount of coordination is an intriguing open research direction. Let b ≥ 1. The proof is by induction on a, from a = b down to a = 1. If a = b, then a/(a + φ) ≤ 1, as required. Assuming the result holds for a + 1, we wish to prove that it holds for a. The l.h.s. is:

b i=a i i + φ = a a + φ • b i=a+1 i i + φ ≤ a a + φ • a + 1 b φ .
So the aim is to prove:

a a + φ • a + 1 b φ ≤ a b φ ⇐⇒ a a + φ ≤ a a + 1 φ ⇐⇒ a + φ a 1 φ ≥ a + 1 a .
Take y = 1 a ≤ 1 and x = 1 φ ≥ 1. The above is equivalent to:

1 + y x x ≥ 1 + y.
It is enough to show that the left side is increasing with x when x ≥ 1. It is increasing iff (1 + y/x) x/y is increasing. Setting z = y/x ≤ 1, as z is decreasing in x, the question is whether (1 + z) 1/z is decreasing, which is the same as showing that 1 z ln (1 + z) is decreasing. Deriving, we want

B Proof of Presentation Lemma

Lemma 13 (restated).(Presentation Lemma) Let c : X → [0, ∞) be a measurable function, and let T ≥ 0. If there is some h ∈ V (T ) such that c h k dµ < ∞, then α = min {β ≥ 0 | f c,β ∈ V (T )} exists, and, for every g ∈ V (T ), c f k c,α dµ ≤ c g k dµ. Furthermore, if α = 0 then (1 -f c,α ) dµ = T .

Proof. In what follows we will drop the subscript c in f when it is clear from context. We start by a sequences of preliminary remarks, that we label for further references.

20.

Note that all of the functions below are measurable, either by definition, or by straightforward proof. Also, as all of these functions are positive, they all have a defined Lebesgue integral, although its value may be ∞.

21.

The fact that α can be taken to be the minimal among all β's assuming we have already proved that there is some f β ∈ V (T ) that is optimal in the above respect is quite simple: α = min {β ≥ 0 | f β ∈ V (T )}, and from the assumption, this set is not empty. By monotonicity, if β < β then cf k β dµ ≤ cf k β dµ, so all what remains to be shown is that this minimum exists. If not, then there is some sequence {β n } ∞ n=1 that approaches the infimum α. By the definitions, f βn converges pointwise to f α . By Fatou's lemma:

(1 -f α ) dµ ≤ lim inf n→∞ (1 -f βn ) dµ ≤ T So f α ∈ V (T ), proving this point.

22.

Denote by S = {x ∈ X | c(x) > 0} the support of c. If T ≥ µ(S), then take α = 0. We get f 0 (x) = 0 on S, and f 0 (x) = 1 elsewhere, so (1 -f 0 ) dµ = µ(S) ≤ T , and so f 0 ∈ V (T ). Also, cf k 0 dµ = 0, and is therefore optimal, so we are done. We will therefore always assume that T < µ(S). Specifically, µ(S) > 0 and T < µ(X).

23.

For any > 0, examine the set Y = {x ∈ X | c(x) > }. We claim that µ(Y ) < ∞. Indeed, denote Z = {x ∈ X | h(x) < 1/2}. As h ∈ V (T ), we get

T ≥ (1 -h) dµ ≥ Z 1 2 dµ ≥ µ(Z) 2 .
So µ(Z) < ∞, and therefore µ(Y ∩ Z) < ∞. Also, we have

∞ > c h k dµ ≥ Y ∩¬Z c h k dµ ≥ 2 k • µ(Y ∩ ¬Z).
Together, this means that µ(Y ) < ∞.

24.

The last preliminary remark is regarding α = 0. Assume (1 -f α ) dµ < T < T . The idea here is to find some non-null set where f α can be slightly decreased, and so still be in V (T ), yet improve on the target integral, contradicting f α 's minimality. We first claim that there is some > 0, and some Y with 0 < µ(Y ) < ∞, such that for all x ∈ Y , c(x) > , and f α (x) > . Let

Y n = {x ∈ X | 1/n < c(x) < n} .

As S = ∪ n∈N Y n , and as, by 22, µ(S) > 0, it follows by sigma additivity that there is some n such that µ(Y n ) > 0. By 23, µ(Y n ) < ∞. Setting Y = Y n , and taking < 1/n guarantees c(x) > as required. Now, for every x ∈ Y , either f α (x) = 1, in which case we are fine since we can assume < 1, or f α (x) = α c(x) -1/(k-1) > α n 1/(k-1) .

Taking to be smaller than this value allows us to conclude this part regarding α = 0. Define g = f α everywhere, except on Y where it is defined as g = f α -δ, where 0 < δ < , and δ < (T -T )/µ(Y ). This means that g > 0 everywhere, and that g ∈ V (T ). Also, by this setting, we get

cf k α dµ -cg k dµ = Y c f k α -(f k α -δ) k dµ ≥ Y δ k dµ > 0
because when a > b > 0, then (a -b) k ≤ a k -b k . This contradicts the optimality of f α .

Lemma 8 .Theorem 9 .

 89 For any integers b ≥ a ≥ 1, and every real φ with 0 < φ ≤ 1, For every distribution p, and every k ≥ 1,

Example 16 .

 16 A corresponding algorithm for the function L in Example 15 is 1. choose box 1 w.p. 0.6, and otherwise choose box 2. 2. choose box 3 w.p. 5/11, and otherwise the unchosen box of 1 and 2.

3 .

 3 choose the last remaining box. Note especially step 2, where the remaining probability of 6/11 is used to check the unchosen box B from 1 and 2, and indeed, by Observation 11, (2/11)/0.4 = (3/11)/0.6 = 5/11, which is the probability of not checking B given that it was not checked up to this point.

APPENDIXA 1 Lemma 8

 18 Proof of Lemma 3.(restated). For any integers b ≥ a ≥ 1, and every real φ with 0 < φ ≤ 1,

  z) < 0 ⇐⇒ (1 + z) ln(1 + z) > z.Using the equality ln (1 + z) =

Table 1 :

 1 . Characteristics and performances of the algorithms presented in the paper. In all cases, the number k of searchers is given as input to each searcher. All algorithms but A coord run in absence of coordination.

	Algorithms		Performances	Comments
	A coord	optimal expected and worst-case running time	Bayesian and linear search
					coordination is allowed
	A	optimal expected running time	Bayesian search
		2 times slower than A coord for p ∼ Unif	distribution p is given
	A order	4 1 -1 k+1	2	times slower than A coord	Bayesian search
		optimal competitiveness w.r.t. A coord	relative likelihood is given
	A obliv	4 times slower than A coord	Bayesian search
		uses logarithmic size memory	relative likelihood is given
	A order and A obliv same competitiveness w.r.t. A coord as for Bayesian	Linear search
		A order has optimal competitiveness w.r.t. A coord
	any A non-coord	robust to inconsistencies in the box indexing	Bayesian and linear search

(1 -N (x, t)) dx = t. Again, fix a t and examine the function f (x) = αρ(x) -1/(k-1) . We observe the following:

* This work has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 648032).

Once we are done with these preliminary remarks, the proof now proceeds by a gradual increase of the generality of the function c that we handle. We start with indicator functions.

(1) Indicator functions. Let us assume that c = 1 A , the indicator function of some set A ⊆ X. By 23, we get µ(A) < ∞, and by 22, we can assume that T < µ(A). For any g ∈ V (T ):

where we used Jensen's inequality for the case where the total measure is not 1. Let us take

We get 0 < α < 1, with f α (x) = α for every x ∈ A, and f α (x) = 1 elsewhere. Also,

It follows that f α is optimal. (Note that f α is a constant function on A). We consider separately two cases.

(2) Simple functions. Let

where all c i > 0, and the X i are pairwise disjoint. By 23, we assume that all the X i are of finite measure. Given some g ∈ V (T ), let us examine it on each of the X i 's separately. Let

Restricted to X i , according to the case of indicator functions, there is some constant g i ≥ 0, such that

Thus, we define

where Y = X \ ∪ n i=1 X i . According to the above, we get

It follows that g ∈ V (T ). Also,

Therefore, g is a better candidate than g, and we can thus assume that g is constant on each of the X i 's, and hence can be written as

Our question can now be viewed as follows. Given c 1 , . . . , c n , and given µ 1 , . . .

As the solution space is compact, and as the function to minimize are continuous, there exists an optimal solution g 1 , . . . , g n . Take some i such that 1 < i ≤ n. We can rebalance the values of g 1 and g i as we wish, as long as the sum µ 1 g 1 + µ i g i remains the same. We use the following claim, whose proof is postponed at the end of the Appendix so that to keep the flow of the current proof.

where g 1 , g 2 ∈ [0, 1] and µ 1 g 1 + µ 2 g 2 = m is achieved only when

According to Claim 25, the values of g 1 and g i must satisfy:

g 1 , we obtain the desired form g i = min 1, αc -1/(k-1) i which concludes this case.

(3) The general case. Let {c n } ∞ n=1 be a non-decreasing family of simple functions that have c as their pointwise limit. According to the simple function case, for each n, there is some α n such that the function f n = f cn,αn yields minimal c n f k n dµ among all functions of V (T ). If this sequence (α n ) n≥1 is unbounded, we can keep only a sub-sequence where α n → ∞, and define f (x) = lim n→∞ f n (x) = 1 everywhere. Otherwise we can keep only a converging sub-sequence of (α n ) n≥1 , and denote its limit by α. Now, let us define the function f (x) = f c,α (x) = lim n→∞ f n (x). Either way the pointwise limit of the f n 's exists, and we denote it by f . Let us examine the sequence of functions (1 -f n ) n≥1 . Each element of this sequence satisfies (1 -f n ) dµ ≤ T . Therefore, by Fatou lemma:

Therefore, f ∈ V (T ). Moreover, the function cf k is the pointwise limit of c n f k n , and hence, as f n is optimal for c n , we get

So all these integrals are jointly bounded, and thus their lim inf exists. Therefore, by Fatou lemma again, we get

Let us assume that there is some g that is better than f . That is, there is some δ > 0 such that:

Let us then pick n large enough, and let us use the fact that f n is optimal for c n , which yields

leading to a contradiction.

The only thing left to show is that f = f c,α for some α. By 22, there is some > 0 such that the set

Moreover, by 23, we also have µ(A) < ∞. If T < µ(A), then let is pick the function g(x) = 1 -T /µ(A) on this set and g(x) = 1 elsewhere. Clearly g ∈ V (T ). Also,

As f is optimal, it cannot be the function 1 X , and this it must be of the required form. If T > µ(A), then we proceed in the same way, except that we set g(x) = 0 on A and g(x) = 1 elsewhere. This completes the proof of the Presentation Lemma.

It just remains to prove the technical Claim 25.

Proof (of Claim 25). Let c = c 2 /c 1 , and µ = µ 2 /µ 1 . Setting N = m/µ 1 , we can write the claim equivalently as follows. Assuming N ≤ 1 + µ, and knowing that g 1 + µg 2 = N , we claim that the values g 1 , g 2 ∈ [0, 1] minimizing g k 1 + cµg k 2 satisfy g 1 = min 1, c 1/(k-1) g 2 . Denoting g 2 = (N -g 1 )/µ, we want to minimize:

Let us take the derivative w.r.t. g 1 , yielding

This is zero exactly when

from which we get that

Let us now take the second derivative w.r.t. g 1 (the first derivative was expressed in Eq. ( 17)), yielding

If we consider g 1 in the range [0, N ], this second derivative is always strictly positive, meaning that our function is U-shaped. Also, by Eq. ( 18) the minimum is somewhere in [0, N ]. Recall that g 1 ∈ [0, 1]. If the minimum of the U-shape is in [0, 1] then we get the lemma. Otherwise this minimum must be somewhere in (1, N ], and so our minimum would be at g 1 = 1. Note that the minimum is unique.