  The mean completion time of a stochastic process may be rendered finite and
minimised by a judiciously chosen restart protocol, which may either be
stochastic or deterministic. Here we study analytically an arbitrary stochastic
search subject to an arbitrary restart protocol, each characterised by a
distribution of waiting times. By a direct enumeration of paths we construct
the joint distribution of completion time and restart number, in a form
amenable to analytical evaluation or quadrature; thereby we optimise the search
over both time and potentially costly restart events. Analysing the effect of a
punctual, i.e. almost deterministic, restart, we demonstrate that the optimal
completion time always increases proportionately with the variance of the
restart distribution; the constant of proportionality depends only on the
search process. We go on to establish simple bounds on the optimal restart
time. Our results are relevant to the analysis and rational design of efficient
and optimal restart protocols.
