Lab 5: Markov Chain Lab

Lab    5:    Markov    Chain    Lab
This    is    an    INDIVIDUAL    assignment.    Due    date    is    as    indicated    on    BeachBoard.    Follow    ALL    
instructions    otherwise    you    will    lose    points.    In    this    lab,    you    will    be    finding    the    probability    of    a    future    
outcome    based    on    some    current    state.    Unlike    the    previous    lab,    you    should    use    the    numpy    library    for    
this    lab.
Background:    
A    Markov    chain    is    a    process    where    future    outcomes    can    be    predicted    by    a    current    state.    These    
future    outcomes    are    based    on    probabilities.    The    probability    of    moving    on    to    a    certain    state    depends    
on    the    previous    state;    this    probability    does    not    change    with    time.    (Please    note    that    this    is    a    VERY    
oversimplified    explanation.    There’s    so    much    more    to    this    concept.)
We    can    express    these    probabilities    as    a    transition    matrix    that    looks    like    below:
� = T
�!!
⋮
�"!
�!#
⋮
�"#
…
⋱
…
�!"
⋮
�""
Y
Where    �$% is    the    probability    of    moving    from    state    i        to    state    j.
An    example    of    a    Markov    chain    is    the    weather    of    one    day    based    on    the    previous    day    where    the    states    
are    (1)    sunny,    (2)    cloudy,    (3)    rainy.    
Weather Weather    of    next    day
Sunny    (j=0) Cloudy    (j=1) Rainy    (j=2)
Sunny    (i=0) 80% 18% 2%
Cloudy    (i=1) 40% 50% 10%
Rainy    (i=2) 20% 60% 20%
This    table    represents    the    probabilities    of    some    day’s    weather    based    on    the    previous    day’s    weather.    
For    example,    the    probability    of    it    being    sunny    the    day    after    a    cloudy    day    (�#!) is    40%.
We    can    get    �" (nth    power    of    P)    by    matrix    multiplication.    �" would    represent    the    probability    of    
passing    from    state    i    to    state    j    in    n    stages.    
�# = T
�!!
⋮
�"!
�!#
⋮
�"#
…
⋱
…
�!"
⋮
�""
Y would    represent    the    probabilities    after    1    stage
�& = T
�!!
⋮
�"!
�!#
⋮
�"#
…
⋱
…
�!"
⋮
�""
Y × T
�!!
⋮
�"!
�!#
⋮
�"#
…
⋱
…
�!"
⋮
�""
Y would    represent    the    probabilities    after    2 stages
�' = T
�!!
⋮
�"!
�!#
⋮
�"#
…
⋱
…
�!"
⋮
�""
Y × T
�!!
⋮
�"!
�!#
⋮
�"#
…
⋱
…
�!"
⋮
�""
Y × T
�!!
⋮
�"!
�!#
⋮
�"#
…
⋱
…
�!"
⋮
�""
Y 3 stages
In    our    weather    example, (your    input    matrix    will    be    a    percentage,    you    must    change    it    to    decimals    
using    per_to_dec())
�# = T
0.8 0.18 0.02
0.4 0.5 0.1
0.2 0.6 0.2
Y after    1    stage    (next    day’s    weather)
�& = T
0.8 0.18 0.02
0.4 0.5 0.1
0.2 0.6 0.2
Y × T
0.8 0.18 0.02
0.4 0.5 0.1
0.2 0.6 0.2
Y = T
0.716 0.246 0.038
0.54 0.382 0.078
0.44 0.456 0.104
Y after    2    stage    (after    2    days)        
Thus,    the    probability    of    it    being    sunny    two    days    after    a    cloudy    day    (�#!
& ) is    54%
If    you    continue    to    calculate    �#, �&, �', �(, �) … ,    you    will    find    the    matrix    stops    changing    (changes    
negligibly).    This    is    called    the    long-run    distribution.    
Notice    that    all    values    from    �## to    �#& have    a    difference    of    less    than    0.0001.    This    is    where    we    will    
stop    for    this    lab    to    find    our    “long-run-distribution”    
Instructions:    
1. Take    a    close    look    at    the    Markov.py file.    There    are    four    empty    functions:    
per_to_dec(mat): Converts    percentages    in    matrix    into    a    decimals
sig_change(oldmat, newmat): Checks    if    there    are    any    “significant”    
changes    between    spatially    corresponding    elements    in    a    matrix.    (use    this    function    
in    long_run_dist) You    are    not    allowed    to    use    the    isclose()    or    any()    or    all()    
function.    You    will    not    get    any    points    if    you    do.
prob_x(mat, x): Returns    the    transition    probability    matrix    after    x    stages.    You    
are    not    allowed    to    use    the    matrix_power()    function.    You    will    not    get    any    points    if    
you    do.
long_run_dist(probs): Returns    the    long-run-distribution.    You    are    not    
allowed    to    use    the    matrix_power()    or    isclose()    or    any()    or    all()    function.    You    will    
not    get    any    points    if    you    do.
Read    through    both    of    their    descriptions    carefully.    Remember,    you    will    lose    points    if    
you    do    not    follow    the    instructions.    We    are    using    a    grading    script
2. Your    job    is    to    implement    all    of    the    listed    functions    so    that    it    passes    any    test    case.    
There    are    sample    test    cases    provided    for    you,    but    these    are    not    the    only    cases    that    
we    will    test.    Remember,    we    will    be    testing    each    function    separately    and    collectively.    
They    should    be    able    to    work    by    themselves    and    harmoniously    with    other    functions.
3. After    completing    these    functions,    comment    out    the    test    cases    (or    delete    them)    or    
else    the    grading    script    will    pick    it    up    and    mark    your    program    as    incorrect. Also,    
MAKE    SURE    THAT    YOUR    PROGRAM    DOES    NOT    PRINT    ANYTHING!!!    The    grading    
script    may    pick    up    any    printed    text    and    misinterpret    it    as    a    test    case    or    input    
causing    you    to    lose    points.
4. Convert    your    Markov.py file    to    a    .txt file.    Submit    your    Markov.py file    and    
your .txt file    on    BeachBoard.    Do    NOT    submit    it    in    compressed    folder.
5. Do    not    email    us    your    code    asking    us    to    verify    it.    We    will    answer    general    questions,    
but    we    will    not    debug    your    code    over    email.    
Grading    rubric:    
To    achieve    any    points,    your    submission    must    have    the    following.    Anything    missing    from    
this    list    will    result    in    an    automatic    zero.    NO    EXCEPTIONS!
• Submit    both    py    and    txt    files
• Files    named    correctly
• Program    has    no    errors    (infinite    loops,    syntax    errors,    logical    errors,    etc.)    that    
terminates    the    program
Please    note    that    if    you    change    the    function    headers    or    if    you    do    not    return    the    proper    
outputs    according    to    the    function    requirements,    you    risk    losing    all    points    for    those    test    
cases.    
Points     Requirement    
5 Correct    submission:    py    and    txt    file
5 Implemented    per_to_dec() correctly.    (5    test    cases)
15 Implemented    sig_change() correctly.    (5    test    cases)
10 Implemented    prob_x() correctly.    (5    test    cases)
15 Implemented    long_run_dist() correctly.    (5    test    cases)
5 Passes    5    original    test    cases    (also    commented    out    or    deleted    the    test    
cases)
*** NOTHING should be rounded. You may lose points if your values are rounded