Unfortunately I don't have any mathematics software so I'm stuck with Excel, my brain, and brute force for now. Maybe I'll try to find a trial version of Maple or Matlab or something when I get home. So I'm going to have to start small, which is good, since it should hopefully make things easier to understand. This is going to be a pretty big wall of crunching the numbers text, so I've added in a jump break here. Jump on if you don't value your sanity!
First things first... What is a Markov Chain? Well, from what I can gather, it's a way to represent the probabilities of different state transitions in a finite state machine. The odds of the different transitions are fixed for each pair of states and depend solely on the current state and not on any previous states. The bottom of this Wikipedia article on stochastic matrices has a really good example about a cat and a mouse that's worth a read if you want more background.
The probabilities can be represented as an NxN matrix where N is the number of states in your machine and the current state can be represented as a 1xN vector. If you know for sure what state you're in (say, you're starting out) then this vector will have a single 1 and N-1 0's. Otherwise it will be composed of positive real numbers that sum to 1 which represents the odds of currently being in each state.
For example, lets pretend we're playing a dungeon crawling game (like, say, Zangband which I have recently started playing again) and we've come to a locked door. We have a 3% chance of picking the lock each time we try to pick the lock. How many tries will it take to pick the lock and get into the sweet, sweet treasure vault?
We have two states here. State A has the door locked. State B has the door unlocked. We also have 4 probabilities for the potential state transitions.
P(B | A) = .03 (The door was locked and we tried to pick it. 3% of the time that will work.)
P(A | A) = .97 (The door was locked and we failed to pick it.)
P(B | B) = 1 (A picked door remains picked.)
P(A | B) = 0 (The door won't relock itself.)
We can combine those values into our transition matrix P, which I don't have a good way of representing on a web page without resorting to terrible MSPaint art, but I will give it a shot...
| P | = | .97 | .03 |
| 0 | 1 |
Our initial state is in A. The door is definitely locked before we do anything. x0 = (1, 0). Try to pick the lock once and we end up in x1 = x0P = (.97, .03). Try again. x2 = x1P= x0PP = (.9409, .0591).
More generally, xi = x0P^i = (.97^i, 1-.97^i).
.97^i=.5 when i = 22.75657, so after 23 tries our odds of being in state B will be above our odds of being in state A.
Alternatively we can use the formula at the bottom of the previously mentioned Wikipedia page to find the expected number of iterations it will take to get to the absorbing state. We drop off the outer row/column from the matrix P to get the new matrix T, which in this case is just [.97]. We also drop the last entry in our row vector x0 to get t0, which in this case would just be [1].
E[K] = t0(I-T)^-1 * 1 = (1)*(.03)^-1*(1) = 33.33333
So to pick the lock half the time we'd need to try 23 times, but to expect to have the lock picked we'd have to try 33 times. I'm not really sure the distinction between the two, but after 33 tries you're only 63.4% of having opened the door.
Using that foundation we can build a similar (but much larger) matrix for the Hallow's End problem. (Well, for a generalized version anyway where we're only trick or treating and not questing.) To start simple and demonstrate, assume we already have 19 of the masks. What are the odds of transitioning to the different states from here?
Well, we can't lose masks, so we have 0 chance of regressing to a previous state if we had any. Our odds of getting a new mask are .2*.8*.05 = .008. (.2 because it looks like from WoWhead that we have a 20% chance of getting any mask from any given bag, .8 because Sthenno estimated the odds of getting a treat instead of a trick at 80% and I have no reason to dispute that, and .05 because we only need 1 of the 20 possible masks) So to transition to the 20 mask state we have a .8% chance and everything else is 0%, so the odds of staying in our current 19 mask state is 99.2%, which gives us the following base matrix for when we start with 19 masks:
| P | = | .992 | .008 |
| 0 | 1 |
Using the formulas above (logs for > 50% chance, E[K] for expected time to absorption) we get 86.3 tries for a 50% chance and 125 tries to absorption. With at least an hour between tries you're looking at spending 5-6 straight days to have a good chance of getting the 20th mask given that you already have 19 of them. (As a note, after 150 tries you're only 70% to have gotten the mask. 30% of people who have 19 masks and who trick or treat every hour for 6 straight days will fail.)
My manual skills are good enough to regress a little bit further. What if we had 18 masks already? Where do we stand now? The lower portion of our matrix remains the same (states with 19 and 20 masks can never get back to 18 masks) so the only new number we care about is the odds of getting a new mask when we have 18. This is .2*.8*.05*2 since there are now 2 masks we're happy to get. As such, our matrix is:
| P | = | .984 | .016 | 0 |
| 0 | .992 | .008 | ||
| 0 | 0 | 1 |
In order to do the 50% thing I'll need to build a generalized form for xi, but after iterating a couple times I am not convinced there is an easy form to represent this information. Instead I just plug my formulae into Excel and see when the bottom number first gets bigger than .5. It turns out this number is 154. E[K] I can still work out, though.
E[K] = {1 0}*{.016 -.016 | 0 .008}^-1*{1 | 1} = {1 0}*1/(.016*.008-(-.016)*0)*{.008 .016 | 0 .016}*{1 | 1} = 1/.000128*{1 0}*{.024 | .016}= 187.5
(It took a stupid amount of time to work that out since I kept making silly mistakes. I ended up writing things out on a napkin and using this site to see someone else going through the steps to find out where my missing sign came from. Turns out 0 - .016 is actually -.016 and not .016. Who knew?)
So if we've already got 18 of the 20 masks and we're just trick or treating we can expect to spent 188 tries to get up to 20. That's less than 8 straight days of trick or treating every hour which doesn't seem sooooo bad?
I also notice a bit of a pattern developing. The expected time to absorption at 19 was 125. At 18 it was 187.5 and the fundamental matrix had as it's top row { 62.5 125 }. The site I linked just above says those numbers represent how much time we expect to stay in each of the given states before we end up absorbed. I would now guess that the value when we start at 17 will be 229.1666 and the value from 0 would be 449.717.
Lets calculate the value at 17 manually again to see if the pattern holds.
| P | = | .976 | .024 | 0 | 0 |
| 0 | .984 | .016 | 0 | ||
| 0 | 0 | .992 | .008 | ||
| 0 | 0 | 0 | 1 |
E[K] = {1 0 0}*{.024 -.024 0 | 0 .016 -.016 | 0 0 .008}^-1*{1 | 1 | 1} = {1 0 0}*{41.67 62.5 125 | 0 62.5 125 | 0 0 125}*{1 | 1 | 1} = {1 0 0}*{229.17 187.5 125} = 229.17
Which is just as predicted above. It also turns out the there is an online mathematics calculator at the same site so I built the full matrix starting from 0 and fed it in. I am not surprised to find the answer it returned was 449.717. I also fed it in x0P^450 and found that we have a 57.68% chance of getting the achievement - from scratch - in 450 tries. Which is only 2 years of 24/7 trick or treating during the holiday!
No comments:
Post a Comment