[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

857.0. "Markov chain and bugs" by ELWD2::CHINNASWAMY () Thu Apr 07 1988 21:08

                         Markov Chains

 Here is a problem that one can find in a few college text books for a first
 year language course( such as Fortran).

 A bug is at one corner of a square, say A, and there is a bug killer at the
 opposite corner, C ( see Fig.)

                          D +-----------+ C
                            |           |
                            |           |
                            |           |
                            |           |
                          A +-----------+ B

 The bug does not stay at any one place and can move only along the edges of
 the square ( AB, BC, AD, DC ). It takes a minute to crawl along one edge 
 ( say from A to B ). From any one corner, except C, it chooses any one of the
 edges with equal probability. For instance, if it is at A, the probability
 that it moves to B is 1/2. Once it reaches B, it can choose to retrace its
 path back to A with probability 1/2 or can go to C with probability 1/2. If
 it goes to C, it is killed at C. What is the expected life time of the bug?

 This problem can be solved by writing a simulation program or using Markov
 chains ( or a different method, I don't know what). I remember solving it for
 a cube using Markov chains ( more than fifteen years ago for my class).

 Can we generalize it and solve it for an n-cube with one bug, with more than
 one bug in different corners ( or same corner ) with all sorts of restrictions
 one can place on the bugs ( such as no two bugs can travel along the same path
 at any one time, etc. ). Replace the bugs by packets and the cube by a network.
 Let your imaginations fly and come up with more practical problems using these
 techniques.
T.RTitleUserPersonal
Name		DateLines
857.1simple solution for the simple caseZFC::DERAMODaniel V. D'EramoMon Apr 11 1988 16:1620
    A simple solution for the simplest case:
    
    
    Think of the bug as going through a sequence of discrete states at
    one minute intervals.  Use three states: A, B+D, C.  From state A
    the bug goes to state B+D.  From state B+D the bug goes to A or to
    C, each with probability 1/2.  From state C the bug remains in state
    C (because it's dead).
    
    So for a bug at A at a given time, there are two possibilities for
    two minutes later, each with probability 1/2:  the bug is back at A,
    or is dead at C.
    
    So the expected lifetime of the bug is
    
         2 minutes * (1/2 + 2/4 + 3/8 + 4/16 + ... + n/2^n + ...)
    
    which is 4 minutes.
    
    Dan
857.2CLT::GILBERTMon Apr 11 1988 17:2995
And for an n-cube, we have n+1 states:

	Distance 0 from the start (the starting corner)
	Distance 1 from the start
	...
	Distance n from the start (where the bug kiler is)

And we have the following transitions:

	D0 -> D1
	D1 -> 1/n D0 + (n-1)/n D2
	D2 -> 2/n D1 + (n-2)/n D3
	...
	Di -> i/n D<i-1> + (n-i)/n D<i+1>
	...
	Dn -> (none)

Letting Ei be the expected lifetime of a bug at distance i from the start,
we have:

	E0 = 1 + E1
	E1 = 1 + 1/n E0 + (n-1)/n E2
	...
	Ei = 1 + i/n E<i-1> + (n-i)/n E<i+1>
	...
	E<n-1> = 1 + (n-1)/n E<n-2> + 1/n En
	En = 0

For a square, we have:

	E0 = 1 + E1
	E1 = 1 + 1/2 E0 + 1/2 E2
	E2 = 0

	E0 = 1 + E1 = 1 + (1 + 1/2 E0) = 2 + 1/2 E0
	E0 = 4 (expected lifetime)

For a cube we have:

	E0 = 1 + E1
	E1 = 1 + 1/3 E0 + 2/3 E2
	E2 = 1 + 2/3 E1 + 1/3 E3
	E3 = 0

	E1 = 1 + 1/3 E0 + 2/3 E2
	   = 1 + 1/3 (1 + E1) + 2/3 (1 + 2/3 E1)
	   = 2 + 7/9 E1
	E1 = 9
	E0 = 10	(expected lifetime)
	E2 = 7


For an n-cube, define Ki by:

	Ei = Ki + E<i+1>

Then
	n Ei = n + i E<i-1> + (n-i) E<i+1>
	     = n + i (K<i-1> + Ei) + (n-i) E<i+1>
	(n-i) Ei = n + i K<i-1> + (n-i) E<i+1>
	Ei = (n + i K<i-1>)/(n-i) + E<i+1>

So that
	K0 = 1
	Ki = (n + i K<i-1>)/(n-i) = 1 + (K<i-1> + 1) * i/(n-i)
	
And
	E0 = K0 + E1 = K0 + K1 + E2 = ... = K0+...+K<n-1> + En

	     n-1
	E0 = sum K<i>
	     i=0

Using these equations, we can simplify the expectation calculations.

For n = 2 (the square), we have

	K0 = 1
	K1 = 1 + (K0 + 1) * 1/(2-1) = 3
	E0 = K0 + K1 = 1 + 3 = 4

For n = 3 (the cube), we have

	K0 = 1
	K1 = 1 + (K0 + 1) * 1/(3-1) = 2
	K2 = 1 + (K1 + 1) * 2/(3-2) = 7
	E0 = K0 + K1 + K2 = 1 + 2 + 7 = 10

For n = 4, we have:

	K0 = 1
	K1 = 1 + (K0 + 1) * 1/(4-1) = 1 + 2/3 = 5/3
	K2 = 1 + (K1 + 1) * 2/(4-2) = 1 + 8/3 = 11/3
	K3 = 1 + (K2 + 1) * 3/(4-3) = 1 + 14/3 * 3 = 15
	E0 = K0 + K1 + K2 + K3 = 1 + 5/3 + 11/3 + 15 = 64/3 = 21.3333...