Markov Chains 2

Yesterday I investigated using Markov Chains to work out how long the average person would take to get the A Mask for All Occasions achievement in World of Warcraft. However, in order to get the problem into a simple Markov Chain format I had to assume the player was only getting masks by Trick or Treating which is not the only way of getting them. On top of the 16% chance you have of getting a mask by trick or treating you also have a 14% chance of getting one by defending a town from the Headless Horseman and (as of Wednesday) what seems to be a 100% chance of getting one from the Headless Horseman daily dungeon.

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!