Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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!
Associated Topics:
College Probability

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/