1 of 31

OR 2

Dr. Akram AlSukker

2 of 31

Definition of A Markov Chain

3 of 31

4 of 31

5 of 31

6 of 31

Gardener Problem

7 of 31

8 of 31

Spammers Go Markovian

  • The message is syntactically correct but its content is nonsensical
  • It turned out that these syntactically correct but otherwise nonsensical inserts are totally computer generated and are used by spammers to bypass spam filters. Interestingly, the computer code used to generate these messages has its roots in Markov chains.
  • The idea is to scan through a text (a paragraph, a chapter, or an entire book) to create a table that tallies the frequencies a word in the text is followed by other words. For example, in the text “It is not what you say; it is what you do.” the states of the Markov chain are represented by 7 words (8, if It and it are distinguishable) and two punctuations. There is a 100% chance that It (or it) is followed by is, and a 50-50 chance that is is followed by either not or what

9 of 31

10 of 31

11 of 31

Absolute And n-Step Transition Probabilities

12 of 31

13 of 31

14 of 31

Cola Example

15 of 31

16 of 31

17 of 31

Steady Satate

18 of 31

19 of 31

20 of 31

21 of 31

22 of 31

23 of 31

First Passage time

24 of 31

25 of 31

26 of 31

Analysis of Absorbing state

27 of 31

28 of 31

Example

  • A product is processed on two sequential machines, I and II. Inspection takes place after a product unit is completed on either machine. There is a 5% chance that the unit will be junked before inspection. After inspection, there is a 3% chance the unit will be junked, and a 7% chance of being returned to the same machine for reworking. Else, a unit passing inspection on both machines is good.
    • For a part starting at machine I, determine the average number of visits to each�state.
    • If a batch of 1000 units is started on machine I, determine the average number of�completed good units.

29 of 31

0

30 of 31

31 of 31