A Markovian Journey through Statland [Markov chains probability animation, stationary distribution]

A Markovian Journey through Statland [Markov chains probability animation, stationary distribution]


[MUSIC PLAYING] JOE BLITZSTEIN: Ana Markov works as
a quality inspector for a company called Normal Distributors. The company has manufacturing
plants in five cities. Ana routinely conduct
surprise inspections at each site to check for abnormalities. She flies from city to city
randomly through airports with direct connecting flights. Every time she performs an
inspection, she stamps her logbook. Then she selects the
next city she will fly to randomly from all
available connecting flights with equal probabilities. The five cities are Averagemont,
Bayesville, Continuopolis, Discretown, and East Vandermonde. Not all of these cities are connected
via direct flights to each other. For example there is a direct flight
from Averagemont to Bayesville, but not from Averagemont to East Vandermonde. In the long run, which city do you
think she will spend the most time in? A Averagemont, B Bayesville,
C Continuopolis, D Discretown, E East Vandermonde, F about
equal among the five cities, or G it depends on which
city she starts out in. Today, Ana is in Bayesville. She uses a spinner to pick
randomly from all available cities with equal probabilities. Bayesville is a major hub and has direct
connections to all the other cities. The spinner lands on Averagemont
so that is her next stop. ANA MARKOV: Just another
average day in Averagemont. JOE BLITZSTEIN: After she
finishes her inspection, It’s time to choose the third stop. Let’s see where she lands next. ANA MARKOV: Bayesville again? Why do I keep ending up in Bayesville? JOE BLITZSTEIN: Now it’s time
for her to pick the next stop. ANA MARKOV: Oh great, East Vandermonde. I haven’t been there in ages. JOE BLITZSTEIN: East
Vandermonde is more remote and only has flights back to Bayesville. So she will definitely go
back to Bayesville next. ANA MARKOV: Why am I even
bothering with this silly spinner? If I keep doing this, I wonder
what fraction of my time will I end up spending in Bayesville. JOE BLITZSTEIN: The process
that Ana was following is an important example
of a Markov chain. The Markov property means
that at each time point, determining the next
city that Ana will go to depends only on where she currently
is and the randomness of her spinner. Given the present, the future
is independent of the past. This is a form of memorylessness. Given her current
location, her past history is irrelevant for predicting
where she will go next. To answer Ana’s question, let’s
consider the following problem. In the long run as Ana
continues this random process, what percentage of her time
will she spend in each city? Let’s plot this after
various numbers of trips. We have one bar for each city. And the height of each bar
indicates the percentage of time Ana has spent in that city overall. In our simulation, here is
how the distribution looks. [MUSIC PLAYING] At first, the plot
was fluctuating a lot. But now it seems to have stabilized. The distribution it has stabilized to
is called the stationary distribution of the Markov chain. We are showing one particular
run of the simulation. But Ana’s process will always converge
to the same stationary distribution no matter which city she starts out in. It turns out that the percentage
of time Ana spends in a city is proportional to its
number of connections. For example, Bayesville
has four connections and East Vandermonde only has one. So Ana visits Bayesville
four times as often as East Vandermonde in the long run. The network structure is
the key to determining the stationary distribution. [MUSIC PLAYING]

Leave a Reply

Your email address will not be published. Required fields are marked *