Tug of War

 Here is an interesting problem that I came across on this site:

  

The Robot Weightlifting World Championship was such a huge success that the organisers have hired you to help design its sequel: a Robot Tug-of-War Competition!

In each one-on-one matchup, two robots are tied together with a rope. The centre of the rope has a marker that begins above position 0 on the ground. The robots then alternate pulling on the rope. The first robot pulls in the positive direction towards 1; the second robot pulls in the negative direction towards -1. Each pull moves the marker a uniformly random draw from [0, 1] towards the pulling robot. If the marker first leaves the interval [‑½, ½] past ½, the first robot wins. If instead it first leaves the interval past -½, the second robot wins.

However, the organisers quickly noticed that the robot going second is at a disadvantage. They want to handicap the first robot by changing the initial position of the marker on the rope to be at some negative real number. Your job is to compute the position of the marker that makes each matchup a 50–50 competition between the robots. Find this position to seven significant digits-the integrity of the Robot Tug-of-War Competition hangs in the balance!

I managed to come up with the following program after experimentation with different starting values.

xxxxxxxxxx

 

1

import random

2

count1,count2=0,0

3

for i in [1..1000]:

4

    d1=-.2850000

5

    d2=d1

6

    while (d1<=0.5 and d1>=-0.5) and (d2<=0.5 and d2>=-0.5):

7

        d1=d1+random.random()

8

        if d1<=0.5 and d1>=-0.5:

9

            d2=d1-random.random()

10

            d1=d2

11

    if d1>0.5:

12

        count1+=1

13

    else:

14

        count2+=1

15

print("First Robot won",count1,"times and Second Robot won",count2,"times")

Language: Sage Gap GP HTML Macaulay2 Maxima Octave Python R Singular

---

Messages

Figure 1: source

I found that a starting value of about -0.285 produced a 50-50 result on average, which is what the person who posed the problem found. See Figure 1. I don't know why an accuracy of seven significant figures was required and I certainly wasn't going to strive for that level of accuracy. In any case, my result was certainly close enough.

Generally the tug-of-war doesn't last long, only one or two randomisations. Figure 2 shows the results for an unusually lengthy match that ended in a win for Robot 1:

Figure 2: permalink

So far this post has been more about programming than mathematics but I was interested in how a number like 0.285 emerges from a problem like this. My result of -0.285 was purely empirical. It turns out that the solution is  the result of evaluating the following expression: $$\arcsin \left (\frac{\sin(0.5)+\frac{\pi}{4}}{2} \right )-\frac{\pi}{4}$$ Now that is interesting and the derivation of this result is explained on this site and reproduced below (where p stands for probability):

In order to find the starting position of the tug-of-war to make a fair fight, we define the function $f$ on [-0.5, 0.5] as $$f(x) = \text{ p(Player 1 wins at a starting position of } x)$$ The symmetry of the game implies  $$\begin{align} f(x) &= \text{ p(Player 1 wins on first move) } + \int_x^{½} \! \text{p(Player 2 wins at position }(-y)) \text{ d}y \\ &= (½ + x) + \int_x^{½}(1 - f(-y) ) \text{ d}y \end{align}$$ Differentiating and applying the fundamental theorem of calculus, we get:

$f’(x) = 1 - (1 - f(-x)) = f(-x)$

Differentiating again and employing the chain rule, and then substituting the equation above, we get:

$f’’(x) = f’(-x) \times (-1) = -f’(-x)= -f(x)$ 

 

The general solution to this differential equation is 

 

$f(x) = A \sin(x) + B \cos(x)$

We need two boundary conditions to determine $f$ exactly. First, it’s clear we must have $f(½) = 1$. Second, from the above formula, $f’(0) = f(0)$. Therefore
$$\begin{align} A \sin(½) + B \cos(½) &= 1 \text{ and}\\ A \cos(0)- B \sin(0) &= A \sin(0) + B \cos(0) \end{align}$$ The second equation implies $A = B$, and the first equation then gives: $$\begin{align}A &= B\\ &= \frac{ 1} {\sin(½) + \cos(½)} \text{ and so}\\ f(x) &= \frac {\sin(x) + \cos(x)}{\sin(½) + \cos(½)} \end{align}$$ Therefore the answer is the solution to: $$\frac{\sin(x) + \cos(x)}{\sin(½) + \cos(½)} = ½ \text{ on }[-½,0]$$ A calculator can give this to the desired accuracy, -0.2850001…, or by using $$\sin(x) + \cos(x) = \sqrt{2}· \sin(x + \pi/4)$$ we can exactly solve that the answer is $$\arcsin \left (\frac{\sin(0.5+\frac{\pi}{4}}{2} \right )-\frac{\pi}{4}$$ I don't fully understand this explanation but I'm exhausted from fine tuning the LaTeX so I'll return to it later.