Transcript ppt - Department of Electrical Engineering

048866: Packet Switch
Architectures
Review #3: Discrete-Time Markov Chains
Dr. Isaac Keslassy
Electrical Engineering, Technion
[email protected]
http://comnet.technion.ac.il/~isaac/
Simple DTMCs
e
p
1-p
0
0
1
q
1-q
1
a
c
b
d
f
2
“States” can be labeled (0,)1,2,3,…
 At every time slot a “jump” decision is
made randomly based on current state


(Sometimes the arrow pointing back to the same state is omitted)
Spring 2006
048866 – Packet Switch Architectures
2
1-D Random Walk
p
1-p
X(t)
Time is slotted
 The walker flips a coin every time slot to
decide which way to go


Spring 2006
048866 – Packet Switch Architectures
3
Single Server Queue
Geom(q)
Bernoulli(p)
Consider a queue at a supermarket
 In every time slot:

 A customer
arrives with probability p
 The HoL customer leaves with probability q
Spring 2006
048866 – Packet Switch Architectures
4
Birth-Death Chain
0
1
2
3
Can be modeled by a Birth-Death Chain
(aka. Geom/Geom/1 queue)
 Want to know:

 Queue
size distribution
 Average waiting time, etc.
Spring 2006
048866 – Packet Switch Architectures
5
Discrete Time Markov Chains

Markov property (memoryless): “Future” is
independent of “Past” given “Present”

A sequence of random variables {Xn} is called a
Markov chain if it has the Markov property:

States are usually labeled {0,1,2,…}
State space can be finite or infinite

Spring 2006
048866 – Packet Switch Architectures
6
Transition Probability

Probability to jump from state i to state j
Assume stationary: independent of time
 Transition probability matrix:
P = (pij)
 Two state MC:

Spring 2006
048866 – Packet Switch Architectures
7
Stationary Distribution
Define
Then pk+1 = pk P (p is a row vector)
Stationary Distribution:
if the limit exists.
If p exists, we can solve it by
Spring 2006
048866 – Packet Switch Architectures
8
Balance Equations

These are called balance equations
 Transitions
in and out of state i are
balanced
Spring 2006
048866 – Packet Switch Architectures
9
In General

If we partition all the states into two sets,
then transitions between the two sets must
be “balanced”.
 Equivalent
to a bi-section in the state
transition graph
 This can be easily derived from the Balance
Equations
Spring 2006
048866 – Packet Switch Architectures
10
Conditions for p to Exist (I)

Definitions:
 State
j is reachable by state i if
 State
i and j communicate if they are
reachable by each other
 The Markov chain is irreducible if all states
communicate
Spring 2006
048866 – Packet Switch Architectures
11
Conditions for p to Exist (I) (cont’d)
Condition: The Markov chain is
irreducible
 Counter-examples:

1
1
Spring 2006
3
2
p=1
2
048866 – Packet Switch Architectures
4
3
12
Conditions for p to Exist (II)
The Markov chain is aperiodic:
 Counter-example:

0
1
0
1
0
1
1
0
2
Spring 2006
048866 – Packet Switch Architectures
13
Conditions for p to Exist (III)

The Markov chain is positive recurrent:
 State
i is recurrent if it will be re-entered
infinitely often:
 Otherwise
transient
 If recurrent
• State i is positive recurrent if E(Ti)<1, where Ti is
time between visits to state i
• Otherwise null recurrent
Spring 2006
048866 – Packet Switch Architectures
14
Irreducible Ergodic Markov Chain

The Markov chain is ergodic if it is positive recurrent and
aperiodic.

In an irreducible ergodic Markov chain, if
pk+1 = pk P, then:


p is independent of the initial conditions
p(j) is the limiting probability that the process will be in
state j at time n.


It is also equal to the long-run proportion of time that the
process will be in state j (ergodicity).
It is called the stationary probability.
Spring 2006
048866 – Packet Switch Architectures
15
Irreducible Ergodic Markov Chain

If f is a bounded function on the state
N
space:
 f (Xn)
lim
N 


n 1
N
  f ( j) p ( j)
j 0
Let mjj be the expected number of
transitions until the Markov chain, starting
in state j, returns to state j. Then mjj=1/p(j)
References: books on stochastic processes (e.g., Ross)
Spring 2006
048866 – Packet Switch Architectures
16