First Passage under Restart with Branching

First passage under restart with branching is proposed as a generalization of first passage under restart. Strong motivation to study this generalization comes from the observation that restart with branching can expedite the completion of processes that cannot be expedited with simple restart; yet a sharp and quantitative formulation of this statement is still lacking. We develop a comprehensive theory of first passage under restart with branching. This reveals that two widely applied measures of statistical dispersion—the coefficient of variation and the Gini index—come together to determine how restart with branching affects the mean completion time of an arbitrary stochastic process. The universality of this result is demonstrated and its connection to extreme value theory is also pointed out and explored.

Figure 1

An illustration of diffusion under restart with branching. When restart occurs, particles are brought back to the origin and each particle is branched into two identical copies of itself.

Figure 2

The effect the introduction of restart with branching has on the mean FPT (to a stationary target) of a particle undergoing diffusion with drift. Results are shown for different values of the Péclet number, $\mathrm{Pe}=LV/2D$, and branching index $m$.

Figure 3

An illustration of first passage under restart with branching ($m=2$). Restart and branching takes place at time $t_1$ and thereafter at time $t_2$. Completion takes place at time $t_f$.

Figure 4

Mean FPT under restart with branching vs restart rate for different FPT processes: (i) cover time of a random walker [36]; (ii) diffusion with drift [34]; and (iii) an infectious cell’s growth model [37]. In all three cases, the branching index was set to $m=2$, and time was measured in units of the mean FPT in the absence of restart and branching. Dashed lines are theoretical curves computed based on Eq. (3) and markers come from Monte Carlo simulations [35].

Figure 5

Graphical exploration of the criterion from Eq. (5) when applied to the Weibull distribution. Left. ${\mathrm{CV}}^2+2{GI}_m$ is plotted vs the shape parameter $\beta$ for different values of the branching index $m$. Right. The CV is plotted vs $G{I}_m$ for different values of the branching index $m$. In both panels, the ${\mathrm{CV}}^2+2{GI}_m=1$ line separates the two different behavioral phases that are predicted by Eq. (5).