# Optimal strategy of tag on ring if two cannot see each other

I want to know the optimal strategy of tag on a ring if two cannot see each other. From intuition, the child should escape from the demon and the demon should follow the shortest path to the child. However, if the child move in the deterministic way, the demon can easily find him. So the optimal strategy should follow some probabilistic way. But I have no idea...

Rule:
＊At first, a demon and a child is on $$u_{0}$$ and $$v_{0}$$.
＊The perimeter of the ring is $$N$$.
＊At $$n$$ seconds later, the demon and the child will move from $$u_{n},v_{n}$$ to $$u_{n+1} \bmod N,v_{n+1} \bmod N$$ s.t. $$|u_n-u_{n+1}|=1$$ and $$v_{n}-v_{n+1}|=1$$ one by one. (The child move fast and then the demon will move)
＊The demon wants to go to the place of the child.
＊The child wants to escape from the demon.
＊The demon and child know both $$u_0$$ and $$v_0$$. However they cannot see each other until they will meet each other. In other words, the child don't know $$u_1,u_2,\ldots$$ and the demon don't know $$v_1,v_2,\ldots$$

• Comparing this to meeting on a sphere makes me wonder whether you can come up with a definition of optimality that doesn't already assume a certain strategy for one of the players, or at least an assumed probability distribution of strategies. Fleshing out the optimality concept might add value to this question. – MvG Dec 23 '19 at 9:07
• The optimal strategy for the child is to maximize the expected time the child will survive. The optimal strategy for the demon is to minimize the expected time the child will survive. – ueir Dec 23 '19 at 9:15
• To compute an expected time, you need to sum (or integrate) over the actual time for a given path of the opponent times the probability of that path. The latter requires you to assume a strategy distribution of some kind. Different assumptions there lead to different answers, and assuming an "optimal" strategy on the part of the opponent makes the whole definition of optimality self-referential and thus a lot harder to make exact. – MvG Dec 23 '19 at 9:49

The child should go to the point across from where the demon started and wait there as long as it’s safe. That ensures that she survives $$\frac N2$$ steps. (I'm ignoring rounding complications.) Once the demon could arrive at that point, it has a $$\frac12$$ chance to catch the child; there's nothing to be done about that. (It can flip a coin to sweep either half of the circle, and the child can't avoid being caught in the swept half with probability $$\frac12$$.) So the best the child can do now is to survive for as long as possible with probability $$\frac12$$. To do that, she can flip a coin and run to the opposite point (where the demon started). That ensures she survives for the next $$\frac N2$$ steps with probability at least $$\frac12$$. Now the demon has another $$\frac12$$ chance of catching the child, which can't be avoided, and so on.
$$\frac N2\sum_{k=0}^\infty\left(\frac12\right)^k=N\;.$$