### Technical Report No. 111 - Abstract

**Sven Schuierer**

*Lower Bounds For Randomized Searching on m Rays*

We consider the problem of on-line searching on *m* rays.
A point
robot is assumed to stand at the origin of *m* concurrent rays
one of which contains a goal *g* that the point robot has to
reach. Neither the ray containing *g* nor the distance to
*g* are known to the robot. The only way the robot can detect
*g* is by reaching its location. We use the *competitive
ratio* to measure the performance of a strategy.
We present a simple proof of a tight lower bound for randomized
strategies to search on *m* rays. In particular, we show in our
proof that there is an optimal randomized strategy that visits the rays
in cyclic order. We also obtain a bound on the convergence rate to the
optimal competitive ratio for a fixed *m* if the goal has a
distance of at most *D* to the origin.
Finally, we show that the optimal competitive ratio is asymptotically
given by 1 + 2*1.544*m* as *m* goes to infinity.

Report No. 111 (PostScript)