To save the casual reader from Wall of Math, details are after the jump.
Now, to build a Markov Chain for a problem the transition probabilities can't be conditional on anything but the current state, so there's not a straightforward way to combine these different methods into one bid process. An idea I had, though, was to build out 7 states for every number of masks below 20. Then I'd transition from the "0 mask, do the daily dungeon" state to either the "0 mask, save a town" state or the "1 mask, save a town" state. From saving a town I'd go to "0 mask, 1st trick or treat" state or "1 mask, 1st trick or treat" state. Repeat this while progressing from a 1st trick state to a 2nd trick state, and so on until the 5th trick state would go back to one of the daily dungeon states.
This would result in a 141x141 matrix which scares me as far as getting the online tool to process it. (Though I can actually cull 6 states from the start if the daily dungeon is a 100% drop of a mask.) I don't think it will work this time but maybe if I start small I can find a pattern again. Let's find out by building the matrix assuming we started with 19 masks...
P | = | 0 | .95 | 0 | 0 | 0 | 0 | 0 | .05 |
0 | 0 | .993 | 0 | 0 | 0 | 0 | .007 | ||
0 | 0 | 0 | .992 | 0 | 0 | 0 | .008 | ||
0 | 0 | 0 | 0 | .992 | 0 | 0 | .008 | ||
0 | 0 | 0 | 0 | 0 | .992 | 0 | .008 | ||
0 | 0 | 0 | 0 | 0 | 0 | .992 | .008 | ||
.992 | 0 | 0 | 0 | 0 | 0 | 0 | .008 | ||
0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
Plugging this into the website I found gives an E[K] value of 70.2871 which is a substantial improvement over the 125 from just trick or treating. Assuming 5 trick or treats per day (because we have 5 trick or treat states per daily states) we were looking at 25 days to get this done under the old plan and just 11 days under the new one.
How about if we started with 18 masks?
P | = | 0 | .9 | 0 | 0 | 0 | 0 | 0 | 0 | .1 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | .986 | 0 | 0 | 0 | 0 | 0 | 0 | .014 | 0 | 0 | 0 | 0 | 0 | ||
0 | 0 | 0 | .984 | 0 | 0 | 0 | 0 | 0 | 0 | .016 | 0 | 0 | 0 | 0 | ||
0 | 0 | 0 | 0 | .984 | 0 | 0 | 0 | 0 | 0 | 0 | .016 | 0 | 0 | 0 | ||
0 | 0 | 0 | 0 | 0 | .984 | 0 | 0 | 0 | 0 | 0 | 0 | .016 | 0 | 0 | ||
0 | 0 | 0 | 0 | 0 | 0 | .984 | 0 | 0 | 0 | 0 | 0 | 0 | .016 | 0 | ||
.984 | 0 | 0 | 0 | 0 | 0 | 0 | .016 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ||
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | .95 | 0 | 0 | 0 | 0 | 0 | .05 | ||
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | .993 | 0 | 0 | 0 | 0 | .007 | ||
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | .992 | 0 | 0 | 0 | .008 | ||
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | .992 | 0 | 0 | .008 | ||
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | .992 | 0 | .008 | ||
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | .992 | .008 | ||
0 | 0 | 0 | 0 | 0 | 0 | 0 | .992 | 0 | 0 | 0 | 0 | 0 | 0 | .008 | ||
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
E[K] = 106.4. Unfortunately there was no pattern which happened because with 19 masks I assumed we always started on the daily dungeon but with 18 masks we start with the next action in line after the one which gave us our 19th mask. This could possibly be fixed by altering my x0 row vector but I'm not sure I can find the right one without going all the way back to the 0 mask state anyway. Even more unfortunately the web tool I'm using had a hard time processing this matrix and I find it very hard to believe it could go all the way up to a 135x135 matrix. And I'm certainly not brute forcing it, especially since it isn't upper triangular like the ones yesterday were.
With 19 I was 70 compared to 125. With 18 I'm 106 compared to 187. Those two ratios are close but sadly not exact. If they were then I'd estimate 253 tries with the new system which is 36 days compared to 64 days of just trick or treating 5 times a day. A mere 3 years of heavy play as opposed to 5. Nice buff, Blizzard!
Since we had a computer refresh at work, I don't have the spreadsheet I used to generate my original results, and to be honest I can't quite recall how I got them. How I got the expected value for number of masks needed is pretty obvious, but how I arrived at the chances of completing every year is less so.
ReplyDeleteObviously in your first example of using Markov Chains in the previous post is a case where we could use other methods much more easily. I get the average number of masks needed by the good old 1/(1-P) method. Similarly, if we wanted to figure out the precise odds of not having a mask in the first N masks we could come up with a gigantic formula. Then we could have another gigantic formula for how likely we are to get each number of masks for a given number of days of trying, and we could combine those two to get a precise value.
I guess the question is at what point the Markov Chain becomes a simpler solution. 135 x 135 matrices are pretty outrageously complicated, but if you don't have a program that will solve them for you obviously you could right your own in VB. At the same time, I could write my own program to go through all the combinations of things I was talking about above. I have a strong feeling that the Markov chains overtake the method I was thinking of in efficiency before we get to the solutions we want for this particular 20 mask problem, but I can't say I really know.