Optimizing the success of random searches¶
Citation
- Viswanathan, G. M., Buldyrev, S. V., Havlin, S., da Luz, M. G. E., Raposo, E. P. & Stanley, H. E. (1999). Optimizing the success of random searches. Nature.
- DOI
Relevance to Hifuku¶
Hifuku's levy_jump_move relocates a tree by a heavy-tailed jump. Its length
is drawn from the Lévy flight-length distribution
\( P(l) \sim l^{-\mu} \) of Viswanathan et al. (1999), who show that a searcher
looking for sparse targets whose locations are unknown maximizes its search
efficiency near \( \mu = 2 \). Hifuku uses \( \mu = 2 \) and applies
\( \mathrm{round}(l) \) subtree-prune-and-regraft moves for a drawn length
\( l \). Heavy tails give many short relocations and a few long ones, which
covers a neighborhood thoroughly while still reaching distant regions.
Reasoning step: the flight-length sampler¶
Hifuku draws \( l \) from \( P(l) \sim l^{-\mu} \) on \( [1, \infty) \) by inverse transform. Normalizing the density gives \( p(l) = (\mu - 1)\, l^{-\mu} \), with cumulative distribution \( F(l) = 1 - l^{-(\mu - 1)} \). Inverting \( U = F(l) \) with \( V = 1 - U \), which is itself uniform, gives the sampler
The sampled length then has survival \( P(L > x) = x^{-(\mu - 1)} \) and density
tail \( x^{-\mu} \), recovering the target exponent. The normalization, the
cumulative distribution, the inversion, the tail exponent, and a numeric check
at \( \mu = 2 \) are in
viswanathan1999levy-flight-length.py.