The best strategy for Bob is pretty simple because he knows exactly what he needs to win (the same cannot be said for Alice). Thus, he can continue to ask for random numbers until he either wins or loses. This is the best and only intuitive strategy for Bob.
The best strategy for Alice is to repeatedly ask for a random number until she has exceeded some threshold, $k$ where $0≤k≤1$. The actual value of $k$ can vary but the important part is that if her current sum is less than $k$, she asks for a new number and otherwise she stays with her current sum. I will solve for the optimal value of $k$ later in this post.
If you get bored of playing the game over and over, you may type in your value for k (the threshold) and run 10000 simulations to see how well that strategy will pay off in the long run.
Now that I've defined the game and each of the strategies, we are ready to start tackling the fun part - the Math! Warning: The rest of the blog post is going to contain some fairly advanced mathematics.
Let's start off with mathematical definitions for Bob's winning percentage based on the strategy we defined earlier. Let \( B_y (x) \) be the probability that Bob wins with current value \( x \) (given that Alice stopped at \( y \)). Thus, it follows that \( 0 \leq x,y \leq 1 \) (if \( x > 1 \), then \( B_y (x) = 0 \)). Further,
$$
B_y (x) =
\left\{
\begin{array}{ll}
1 & x > y\\
\int_{t=x}^{1} B_y(t) dt & otherwise
\end{array}
\right.
$$ Notice that \( B_y(x) \) is defined recursively, in fact it's defined as a "recurrence integral". For the first condition, if \( x > y \), then Bob has already won, so his probability of beating Alice is \( 1 \). In the second case, \( B_y(x) \) is defined in terms of itself by averaging (over the continuous range of possibilities) the probability of winning for each possible random number that we are given (we stop when our sum is \( 1 \) because after that, the probability of winning is \( 0 \). We can simplify this piecewise definition into a single definition by breaking up the integral into 2 parts.
$$
B_y (x) = (1 - y) + \int_{t=x}^{y} B_y(t) dt
$$ Here, the \( (1-y) \) corresponds to the probability of getting a random number that puts Bob in the range \( (y, 1] \) and the integral represents the average probability of winning ranged over all sums in the range \( [x, y] \). The rest of the possibilities (\( (1, 1+x] \)) are not included because the probability of winning in that range is just \( 0 \).
So how do we attack such a problem? Well, we can utilize the second fundamental theorem of calculus to reduce this problem to a differential equation which we can then solve.
$$
B_y (x) = (1 - y) + \int_{t=x}^{y} B_y(t) dt
$$ In order to apply the second fundamental theorem of calculus, x has to be the upper index of the integral. We can switch the indices by negating the integral as follows:
$$
B_y (x) = (1 - y) - \int_{t=y}^{x} B_y(t) dt
$$ Now we can differentiate both sides with respect to \( x \) and apply the second fundamental theorem of calculus on the RHS.
$$
B_y ' (x) = - B_y (x)
$$ This is a simple differential equation to solve and you may even be able to see what the general solution is without any knowledge of differential equations. The general solution to this differential equation is:
$$
B_y (x) = c e^{-x}
$$ We can use the initial condition to solve for c
$$
B_y(y) = (1 - y) - \int_{t=y}^{y} B_y(t) dt = 1 - y \\
B_y (y) = c e^{-y} = 1 - y \\
c = e^y (1 - y) \\
B_y (x) = c e^{-x} = e^{-x} e^y (1 - y) $$ Thus, in it's most simplified form, the probability that Bob wins, \( B_y (x) \) is given by
$$
B_y (x) = e^{y-x} (1 - y) \\
B_y (0) = e^y (1 - y)
$$ I've now established the probability of Bob winning given the value \( y \) which he needs to beat.
Alice can use this information to make her decisions because she now knows the probability that Bob will win if she stops, and she knows the probability that her guess will bring her sum over \( 1 \), so she can attempt to balance these probabilities appropriately to choose the optimal threshold value \( k \).
Let's define a similar function for Alice. Let \( A(y) \) be the probability that Alice wins with current value y. It follows that \( 0 \leq y \leq 1 \) (if \( y > 1 \), \( A(y) = 0 \)).
$$
A(y) = max \Big[ 1 - B_y (0), \int_{t=x}^1 A(t) dt \Big] dt
$$ The first term corresponds to the case where Alice stops asking for random random numbers. The probability that Alice wins when she stops is equal to the probability that Bob loses, or \( 1 - B_y (0) \). The second term corresponds with the case that Alice wants to keep asking for random numbers, and the integral represents the probability of Alice winning averaged over all guesses in the range \( t \in [y, 1] \). For values in the range \( t \in (1, 1+y] \), \( A(t) = 0 \) so these are omitted. These are the two choices Alice faces, and the one that returns a higher probability of eventually winning is the one she should pick.
Based on the strategy we defined for Alice, we know she will stop if \( y > k \) and she will ask for another number if \( y \leq k \), where k is the threshold value. Thus, we can use this to define a new function, \( A_k (y) \) which is going to break up the components of \( A(y) \).
$$
A_k (y) =
\left\{
\begin{array}{ll}
1 - B_y(0) & y > k\\
\int_{t=y}^{k} A_k(t) dt + \int_{t=k}^{1} (1-B_t(0)) dt & otherwise
\end{array}
\right.
$$ Now we have another recurrence integral to solve and we can use the same method to determine what \( A_k (y) \) is in closed form. Using the result from earlier, we can evaluate the second integral up front.
$$
A_k (y) = \int_{t=y}^{k} A_k(t) dt + \int_{t=k}^{1} (1-B_t(0)) dt \\
A_k (y) = \int_{t=y}^{k} A_k(t) dt + \int_{t=k}^{1} (1- e^t (1 - t)) dt
$$ Using integration by parts, we can evaluate the second integral:
$$
A_k (y) = \int_{t=y}^{k} A_k(t) dt + (2-k) e^k + 1 - e - k
$$ Using the same technique from earlier, we can differentiate both sides with respect to x and solve a differential equation for \( A_k (y) \).
$$
A_k' (y) = -A_k(y) \rightarrow A_k (y) = c e^{-y} \\
A_k (k) = c e^{-k} = (2-k) e^k + 1 - e - k \\
c = (2-k) e^{2k} + e^k (1 - e - k)
$$ Now we have \( A_k (y) \) in closed form!
$$
A_k (y) = [(2-k) e^{2k} + e^k (1 - e - k)] e^{-y}
$$ We want to choose \( k \) in order to maximize \( A_k (y) \) (or alternatively \( c \)). We can maximize this function by taking the derivative and finding the critical point, but unfortunately this process requires us to solve a difficult nonlinear equation. The exact function that we would need to solve is
$$
k = \frac{3 e^k - e}{1 + 2 e^k}
$$ You can try to work this out for yourself if you'd like, but I opted to use fixed point iteration to numerically solve for $k$. The optimal value for $k$ and corresponding value for \( A_k \) are
$$
k \approx 0.57056 \\
A_k (0) \approx 0.424959
$$
Here is a plot of \( k \) vs. \( A_k \) (fixing \( y = 0 \)).
Conclusion
Based on the analytical results, we know this game is not fair. In fact, Bob has a
\( 1 - 0.424959 = 0.575041 \) probability of winning as opposed to Alice's \( 0.424959 \). These probabilities make sense because Bob has more information on his turn, so he doesn't have to decide when to stop asking for more numbers. The actual threshold value for Alice, \( k = 0.57056 \) surprised me a little bit. I thought it would turn out to be higher than that.
Unfortunately for Alice, even if she uses perfect strategy, she is still at a disadvantage in this game. Her disadvantage would be even worse if she wasn't aware of her optimal strategy. In fact, if she instead chose \( k = 0.8 \) as her threshold value, her probability of winning this game decreases substantially to \( p = 0.340896 \)!
I enjoyed this problem very much because it required creativity and knowledge from some of my favorite fields of mathematics including Game Theory, Probability Theory, and Differential Equations.
Comments
Post a Comment