Optimal search for one of many objects hidden in two boxes

A discrete search model for one of many objects hidden in two boxes is studied. The number of objects is assumed to be a random variable with a known prior distribution. When box i is searched, a cost c_i > 0 is paid and the conditional probability of finding a specific object given it was hidden there is α_i. We are interested in determining a search strategy which finds at least one object with minimum expected cost. Zones of the state space for which Blackwell's rule [3] is optimal are characterized. Based on these results an algorithm for constructing an optimal search sequence is suggested and demonstrated in the case where the number of hidden objects has a geometric distribution.     

Coordinated search for an object hidden on the line

We consider the coordinated search problem faced by two searchers who start together at zero and can move at speed one to find an object symmetrically distributed on the line. In particular we fully analyze the case of the negative exponential distribution given by the density f(x) = e^−|x|μ/(2μ), μ > 0. The searchers wish to minimize the expected time to find the object and meet back together (with the object) at zero. We give necessary and sufficient conditions for the existence of an optimal search strategy when the target density is continuous and decreasing. We show that for the negative exponential distribution the optimal time is between 4.728μ and 4.729μ. A strategy with expected time in this interval begins with the searchers going in opposite directions and returning to the origin after searching up to successive distances 0.745μ, 2.11μ, 3.9μ, 6μ, 8.4μ,…. These results extend the theory of coordinated search to unbounded regions. It has previously been studied for objects hidden on a circle (by Thomas) and on an interval (by the author).     

A method for reconstructing label images from a few projections, as motivated by electron microscopy

Our aim is to produce a tessellation of space into small voxels and, based on only a few tomographic projections of an object, assign to each voxel a label that indicates one of the components of interest constituting the object. Traditional methods are not reliable in applications, such as electron microscopy in which (due to the damage by radiation) only a few projections are available. We postulate a low level prior knowledge regarding the underlying distribution of label images, and then directly estimate the label image based on the prior and the projections. We use a relatively efficient approximation to a global search for the optimal estimate.     

Variable block search with prior information

Consider the problem of optimizing an unknown, unimodal, univariate function by direct function evaluation. This article replaces the classic criterion for evaluating search strategies, minimax, by one we feel to be more practical, minimum expected final interval of uncertainty. This latter measure of effectiveness is useful when the experimenter has some prior knowledge of the underlying function and can specify a probability distribution on the location of the optimum.We show here that for a large class of search strategies under the uniform distribution, minimax is equivalent to minimum expected final interval length, i.e., the uniform distribution represents a ‘worst-case’ prior. In addition, computational procedures are develooed for determining the optimal search strategy for arbitrary a priori distributions. Several examples are included.     

On optimal search with unknown detection probabilities

An object is hidden in box i with probability P_i, for i = 1, 2,…, I. A search of a box detects the object, given that it is in the box, with probability d. The detection probability d is fixed but unknown. The asymptotic form of an optimal search policy is related to the behaviour near zero of the prior distribution for d.     

Son of the linear search problem

I wish to find something which is located on a certain road. I start at a point on the road, but I do not know in which direction the object sought is to be found. Somehow, I must incorporate in my way of searching the possibility that it is either to the right or to the left. Thus, I must search first to the right, and then to the left, and then to the right again until it is found. What is a good way of conducting this search, and what is a bad way? This general problem can be phrased in many ways mathematically, some of which are answered in the papers in the bibliography. In this paper, we consider three well-known assumptions concerning thea priori guesses for the probability distribution on where the object is located. These concern uniform distribution on an interval, triangular distribution around the original point, and normal distribution about that point. The uniform distribution has a simple answer. For the triangular distribution, we obtain qualitative results and calculate approximate values for the turning points.     

Discounted Bayesian search problems with unknown detection probabilities

In this paper we consider three discrete-time discounted Bayesian search problems with an unknown number of objects and uncertainty about the distribution of the objects among the boxes. Moreover, we admit uncertainty about the detection probabilities. The goal is to determine a policy which finds (dependent on the search problem) at least one object or all objects with minimal expected total cost. We give sufficient conditions for the optimality of the greedy policy which has been introduced in Liebig/Rieder (1996). For some examples in which the greedy policy is not optimal we derive a bound for the error.     

On a problem of optimal search

Summary A class of one-dimensional search problems is considered. The formulation results in a functional-minimization equation of the dynamic programming type. In the case of a uniform a priori distribution for the location of the hidden object an optimality criterion is established and the optimal search procedure is found.

---

Zusammenfassung Nach allgemeinen Betrachtungen über das Spektrum von Suchproblemen wird eine Klasse eindimensionaler Suchprobleme betrachtet. Die Formulierung führt zu einer Funktionalgleichung vom Typ der dynamischen Optimierung. In dem Fall einer uniformen a priori Verteilung für das Auffinden eines versteckten Objekts wird ein Optimalitätskriterium begründet und das optimale Suchverfahren angewandt.

     

Approximate solutions for expanding search games on general networks

We study the classical problem introduced by R. Isaacs and S. Gal of minimizing the time to find a hidden point H on a network Q moving from a known starting point. Rather than adopting the traditional continuous unit speed path paradigm, we use the dynamic “expanding search” paradigm recently introduced by the authors. Here the regions S(t) that have been searched by time t are increasing from the starting point and have total length t. Roughly speaking the search follows a sequence of arcs \(a_i\) such that each one starts at some point of an earlier one. This type of search is often carried out by real life search teams in the hunt for missing persons, escaped convicts, terrorists or lost airplanes. The paper which introduced this type of search solved the adversarial problem (where H is hidden to maximize the time to be found) for the cases where Q is a tree or is 2-arc-connected. This paper’s main contribution is to give two strategy classes which can be used on any network and have expected search times which are within a factor close to 1 of the value of the game (minimax search time). These strategies classes are respectively optimal for trees and 2-arc-connected networks. We also solve the game for circle-and-spike networks, which can be considered as the simplest class of networks for which a solution was previously unknown.

     

Vortex singularities of optimal strategies at the beginning of motion in search problems on <Emphasis Type="Italic">n</Emphasis>-dimensional Riemannian manifolds

This work studies optimal strategies having unexpected singularities. So, in particular, in the problem of searching for an object E on a segment that has the probability distribution function of location going to infinity to both side of a pursuer P, the modulus of whose speed does not exceed some constant, the optimal search strategy has no derivative at the initial instant of time. During an arbitrary small interval of time, the pursuer P changes the direction of his motion infinitely many times in order to be at both sides where the probability of location of E is maximal. In the case of a two-dimensional manifold, with analogous singularities of the probability distribution function of location of E, the velocity of P executes countably many turns during an arbitrary small interval of time for the optimal search (this is the reason for which such singularities are said to be vortex singularities). It is more difficult to imagine optimal strategies arising in the search on manifolds of dimension more than 2. Here, during an arbitrary small initial interval of time, the player P tends to completely inspect a neighborhood of the boundary of the visibility domain at the initial instant of time. Another unexpected phenomenon in the search problem on a segment is as follows: if the distribution function tends to zero at the endpoints of the segment, then the player P changes the direction of motion infinitely many times when approaching the endpoints of the segment. Precisely, when the probability of finding E near a given endpoint of the segment becomes sufficiently small, P runs to another endpoint of the segment, and there, not arriving at this end, he turns backward, and this occurs infinitely many times. In this case, in principle, the search can be performed arbitrarily many time, despite the fact that the inspection of the whole segment requires a fixed finite time. However, the expectation of the search time turns out to be minimal. This paper finds the formulas for switching points, and in the case of infinitely many switching points, the asymptotics of turn points is calculated. Translated from Sovremennaya Matematika i Ee Prilozheniya (Contemporary Mathematics and Its Applications), Vol. 58, Optimal Control, 2008.     

Optimal search efficiency of Barker’s algorithm with an exponential fitness function

Markov Chain Monte Carlo (MCMC) methods may be employed to search for a probability distribution over a bounded space of function arguments to estimate which argument(s) optimize(s) an objective function. This search-based optimization requires sampling the suitability, or fitness, of arguments in the search space. When the objective function or the fitness of arguments vary with time, significant exploration of the search space is required. Search efficiency then becomes a more relevant measure of the usefulness of an MCMC method than traditional measures such as convergence speed to the stationary distribution and asymptotic variance of stationary distribution estimates. Search efficiency refers to how quickly prior information about the search space is traded-off for search effort savings. Optimal search efficiency occurs when the entropy of the probability distribution over the space during search is maximized. Whereas the Metropolis case of the Hastings MCMC algorithm with fixed candidate generation is optimal with respect to asymptotic variance of stationary distribution estimates, this paper proves that Barker’s case is optimal with respect to search efficiency if the fitness of the arguments in the search space is characterized by an exponential function. The latter instance of optimality is beneficial for time-varying optimization that is also model-independent.     

Bounding the zeros of an interval equation

In this paper, we consider the problem of finding reliably and with certainty all zeros of an interval equation within a given search interval for continuously differentiable functions over real numbers. We propose a new formality of interval arithmetic which is treated in a theoretical manner to develop and prove a new method, lying on the context of interval Newton methods. Some important theoretical aspects of the new method are stated and proved. Finally, an algorithmic realization of our method is proposed to be applied on a set of test functions, where the promising theoretical results are verified.     

Arbres de Markov Triplet et fusion de Dempster–Shafer

The hidden Markov chains (HMC) (X,Y) have been recently generalized to triplet Markov chains (TMC), which enjoy the same capabilities of restoring a hidden process X from the observed process Y. The posterior distribution of X can be viewed, in an HMC, as a particular case of the so called “Dempster–Shafer fusion” (DS fusion) of the prior Markov with a probability q defined from the observation Y=y. As such, when we place ourselves in the Dempster–Shafer theory of evidence by replacing the probability distribution of X by a mass function M having an analogous Markov form (which gives again the classical Markov probability distribution in a particular case), the result of DS fusion of M with q generalizes the conventional posterior distribution of X. Although this result is not necessarily a Markov distribution, it has been recently shown that it is a TMC, which renders traditional restoration methods applicable. The aim of this Note is to present some generalizations of the latter result: (i) more general HMCs can be considered; (ii) q, which can possibly be a mass function Q, is itself a result of the DS fusion; and (iii) all these results are finally specified in the hidden Markov trees (HMT) context, which generalizes the HMC one. To cite this article: W. Pieczynski, C. R. Acad. Sci. Paris, Ser. I 336 (2003).     

Bayesian estimation of regression parameters in elliptical measurement error models

The main object of this paper is to discuss the Bayes estimation of the regression coefficients in the elliptically distributed simple regression model with measurement errors. The posterior distribution for the line parameters is obtained in a closed form, considering the following: the ratio of the error variances is known, informative prior distribution for the error variance, and non-informative prior distributions for the regression coefficients and for the incidental parameters. We proved that the posterior distribution of the regression coefficients has at most two real modes. Situations with a single mode are more likely than those with two modes, especially in large samples. The precision of the modal estimators is studied by deriving the Hessian matrix, which although complicated can be computed numerically. The posterior mean is estimated by using the Gibbs sampling algorithm and approximations by normal distributions. The results are applied to a real data set and connections with results in the literature are reported.     

Co-ordinating Two Searchers for an Object Hidden on an Interval

Two unit-speed searchers starting at 0 seek a stationary target hidden according to a known bounded symmetric distribution. The objective is to minimize the expected time for the searchers to return to 0 after one of them has found the target. We find a general optimality condition and use it to solve the problem when the target has a uniform, triangular, or truncated, exponential distribution. The problem has applications to parallel processing and to the optimal choice of drilling depths in the search for an underground mineral.     

A bayesian approach to inference for monotone failure rates

In reliability theory, the notion of monotone failure rates plays a central role. When prior information indicates that such monotonicity is meaningful, it must be incorporated into the prior distribution whenever inference about the failure rates needs to be made. In this paper we show how this can be done in a straightforward and intuitively pleasing manner. The time interval is partitioned into subintervals of equal width and the number of failures and censoring in each interval is recorded. By defining a Dirichlet as the joint prior distribution for the forward or the backward differences of the conditional probabilities of survival in each interval, we find that the monotonicity is presenved in the posterior estimate of the failure rates. A posterior estimate of the survival function can also be obtained. We illustrate our method by applying it to some real life medical data.     

第三方库存-路线问题的模型及混合遗传算法设计

根据第三方库存-路线问题的特点,以车辆租赁费用和运行费用之和为目标函数,不限制客户每次的配送量小于车辆容量,建立了满载运输和非满载运输混合的整数规划模型.针对第三方库存-路线问题的复杂性,本文设计嵌入禁忌搜索的遗传算法来同时决策库存和路线问题.首先对配送间隔进行编码,然后用禁忌搜索法计算每天需要配送的车辆路线问题.最后与其下界值进行比较,结果表明该算法是一个有效的算法,不但第三方能取得较低的运营总成本和较高的车辆利用率,而且也能为客户节约库存空间.     

On the posterior median estimators of possibly sparse sequences

We adopt the Bayesian paradigm and discuss certain properties of posterior median estimators of possibly sparse sequences. The prior distribution considered is a mixture of an atom of probability at zero and a symmetric unimodal distribution, and the noise distribution is taken as another symmetric unimodal distribution. We derive an explicit form of the corresponding posterior median and show that it is an antisymmetric function and, under some conditions, a shrinkage and a thresholding rule. Furthermore we show that, as long as the tails of the nonzero part of the prior distribution are heavier than the tails of the noise distribution, the posterior median, under some constraints on the involved parameters, has the bounded shrinkage property, extending thus recent results to larger families of prior and noise distributions. Expressions of posterior distributions and posterior medians in particular cases of interest are obtained. The asymptotes of the derived posterior medians, which provide valuable information of how the corresponding estimators treat large coefficients, are also given. These results could be particularly useful for studying frequentist optimality properties and developing statistical techniques of the resulting posterior median estimators of possibly sparse sequences for a wider set of prior and noise distributions.     

Optimal search strategies for Wienér processes

Let n independent Wiener processes be given. We assume that the following information is known about these processes; one process has drift μt, the remaining n - 1 processes have drift zero, all n processes have common variance σ²t, and we assume that a prior probability distribution over the n processes is given to identify the process with drift μt. A searcher is permitted to observe the increments of one process at a time with the object of identifying (with probability 1 - λ of correct selection) the process with drift μt.The authors define a natural class of search strategies and show that the strategy within this class which minimizes the total search time is the strategy which, whenever possible, searches the process which currently has the largest posterior probability of being the one with drift μt.