How I solved a cool probability problem

First Steps

When I first read the problem, it screamed recursive probability function definition to me: When it’s player1’s turn they have a certain chance to win. If they don’t, player2 plays and if they also don’t win, it is player1’s turn again and we’re back to the same initial situation (or sort of, because the marker position player1 is playing from now has likely changed).

Solving p1(x) using discrete integral approximation

My idea came from numerical integral approximation, basically I would break the integration interval in blocks of size step, i.e. [x, x+step], and approximate the area of each block by the value of the function at it's beginning times the step size, i.e. f(x) * step. As step gets smaller, the approximation gets better.

code as text

Final Thoughts

After I was satisfied with my solution, I still had one question at the back of my mind: “Does this problem have an analytical closed-form solution?”. It reminded me of the goat problem which got popular since it just got solved in closed-form recently.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Luca Mattos Moller

Luca Mattos Moller

I'm a Computer Engineer interested in all sorts of stuff. Check out my personal website at lucamoller.com