Probability and Finding the Duration of an Event
Date: 04/18/2009 at 01:52:36 From: Fabian Subject: Average Effect Uptime I have come across a problem... and I have no idea how to approach it: Event A happens constantly every 3 seconds, and each time Event A happens there is a 15% chance to trigger Effect B. Effect B lasts 12 seconds. Given that Effect B would reset its duration when it is triggered while already in effect, what is the average uptime of Effect B? This is a mechanic found in World of Warcraft. I have translated it into math terms so it is easier for people with no WoW background to understand it.
Date: 04/21/2009 at 19:59:07 From: Doctor Vogler Subject: Re: Average Effect Uptime Hi Fabian, Thanks for writing to Dr. Math. And thanks for the translation, as I have little experience with WoW. So you are interested in average uptime, not (for example) the percentage of total time that B is happening. So you want to know, when B starts, what is the mathematical expectation of how long it will continue until it stops? Of course, it has to go at least 12 seconds. It will go exactly 12 seconds if A does *not* trigger B at either the 3-second mark, the 6-second mark, the 9-second mark, or the 12-second mark, for a probability of (1 - 0.15)^4. It will go exactly 15 seconds if A *does* trigger B (again) at the 3-second mark, but not in any of the next four marks, for a probability of 0.15*(1 - 0.15)^4. It will go exactly 18 seconds if A *does* trigger B (again) at the 6-second mark (regardless of whether it triggered B already at the 3-second mark), but not in any of the next four marks, for a probability of 0.15*(1 - 0.15)^4. Similarly for 21 and 24 seconds. But to go exactly 27 seconds, we need A to trigger B at (at least) one of the first four marks, then at the fifth mark (at 15 seconds) and not the next four. The probability of A triggering B at at least one of the first four marks is the probability that it doesn't *never* trigger B, which is 1 - (1 - 0.15)^4, so the probability of exactly 27 seconds is (1 - (1 - 0.15)^4)*0.15*(1 - 0.15)^4. Things start to get more complicated after that. For event B to go exactly 3k seconds, it needs for A to trigger B at the (k-4)'th step, to not trigger B at the (k-3)'rd, (k-2)'nd, (k-1)'st, or k'th steps, and it also needs that A doesn't fail to trigger B for four consecutive steps from the first to the (k-5)'th. So the hard question is what is the probability that A triggers B for four consecutive steps in m steps. So we have two related values, namely P(k) = the probability that the first four consecutive misses are in positions k-3, k-2, k-1, and k, and S(k) = the probability that there are NOT four consecutive misses among the first k positions where, in a particular position, a "hit" happens with probability p = 15% = 3/20, and a "miss" happens with probability q = 1 - p = 85% = 17/20. These are related by 1 - S(k) = P(0) + P(1) + P(2) + P(3) + ... + P(k) because each side of the equation is the probability that there ARE four consecutive misses among the first k positions. Now we take a leap of intuition and notice that all of my discussion above amounts to the equation P(k) = S(k-5)*p*q^4 (when k >= 5) that the probability that the first four consecutive misses are in positions k-3, k-2, k-1, and k is equal to the probability that there are not four consecutive misses in the first k-5 positions, but there is a hit in the k-4'th position, and then misses in the last four positions. We can also write this equation as S(k-1) - S(k) = S(k-5)*p*q^4. This is what is known as a (linear) recurrence relation in the sequence S(k). If you search our archives for "recurrence relation" or "linear recurrence relation," you'll find that there is a general technique for solving a linear recurrence relation, which results in writing the general term S(k) as a sum of a handful of exponential functions. The trick is finding the roots of the characteristic equation x^5 - x^4 + pq^4 = 0 It turns out that one of the roots is q = 17/20. There are two other real roots, which are approximately u = 0.742812948276366489463128811613427695449921980586756417943441 and v = -0.47962705658325330851176978146539306897516893242000225082259. The other two roots are a (conjugate) pair of complex roots, namely a + bi and a - bi, where a = -0.056592945846556590475679515074017313237376524083377083560 b = 0.5053309373929750613399936485557216658012852523629916193118 which is sometimes more convenient to write in polar form (using Euler's equation) Imaginary exponents and Euler's equation. http://mathforum.org/dr.math/faq/faq.euler.equation.html as the numbers z = a + bi = r*exp(it) w = a - bi = r*exp(-it) where r = 0.508490037076493926392046871317511536717396191925784337476 t = 1.682323460471605404544337798051378478981715564154056557507 Then it turns out that the sequence S(k) can be expressed as S(k) = A*q^k + B*u^k + C*v^k + D'*z^k + E'*w^k or (using only real numbers) S(k) = A*q^k + B*u^k + C*v^k + D*r^k*cos(kt) + E*r^k*sin(kt) for some constants A, B, C, D, and E. We can determine their values by the known values of S(k), namely S(0) = 1 S(1) = 1 S(2) = 1 S(3) = 1 S(4) = 1 - q^4 Substituting our new formula for S(k) into the left sides of those five equations, we get five linear equations, which we can write as a matrix equation and solve by inverting the matrix, or Gaussian elimination, or something similar: [ 1 1 1 1 0 ] [ A ] = [ 1 ] [ q u v r*cos(t) r*sin(t) ] [ B ] = [ 1 ] [ q^2 u^2 v^2 r^2*cos(2t) r^2*sin(2t) ] [ C ] = [ 1 ] [ q^3 u^3 v^3 r^3*cos(3t) r^2*sin(3t) ] [ D ] = [ 1 ] [ q^4 u^4 v^4 r^4*cos(4t) r^2*sin(4t) ] [ E ] = [ 1-q^4 ] The result is that A = 0 (interesting that the obvious root is not actually relevant; we could probably have written a degree-four recurrence relation in S(k)), and B = 1.85636264406287676837191475659876788989306008687285074240011 C = -0.6644905984876329238545995734528356706741360906265360991366 D = -0.1918720455752438445173151831459322192189239962463146432635 E = -1.4020445423868114795896710160407999491812703424101825404634 Now we can use these numbers to check the values that we determined by hand, such as S(0) = 1 S(1) = 1 S(2) = 1 S(3) = 1 S(4) = 1 - q^4 S(5) = 1 - (p+1)q^4 S(6) = 1 - (2p+1)q^4 S(7) = 1 - (3p+1)q^4 and P(0) = 0 P(1) = 0 P(2) = 0 P(3) = 0 P(4) = q^4 P(5) = pq^4 P(6) = pq^4 P(7) = pq^4 P(8) = pq^4 P(9) = (1 - q^4)pq^4 P(10) = (1 - (p+1)q^4)pq^4 Furthermore, we can now use this formula to evaluate the *expectation* (which is the usual meaning for "average" in probability) of the value 3*k, which is E = 3*P(1) + 6*P(2) + 9*P(3) + 12*P(4) + 15*P(5) + ... or E = sum(from i=1 to infinity) of (3i)*P(i) or E = sum(from i=1 to infinity) of (3i)*(S(i-1) - S(i)). After verifying that i*S(i) approaches zero as i grows to infinity, it doesn't take too much work to show that this sum can also be written as E/3 = sum(from i=0 to infinity) of i*S(i). = sum (A*q^k + B*u^k + C*v^k + D*r^k*cos(kt) + E*r^k*sin(kt)) = A*(sum q^k) + B*(sum u^k) + C*(sum v^k) + D*(sum r^k*cos(kt)) + E*(sum r^k*sin(kt)) Of course, the first three sums are easy to determine, since they are simple geometric series. (And the first one is irrelevant, since A=0.) We have sum u^k = 1/(1 - u) sum v^k = 1/(1 - v) The last two sums are a little harder, but they can actually be evaluated as geometric series too, though you have to use complex numbers to do it. You can also write the formula in terms of exponents and trig functions, and prove it by induction, if you want to avoid complex numbers. Using the first method, we get sum r^k*cos(kt) = sum r^k*(e^(ikt) + e^(-ikt))/2 = (1/2)(sum (r*e^(it))^k + sum (r*e^(-it))^k) = (1/2)(1/(1 - r*e^(it)) + 1/(1 - r*e^(-it))) and similarly for the other one. The bottom line is that E/3 = 6.104572502723865854096574514194035033105446534404521018666 and therefore E = 18.31371750817159756228972354258210509931633960321356305599789 and so the average uptime of event B is 18.3137 seconds. If you have any questions about this or need more help, please write back and show me what you have been able to do, and I will try to offer further suggestions. - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/
Date: 04/22/2009 at 01:03:29 From: Fabian Subject: Thank you (Average Effect Uptime) Thank you so much Dr. Vogler for your very detailed explanation!
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.