I have a very different method for solving the problem. It’s by no means as simple or elegant as FractalFusion’s approach, but I think it’s pretty cool and seems to get the right answer. I don’t know anything about martingales or Markov chains, but I do know a bit about scattering theory in physics, and I was able to translate the problem into a scattering problem. Apologies in advance as this will be a bit long and probably not very straight-forward to follow.
Imagine a network of nodes and links that looks something like this
– 1 – 2 – 3 – 4 – 5 – 6 – 7 – 8 –
The numbers (nodes) represent how many coins you have, and the dashes, which connect different nodes are going to allow you to move left or right within the network. The physics problem I’m imagining might be something like a series of optical waveguides (lines) with connections (numbers) at which light can scatter (either forwards or backwards). The idea is that we’re going to inject light into the network from the left side and find the probability (or intensity) of the light that makes it to the end.
Three things can happen at each turn in the game and each one corresponds to a different type of scattering in the network:
lose a coin (p = 5/9) = scatter left in the network
gain a coin (p = 1/3) = scatter right one node
gain two coins (p = 1/9) = scatter right two nodes (more on how this works shortly)
To model the light in the network I’m going to suppose there are 4 different channels in each connection, a, b, c and d. Channel a is for all light that propagates to the left. Channels b, c and d will all be for right-propagating light but have different functions with respect to the game. Channel b will account for the case of when you win 1 coin (move right one node), channel c for when you win 2 coins (move right two nodes), and d will let me ‘skip ahead’ so that the light I initially inject into to the system can straight to go node 5 (since the game starts with 5 coins). The light in each link can thus be described by a vector of four components and scattering at the nodes can be described by setting up 4x4 scattering matrices (
https://en.wikipedia.org/wiki/S-matrix ) at the nodes. I need three different scattering matrices: one for before the entry point (node 5), one for at the entry point, and one for afterwards.
I'm going to use plain variables for channels on the left side of a node, and a prime for channels on the right side of the node. For nodes 1, 2, 3, 4 we have the matrix equation (forgive the formatting)
a 5/9 0 0 5/9 b
b' = 1/3 1 0 1/3 c
c' 1/9 0 0 1/9 d
d' 0 0 1 0 a'
The way this works is that light injected into the skip channel (d) stays in there and won't be scattered into any other channel. This channel acts independently of all the others. Light that comes into the node from channel c on the left all goes into channel b on the right. This ensures that all the light that scatters into channel c from the left effectively skips ahead one node (so it corresponds to winning 2 coins in the game). At the entry node (node 5) we have
a 5/9 0 5/9 5/9 b
b' = 1/3 1 1/3 1/3 c
c' 1/9 0 1/3 1/9 d
d' 0 0 0 0 a'
which is more or less the same matrix, but now light coming from the skip channel gets evenly distributed among all the other options, which means light is now entering into the network at this point. For nodes to the right of the entry point the 'skip' channel becomes useless and we just have
a 5/9 0 0 5/9 b
b' = 1/3 1 0 1/3 c
c' 1/9 0 0 1/9 d
d' 0 0 0 0 a'
There may well be a simpler way to set everything up, but this approach seemed fairly intuitive to me.
Now we need to get the scattering matrix for the entire network so we can relate the channels at the far left to the far right. Then we can just inject light with intensity 1 into the skip channel at the left end and see how much comes out at the right end. One way to do this is to convert each 4x4 scattering matrix into a 4x4 transfer matrix (see for example
http://assets.press.princeton.edu/chapters/s8695.pdf ). You can work these out by essentially finding the 'partial inverses' of the scattering matrices (
https://en.wikipedia.org/wiki/Partial_inverse_of_a_matrix ), although you need to be a bit careful with the matrix block structure. Once you have the transfer matrices you can just multiply them together to get the transfer matrix for the whole system, which can then be converted back into a scattering matrix. If I use M to denote transfer matrices, the transfer matrix for the whole system is just
M_right ^ 3 * M_entry * M_left ^ 4
Convert this back into a scattering matrix S and finally compute S * [0, 0, 1, 0]. My little Python program outputs
[a, b', c', d'] = [0.45451636, 0.45483641, 0.09064723, 0]
Finally, since the network stopped at node 8, we need to remember that I win if I'm in either channel b or c. b is light that entered 9 directly from node 8 (you won 1 coin when you had 8) and c is light heading towards an imaginary node 10 from node 8 (you won 2 coins from node 8). So we just need to add
0.45483641 + 0.09064723 = 0.5454836405947694
which seems to be at least close to the right answer.
what point C on the central horizontal axis in the figure is such that AC + CB is minimal? This is solved by reflecting the triangle through the axis and constructing the straight line from A to B' (purple line in the diagram). In this case, the angles to A and B from C are equal, which means
(4-x)/5 = (2+x)/3.
Solving this gives x = 1/4, which is the same as what Dacicus found.
edit: just realized my solid/dash styling is inconsistent, but I can't be bothered changing it now. Sorry!
