An official website of the United States government
Abstract Many physical phenomena are modeled as stochastic searchers looking for targets. In these models, the probability that a searcher finds a particular target, its so-called hitting probability, is often of considerable interest. In this work we determine hitting probabilities for stochastic search processes conditioned on being faster than a random short time. Such times have been used to model stochastic resetting or stochastic inactivation. These results apply to any search process, diffusive or otherwise, whose unconditional short-time behavior can be adequately approximated, which we characterize for broad classes of stochastic search. We illustrate these results in several examples and show that the conditional hitting probabilities depend predominantly on the relative geodesic lengths between the initial position of the searcher and the targets. Finally, we apply these results to a canonical evidence accumulation model for decision making.
more »
« less
Capacities and efficient computation of first-passage probabilities
A reversible diffusion process is initialized at position x0 and run until it first hits any of several targets. What is the probability that it terminates at a particular target? We propose a computationally efficient approach for estimating this probability, focused on those situations in which it takes a long time to hit any target. In these cases, direct simulation of the hitting probabilities becomes prohibitively expensive. On the other hand, if the timescales are sufficiently long, then the system will essentially “forget” its initial condition before it encounters a target. In these cases the hitting probabilities can be accurately approximated using only local simulations around each target, obviating the need for direct simulations. In empirical tests, we find that these local estimates can be computed in the same time it would take to compute a single direct simulation, but that they achieve an accuracy that would require thousands of direct simulation runs.
more »
« less
- Award ID(s):
- 1740741
- PAR ID:
- 10188723
- Date Published:
- Journal Name:
- Physical review
- Volume:
- 102
- ISSN:
- 2470-0045
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract A variety of systems in physics, chemistry, biology, and psychology are modeled in terms of diffusing ‘searchers’ looking for ‘targets’. Examples range from gene regulation, to cell sensing, to human decision-making. A commonly studied statistic in these models is the so-called hitting probability for each target, which is the probability that a given single searcher finds that particular target. However, the decisive event in many systems is not the arrival of a given single searcher to a target, but rather the arrival of the fastest searcher to a target out of many searchers. In this paper, we study the probability that the fastest diffusive searcher hits a given target in the many searcher limit, which we call the extreme hitting probability. We first prove an upper bound for the decay of the probability that the searcher finds a target other than the closest target. This upper bound applies in very general settings and depends only on the relative distances to the targets. Furthermore, we find the exact asymptotics of the extreme hitting probabilities in terms of the short-time distribution of when a single searcher hits a target. These results show that the fastest searcher always hits the closest target in the many searcher limit. While this fact is intuitive in light of recent results on the time it takes the fastest searcher to find a target, our results give rigorous, quantitative estimates for the extreme hitting probabilities. We illustrate our results in several examples and numerical solutions.more » « less
-
We show that the entire class of polar codes (up to a natural necessary condition) converge to capacity at block lengths polynomial in the gap to capacity, while simultaneously achieving failure probabilities that are exponentially small in the block length (i.e., decoding fails with probability exp(-N^{Omega(1)}) for codes of length N). Previously this combination was known only for one specific family within the class of polar codes, whereas we establish this whenever the polar code exhibits a condition necessary for any polarization. Our results adapt and strengthen a local analysis of polar codes due to the authors with Nakkiran and Rudra [Proc. STOC 2018]. Their analysis related the time-local behavior of a martingale to its global convergence, and this allowed them to prove that the broad class of polar codes converge to capacity at polynomial block lengths. Their analysis easily adapts to show exponentially small failure probabilities, provided the associated martingale, the "Arikan martingale", exhibits a corresponding strong local effect. The main contribution of this work is a much stronger local analysis of the Arikan martingale. This leads to the general result claimed above. In addition to our general result, we also show, for the first time, polar codes that achieve failure probability exp(-N^{beta}) for any beta < 1 while converging to capacity at block length polynomial in the gap to capacity. Finally we also show that the "local" approach can be combined with any analysis of failure probability of an arbitrary polar code to get essentially the same failure probability while achieving block length polynomial in the gap to capacity.more » « less
-
Abstract Quantitative simulation of precipitation in current climate has been an ongoing challenge for global climate models. Despite serious biases in correctly simulating probabilities of extreme rainfall events, model simulations under global warming scenarios are routinely used to provide estimates of future changes in these probabilities. To minimize the impact of model biases, past literature tends to evaluate fractional (instead of absolute) changes in probabilities of precipitation extremes under the assumption that fractional changes would be more reliable. However, formal tests for the validity of this assumption have been lacking. Here we evaluate two measures that address properties important to the correct simulation of future fractional probability changes of precipitation extremes, and that can be assessed with current climate data. The first measure tests climate model performance in simulating the characteristic shape of the probability of occurrence of daily precipitation extremes and the second measure tests whether the key parameter governing the scaling of this shape is well reproduced across regions and seasons in current climate. Contrary to concerns regarding the reliability of global models for extreme precipitation assessment, our results show most models lying within the current range of observational uncertainty in these measures. Thus, most models in the Coupled Model Intercomparison Project Phase 6 ensemble pass two key tests in current climate that support the usefulness of fractional measures to evaluate future changes in the probability of precipitation extremes.more » « less
-
Abstract An occupancy model makes use of data that are structured as sets of repeated visits to each of many sites, in order to estimate the actual probability of occupancy (i.e. proportion of occupied sites) after correcting for imperfect detection using the information contained in the sets of repeated observations. We explore the conditions under which preexisting, volunteer-collected data from the citizen science project eBird can be used for fitting occupancy models. Because the majority of eBird’s data are not collected in the form of repeated observations at individual locations, we explore 2 ways in which the single-visit records could be used in occupancy models. First, we assess the potential for space-for-time substitution: aggregating single-visit records from different locations within a region into pseudo-repeat visits. On average, eBird’s observers did not make their observations at locations that were representative of the habitat in the surrounding area, which would lead to biased estimates of occupancy probabilities when using space-for-time substitution. Thus, the use of space-for-time substitution is not always appropriate. Second, we explored the utility of including data from single-visit records to supplement sets of repeated-visit data. In a simulation study we found that inclusion of single-visit records increased the precision of occupancy estimates, but only when detection probabilities are high. When detection probability was low, the addition of single-visit records exacerbated biases in estimates of occupancy probability. We conclude that subsets of data from eBird, and likely from similar projects, can be used for occupancy modeling either using space-for-time substitution or supplementing repeated-visit data with data from single-visit records. The appropriateness of either alternative will depend on the goals of a study and on the probabilities of detection and occupancy of the species of interest.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- The DOI is not currently available.
