Robot tug-of-war (w/ Jane Street's August 2021 challenge)
The fourth post in my series of Jane Street puzzles; previous solves can be found here, here and here.
The Robot Weightlifting World Championship was such a huge success that the organizers 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 center 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 organizers 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!
Simulation
Let’s make a simulation to get an initial overview of the problem. We denote \(x\) as the starting position of the robot, and we have to find \(x \in \left(-\frac 1 2, \frac 1 2 \right)\) such that
\[p(x) = \mathbb{P}(\text{robot 1 wins} \mid \text{starting position is } x) = 0.5\]
We can read from the graph that the solution is approximately \(0.285\). Unfortunately, brute force will not be quick enough to find the solution to seven decimal places. We also cannot use the binary search technique I used last time, because we are not dealing with a kink in a graph. We will have to find the actual closed-form formula of the graph.
Analytic description
The clue lies in the symmetry between robot 1 and robot 2. Let’s try to reason from the perspective of robot 2 after robot 1 has made his move. Suppose that robot 1 moved from \(x\) to \(x + t\), \(x + t \in \left(0, \frac 1 2 \right]\). Now it is the turn of robot 2, and from symmetry we can deduce that the probability of robot 2 winning in this case is the same as the probability of robot 1 winning after starting from \(-x-t\).
Let’s combine this with the law of total probability:
\[\begin{align*} p(x) &= \mathbb{P}(\text{robot 1 wins} \mid \text{starting position is } x) \\ p(x) &= \int_0^1 \mathbb{P}(\text{robot 1 wins} \mid \text{his first pull is } t) dt \end{align*}\]We can split this integral into two different cases:
\[\begin{cases} \mathbb{P}(\text{robot 1 wins} \mid \text{position is } x+t) = 1, &x+t \geq \frac 1 2 \\ \mathbb{P}(\text{robot 1 wins} \mid \text{position is } x+t) = p(-x-t), &x+t < \frac 1 2 \end{cases}\]Therefore we have
\[\begin{align*} p(x) &= \int_0^{\frac 1 2 - x} \mathbb{P}(\text{robot 1 wins} \mid \text{his first pull is } t) dt + \int_{\frac 1 2 - x}^1 dt \\ &= \int_0^{\frac 1 2 - x} 1 - p(-x-t) dt + \frac 1 2 + x \\ &= 1 - \int_0^{\frac 1 2 - x} p(-x-t) dt \\ \end{align*}\]Apply a substitution with \(u = - x - t\):
\[\begin{align*} p(x) &= 1 + \int_{-x}^{-\frac 1 2} p(u) du \\ &= 1 - \int_{-\frac 1 2}^{-x} p(u) du \end{align*}\]Let’s differentiate both sides, and apply the fundamental theorem of calculus:
\[\frac {dp(x)} {dx} = \frac d {dx} \left[ 1 + \int_{-\frac 1 2}^{-x} {p(u)}du \right]\] \[p'(x) = p(-x)\]We can check this differential equation with the approximate simulation we’ve made before. You can see our tangent line aligns nicely.
To solve this differential equation analytically, let’s consider the Taylor series of \(p(x)\):
\[p(x) = p(0) + \frac {p'(0)} {1!} \cdot x + \frac {p''(0)} {2!} \cdot x^2 + \ldots \\ \implies \begin{cases} p(-x) &= p(0) &- \frac {p'(0)} {1!} \cdot x &+ \frac {p''(0)} {2!} \cdot x^2 &- \ldots \\ p'(x) &= p'(0) &+ \frac {p''(0)} {1!} \cdot x &+ \frac {p'''(0)} {2!} \cdot x^2 &+ \ldots \\ \end{cases}\]Because this holds for all \(x \in \left(\frac 1 2, \frac 1 2 \right)\), this implies that all \(i\)‘th derivatives of these two power series must be equal on this interval. Therefore, the coefficients of these two power series must be equal:
\[\begin{cases} p'(0) &= p(0), \\ p''(0) &= -p'(0), \\ p'''(0) &= p''(0), \\ p''''(0) &= -p'''(0), \\ \ldots \end{cases}\]Let \(p(0) = a\), and let’s denote the \(n^{th}\) derivative of \(p(x)\) as \(p^{(n)}(x)\) for simplicity:
\[\begin{cases} p^{(0)}(0) & &= a, \\ p^{(1)}(0) = &p^{(0)}(0) &= a, \\ p^{(2)}(0) = - &p^{(1)}(0) &= -a, \\ p^{(3)}(0) = &p^{(2)}(0) &= -a, \\ p^{(4)}(0) = - &p^{(3)}(0) &= a, \\ p^{(5)}(0) = &p^{(4)}(0) &= a, \\ \ldots \end{cases}\]Do you notice the pattern? Alternating double positives and double negatives, repeating indefinitely. We can use this to find the final Taylor expansion for \(p(x)\):
\[\begin{align*} p(x) &= &a &+ \frac a {1!} \cdot x &- \frac a {2!} \cdot x^2 &- \frac a {3!} \cdot x^3 &+ \ldots \\ &= &a & &- \frac a {2!} \cdot x^2 & &+ \ldots \\ & & &+ \frac a {1!} \cdot x & &- \frac a {3!} \cdot x^3 &+ \ldots \end{align*}\]These are two Taylor series you might recognize! The top one resembles \(a \cdot \sin(x)\), and the bottom one \(a \cdot \cos(x)\). Therefore, we conclude that
\[p(x) = a(\sin(x) + \cos(x))\]Solving for \(a\) is simple when you consider that \(p \left(\frac 1 2 \right) = 1\). When robot 1 starts at \(\frac 1 2\), it is certain it will win:
\[\begin{align*} a &= \frac 1 {\sin \left(\frac 1 2 \right) + \cos \left(\frac 1 2 \right)} \\ \implies p(x) &= \frac {\sin(x) + \cos(x)} {\sin \left(\frac 1 2 \right) + \cos \left(\frac 1 2 \right)} \end{align*}\]Now we can solve for \(x\) and find the solution to our original problem.
\[\begin{align*} & & p(x) &= 0.5 \\ &\iff & \frac {\sin(x) + \cos(x)} {\sin \left(\frac 1 2 \right) + \cos \left(\frac 1 2 \right)} &= 0.5 \\ &\iff & x &= \frac \pi 4 - \cos^{-1}\left(\frac {\sin\left(\frac 1 2\right) + \cos\left(\frac 1 2\right)} {2 \sqrt 2}\right) \\ &\implies & x &\approx -0.2850001 \end{align*}\]So if robot 1 starts at \(-0.2850001\), both robots will have a \(50\%\) chance of winning the tug of war, which is the answer to our problem.
