Subscribe to DSC Newsletter

Challenge of the week: interesting quantities associated with Markov chains

To access the main article on this subject, click here.

Markov chains are a fondamental statistics and data science tool, extensively used in modeling and operations research. A basic, 2-states model is as follows:

You start at time t=0, walking along the X-axis (representing time). At each iteration (also called step), you move up with probability p, and down with probability q, along the Y-axis. The Y-axis could represent gain/losses in a gamble (throwing a dice), stock market gains etc. When p = q, this is called a random walk. 

Random walk in 2 dimensions, showing 2 million steps (source: Wikipedia)

This is easily generalized to 2 (or 3) dimensions, for instance to represent the path of a drunkard trying to get back home and getting lost (see picture - a simulated example), or the movements of a gas molecule in a container. Monte Carlo simulations can be used to compute various quantities associated with these models.

Here are questions for you to answer (challenge of the week)

  • In a one-dimensional realization of a random walk, what is the probability of never crossing the X-axis?
  • What is the average time between two successive crossings of the X-axis?
  • Is the process (Y values) bounded or not? If not, it means that over time, you will reach any pre-specified, arbitrary large integer value.
  • What is the highest point M that you are expecting to reach, after n steps? What is the statistical distribution of M, as a function of n?
  • In a 2-dimensional random walk, what is the probability of permanently getting stuck in one quadrant?
  • Are you likely to spend most of your time on the same side (either above or below) of the X-axis, or do you expect to fluctuate evenly, in the long run spending the same amount of time above and below?
  • For a random walk on a circle, are you going to fill the entire circle (visiting every point on the circle), or only a portion of it (what proportion), depending on how big your steps are relative to the radius? What is the propotion of visited points, that are going to be visited at least twice? Let's assume that the ratio step size by circle radius is NOT a rational number. 
  • Same question if circle is replaced by a sphere, or an n-dimensional hypershere.
  • On a 2-dimensional random walk, what is the chance of ever reaching your initial position ever again? And how many times would you expect to cross the origin?

Related articles

Views: 1891

Reply to This

Follow Us

On Data Science Central

On DataViz

On Hadoop

© 2017 is a subsidiary and dedicated channel of Data Science Central LLC   Powered by

Badges  |  Report an Issue  |  Terms of Service