I was puzzled by a question my colleague asked me, and now seeking your help.
Suppose you and your friend* end up on a big sphere. There are no visual cues on where on the sphere you both are, and the sphere is way bigger than you two. There are no means of communication. You can determine your relative position and direction by navigating the stars**. You can move anywhere, and your friend too.
Upon inspecting the sphere, you see it is rock-solid, so you cannot create markings. To protect the environment, you are not allowed to leave other stuff, like a blood trace or breadcrumbs.
You have been put on the sphere without being able to communicate a plan.
How would you be able to find each other (come within a certain distance $\epsilon$?) What would be the optimal strategy to move?
*Since you are here, you must be a rational person. For this puzzle we assume your friend is rational too..Which makes it odd that you end up on that sphere anyway
**While you can determine your position relatively, you are on a sphere in a galaxy so far away that you cannot determine absolute ‘north’, ‘south’ etc. by the stars.
Move at random.
Any deterministic strategy you choose has a chance that your partner will choose the exactly opposite strategy, so you end up moving along more or less antipodal paths and never meet. So deterministic strategies have to be avoided.
You might make some adjustments to your random strategy. For example, you could prefer to walk longer distances in a straight line as opposed to choosing a completely new direction after every centimeter of movement. Depending on what your partner does, some of that might improve things. But to accurately judge whether it does, you’d need some probabilistic model of what plan your partner is likely to choose, and getting that right would pretty much amount to a pre-agreed plan. So you can’t even know the probability distribution of plans for your partner, hence you can’t quantitatively compare strategies against one another.