A Data Science Central Community

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**

Tags:

© 2020 TechTarget, Inc. Powered by

Badges | Report an Issue | Privacy Policy | Terms of Service

**Most Popular Content on DSC**

To not miss this type of content in the future, subscribe to our newsletter.

- Book: Applied Stochastic Processes
- Long-range Correlations in Time Series: Modeling, Testing, Case Study
- How to Automatically Determine the Number of Clusters in your Data
- New Machine Learning Cheat Sheet | Old one
- Confidence Intervals Without Pain - With Resampling
- Advanced Machine Learning with Basic Excel
- New Perspectives on Statistical Distributions and Deep Learning
- Fascinating New Results in the Theory of Randomness
- Fast Combinatorial Feature Selection

**Other popular resources**

- Comprehensive Repository of Data Science and ML Resources
- Statistical Concepts Explained in Simple English
- Machine Learning Concepts Explained in One Picture
- 100 Data Science Interview Questions and Answers
- Cheat Sheets | Curated Articles | Search | Jobs | Courses
- Post a Blog | Forum Questions | Books | Salaries | News

**Archives:** 2008-2014 |
2015-2016 |
2017-2019 |
Book 1 |
Book 2 |
More

**Most popular articles**

- Free Book and Resources for DSC Members
- New Perspectives on Statistical Distributions and Deep Learning
- Time series, Growth Modeling and Data Science Wizardy
- Statistical Concepts Explained in Simple English
- Machine Learning Concepts Explained in One Picture
- Comprehensive Repository of Data Science and ML Resources
- Advanced Machine Learning with Basic Excel
- Difference between ML, Data Science, AI, Deep Learning, and Statistics
- Selected Business Analytics, Data Science and ML articles
- How to Automatically Determine the Number of Clusters in your Data
- Fascinating New Results in the Theory of Randomness
- Hire a Data Scientist | Search DSC | Find a Job
- Post a Blog | Forum Questions