  We study Kleinberg navigation (the search of a target in a d-dimensional
lattice, where each site is connected to one other random site at distance r,
with probability proportional to r^{-a}) by means of an exact master equation
for the process. We show that the asymptotic scaling behavior for the delivery
time T to a target at distance L scales as (ln L)^2 when a=d, and otherwise as
L^x, with x=(d-a)/(d+1-a) for a<d, x=a-d for d<a<d+1, and x=1 for a>d+1. These
values of x exceed the rigorous lower-bounds established by Kleinberg. We also
address the situation where there is a finite probability for the message to
get lost along its way and find short delivery times (conditioned upon arrival)
for a wide range of a's.
