{'fraction_non_alphanumeric': 0.031784695817490494, 'fraction_numerical': 0.0092680608365019, 'mean_word_length': 4.308420056764428, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Optimal random search for a single hidden target

A single target is hidden at a location chosen from a predetermined probability distribution. Then, a searcher must find a second probability distribution from which random search points are sampled such that the target is found in the minimum number of trials. Here it will be shown that if the searcher must get very close to the target to find it, then the best search distribution is proportional to the square root of the target distribution. For a Gaussian target distribution, the optimum search distribution is approximately a Gaussian with a standard deviation that varies inversely with how close the searcher must be to the target to find it. For a network, where the searcher randomly samples nodes and looks for the fixed target along edges, the optimum is to either sample a node with probability proportional to the square root of the out degree plus one or not at all.


I. INTRODUCTION
Imagine a single target hidden with some known distribution and a searcher trying to locate it by randomly drawing points from another distribution. Assuming the cost for the search only depends on the number of steps, an optimal searcher has to choose a distribution that minimizes the average number of steps to locate the target. This situation is different from the usual search paradigms in which there are many targets [1][2][3][4] and/or no knowledge of where the target may be [5,6]. When there are many targets, the solution is to perform a random walk with a Lévy flight, but that depends on expanding the search time in the distance between targets which is not possible when there is only one target [1]. Intermittent searches are optimal if there is no knowledge of the target and large steps cost more than small ones [5,[7][8][9].
The goal here is to describe the optimum guess distribution to sample to find a target, given the target distribution and assuming the searcher must be within a distance R of the target to consider it found and with no additional cost for large steps. A familiar example of this is searching with the eye for a particular target [10,11], such as a face in a crowd.
Without any guess this is a very difficult proposition, but if someone who knows where the target face is gestures, even inaccurately, toward the target, then that clue greatly improves the search. In the case of the eye, the movement is very rapid compared to identification of the target [12] so that the search time is dominated by the number of places checked rather than, for example, the total path length traversed. Also, the searcher may not see the target on the first pass, so memory is not really important. In other words, actual identification of the target is unreliable so there is no reason to avoid a spot just because the search failed there a few times. Under these assumptions, it will be shown that the optimal search distribution is different than the target distribution, and specifically, if R is small compared to the variability of the target distribution, then the search distribution is proportional to the square root of the target distribution.

II. CONTINUOUS SYSTEMS
Now consider definitions of the relevant quantities for a continuous target distribution.
Let G(x) be the unknown guess distribution, T (x) the known target distribution, and R the range over which the guess is considered to find the target. For example, if T (x) is a delta function so that the target is at x = 0, then the best guess is clearly also G(x) = δ(x) when R = 0. For non-zero R a guess anywhere on the interval [−R, R] is considered a hit, so the best guess distribution may be a boxcar from [−R, R]. For simplicity concentrate on one dimension, although generalizing to two (or more) is trivial.
For a fixed target at position x and assuming the guesses are uncorrelated (memoryless), the average number of guesses required before finding the target is just the inverse of the probability that a guess is correct. Averaging over all possible target locations gives . (1) Note that the the denominator in the integral over T (x) is non-local which is the source of some mathematical difficulties.
The optimum n is found by taking the functional derivative of G subject to the constraint that G be normalized: where α is a Lagrange multiplier. To handle the non-local integral, define a function i.e., Q(t; x, R) is a boxcar function of width 2R centered at x. Then, by the generalized chain rule for functional derivatives, or as may be verified from the definition of a functional derivative δ δG(y) n = lim By definition, Q(y; x, R) = 1 whenever |x − y| < R. Thus, Q(y; x, R) = Q(x; y, R), and note that this is regardless of dimension as long as the norm is well defined. The functional derivative simplifies to But, α is a constant and this must hold for any y, so the integrand must be a constant, and, indeed, it must be α/2R, but we can rely on some constant A to handle normalization.
Thus, solving the integrand for G(x) and noting that everything is positive (G and T are both probability distributions), whereÃ takes care of normalization. Thus, in the limit that the range becomes small the optimal guess distribution is constructed by taking the square root of the target distribution and normalizing. This is somewhat surprising because at first glance the best choice for the guess distribution would have been to match the target distribution. The square root effectively widens the search distribution and lowers the chance of sampling at the most likely position. This is advantageous because the search is completely memoryless, so the most likely target location would be oversampled in a probability matching approach, and the searcher would waste time repeatedly sampling the same site. A simple example is to imagine just two discrete target sites, one with a 99% probability of having the target and one with 1%. If the searcher probability matches, then the mean time to find the target is n = 0.99/0.99 + 0.1/0.1 = 2, and the searcher finds the target in one guess 99% of the time and looks in the wrong spot an average of 100 times on 1% of the trials. This can be improved significantly by looking at the more likely target slightly less often, say 98% of the trials, making the mean n = 0.99/0.98 + 0.1/0.2 ≈ 1.5. The improvement comes from searching at the unlikely hiding spot slightly more often, but not often enough to impact the more likely case significantly. The square root rule finds the best trade off and generalizes to more complex, continuous situations.
imate the actual value for the mean number of trials n before finding the target (equation 1). Thus, if the number of steps is too large, say greater than 2 n as human searchers seem to use [13], either the assumed target distribution is likely invalid or the target is not present, and failure is recognized. Note that this is not the case for any Lévy or intermittent search for a single target because their mean search times scale with the size of the search region [14], so failure is difficult to recognize for those cases.
To solve for G in the case when T (x) is differentiable, take a derivative: Now, redefine x → x − R, A to handle all the constants, and simplify the recursive equation to give assuming G (∞) → 0 and the sum converges. Formally, this expression correctly gives G in terms of T ; however, there are some significant practical considerations. To understand the source of the problem, consider a Gaussian target distribution: Then, plugging into equation 10, G is The problem with this expression can be seen by imagining trying to normalize G. Each term of the sum integrates to zero, but the whole thing must not integrate to zero since G is a probability distribution. This is a problem with commuting the two infinities, in the sum and the integral, shown by numeric summation of the first few terms ( figure 1). There is a negative bubble that moves off to infinity as the number of terms increases, and a Gaussian like peak that remains near zero. Thus, the limit of the sum must be taken before that of the integral.
Alternatively, since the negative bubble always moves to plus infinity, we can rely on the fact that G(x) is even because T (x) is even, and only look at x < 0. While numerically such a process works fine, it complicates the integrals considerably as far as trying to approximate G analytically. The dashed black line is the best fit Gaussian (σ = 1.3(1)) with 500 terms. Note that the fit Gaussian has so much error because the guess distribution is not exactly a Gaussian when R = 0.
To make some headway analytically, consider a Laplace transform approach. For convenience, define q(x) = A T (x), and then the bilateral Laplace transform of equation 7 where the sinh (Rs) /s prefactor can be derived easily using the same boxcar trick as before (equation 3).

A. Box car target distribution
The Laplace transform can be very difficult to invert, so equation 13 is not always useful; however, it does work for special cases of boxcar target distributions and Gaussian distributions with small R. First, consider the boxcar Up to a constant factor, the square root of a boxcar is also a boxcar, sõ Then, from equation 13G For the special case R = Q, everything cancels andG(s) ∝ 1 immediately gives G(t) = δ(0) as expected. By looking at the center of the distribution the search radius covers all possible targets and is clearly optimal.
Similarly, for R = Q/2, we can apply the hyperbolic identity sinh 2x = 2 sinh x cosh x to give after minor simplificationG

B. Gaussian target distribution
Another case of great interest is the Gaussian target distribution. In that case, notice that x/ sinh x itself looks like a Gaussian, so we can approximate it as a Gaussian by matching variances. The integral of x/ sinh x is standard, and the normalized second moment is π 2 2R 2 . Thus, the the useful approximation is a Gaussian with a matching second moment Finally, plugging in the square root of a Gaussian with standard deviation σ T for q leaves (dropping all coefficients as usual) for σ T > R/π ( figure 3A,D). For R/π > σ T the approximation breaks down. Thus, the optimal guess distribution is approximately a Gaussian with standard deviation σ G ≈ √ 2 σ 2 T − R 2 π 2 in good agreement with numerical estimates (figure 2). The dots are numerically calculated by assuming the guess distribution is a Gaussian and directly optimizing n . The line is the analytical result using the Gaussian approximation for x/ sinh x.
In both cases the target distribution is a Gaussian with units set by choosing σ T = 1.

C. Convolution
As a further example highlighting the non-local nature of the search, consider the special case where the target distribution can be written in the form of a convolution squared: where f and g are arbitrary functions such that T is a probability distribution. Then, since the Laplace transform of the convolution is the product of the Laplace transforms, Now we can combine the boxcar and Gaussian functions from before to highlight the interesting, non-local behavior. Let g be a boxcar of width nR for n > 0 an integer as before. Then, where the sum is over x i = R + 2Ri − nR and i ∈ Z n to tile the interval from [−nR, nR] evenly with subintervals of length 2R. Next, exp(as) is the Laplace transform of δ(x − a) so This can lead to some interesting effects. For example, set f ∝ exp − x 2 2σ 2 and let B Q (x) be a boxcar of radius Q centered at x, then the target function is which looks like to a Gaussian with a peak at zero. The guess distribution, on the other hand, has two peaks at ±R, and the most likely place to search does not coincide with the most likely target location (figure 3C).

III. DISCRETE SYSTEMS
While the search technique introduced here is very powerful for continuous systems, it also applies to discrete systems for which the target can only be found by looking at its site. These can be considered a special case of continuous systems, or more simply, write the discrete version of equation 1 for a set of discrete sites A: where t i are the target probabilities and g i the guess probabilities. Then, as one could guess from the general result for small search radius (equation 8), the optimum choice of g i given For R = 3 the most likely search points are at ±3, but the target is most likely at zero. Part D shows a two dimensional Gaussian target distribution (black) and the optimum guess distribution for R = 0.5. For clarity the normalization is such that the peak heights match.
A discrete set of isolated sites is quite simple, but a system of great interest and richness is networks [15,16]. On networks, one can imagine a searcher with random access to the nodes that is able to look at any node and out along the node's edges to its nearest neighbors.
This is akin to typing in a web address and checking the links on the resulting page for the target, rather than just following links from page to page. In that case, the probability of finding a single target at any given node u depends on the in-degree of the node, for each of its neighbors, plus one, for the node itself: d u + 1, and the mean search time for a target randomly hidden on some fixed node is where i is a node, and the sum in the denominator is over all nodes that have an edge pointing to i. The mean field assumption here is that the probability that the target is hidden at node i is equal to the probability of finding the target at node i so that g i ∝ 1 + d out,i , but it can fail spectacularly for graphs. As a simple example, consider a star graph with one node connected to 5 independent nodes ( figure 4, left), and hide the target on that graph with equal probability at each node. Then, the probability of finding the target by looking at the center node is 1, but the probability the target is hidden at the center node is only 1/6.
The star graph (figure 4, left) also points to an heuristic solution of the search problem because the ideal strategy is certainly to look only at the center node and not at the others, finding the target in one try every time. But, the simple approach, ignoring the graph structure, would have a finite probability of looking at the boundary nodes. Thus, the heuristic proposed here is to start from the square root of the out-degree rule and iteratively remove nodes from consideration if such a removal improves the search time: look at a node u with probability either 1 + d out,u or zero. Note that this is not very efficient since the setup time for a search is at least order the size of the graph so if the search only happens once, it would be just as good to just check every node. If there are many searches on a static network, then this algorithm may be advantageous, but it is more likely that the best search would combine the usual random search [17] with the strategy presented here as a starting point or, for an example on the internet, to choose places to randomly jump in the popular PageRank algorithm [18]. obvious best strategy is to look at the center node (large, blue) where any target is found in exactly one step. On the right is the adjnoun network [19] with nodes to be looked at labeled blue, larger, and ones that should be ignored in red, smaller. The blue nodes are found using the heuristic algorithm described in the main part.
exp (−∆ n /T ). The initial step size is δ 0 = 0.01, and the initial temperature is T = 0.01 which is large compared to the usual change in probability. After 1000 steps without finding a smaller minimum n , the temperature and step size are both lowered by a factor of two.
The simulation stops after at most 10 million iterations, T < 10 −12 , or δ < 10 −12 . Figure   5 shows the minimization for six graphs from freely available databases [19][20][21]. For larger graphs the convergence is poor, but the split between either the square root rule or nothing is apparent.

IV. CONCLUSION
In conclusion, a searcher that has random access to possible target positions and is trying to locate only a single target should sample a guess distribution as described here. If the searcher must be very close to a target continuously distributed in any dimension to locate it, then the guess distribution is approximately the square root of the target distribution. Otherwise, the guess distribution is more difficult to estimate, but can be numerically evaluated with sufficient care. On discrete networks an heuristic approach is to either look at a node with probability proportional to the square root of its out degree plus one or not at all. Determining a fast, local algorithm to decide whether or not to look at a node remains, but the search times from the heuristic compare favorably to those from a Monte Carlo estimation of the optimal search.