Solution to "Feedback Strategies," DDJ, November 2005
- The probability of winning under FeedYes is about 0.89 when Pgood is 0.9. It cannot be better than 0.9 because if one is on the second from top row and is adjacent to the winning square, there is some chance of losing. The strategy for FeedYes consists of trying to reduce the horizontal distance to the goal to zero (or to one on rows that are an odd distance away). Calculating the probability involves the following key recurrence ideas: If you are n steps (n>0) away from the top row and 0 distance away, then your probability of hitting is the same as the probability of hitting if you are n-1 steps away and one away from column 5. Otherwise, with probability Pgood you will be one column closer to your goal and with probability 1-Pgood you will be one farther from the goal both with n-1 steps.
- Under the FeedNo strategy, the probability is about 0.55. To compute the probability for FeedNo, assume a strategy that will take four aims to the right and three aims to the left since this gives the best likelihood of hitting the destination. Given this, there are four ways to win: All seven aims are true; three of the right aims are true and two of the left are; two of the right are true and one of the left; and one right and zero left. So, the feedback dividend is about 1.6.
- The value of Pgood, for which the dividend ratio is highest, is not 0.75 as one might think but something around 0.772. For that value, the dividend ratio reaches 1.99. I don't believe it ever reaches 2.
- In both the FeedNo and FeedYes cases, the analysis combines short trips: One wants to go from row 1 column 4 to row 3 column 4 in the first two moves then to row 5 column 4 in the second two moves, then row 7 column 4, and finally row 8 column 5. For FeedNo, this gives a formula like the following:
((((Pgood2)+(1-Pgood)2))3)×Pgood
- For FeedYes, this gives a formula that is Pgood4. This gives a maximum feedback dividend of 1.75 when Pgood is 0.71.
Alan Dragoo helped with these solutions.
DDJ
