Back to Portfolio
Research Paper

Markov Chains

Theory, Applications, and AI Integration

December 2025

Authors

Research Team

  • Ayman Loay • 320240079
  • Youssef Hussein Abdallah • 320240062
  • Mohamed Ahmed Mohamed Ali • 320240066
  • Ahmed Mahmoud • 320240024

Technical Team

  • Shymaa Mohamed Ahmed • 320240067
  • Basmala Refaat Mohamed Azab • 320240022
  • Mariam Ahmed M. A. Abdou Ayoub • 320240011
  • Aya Yasser Abd El Hamid Hfny • 320240065
  • Maryam Ahmed Mohamed Fekry • 320240105

Front-End Engineer

Ahmed Hossam Aldeen • 320240051

Team Leader

Moaz Hassan Ismail El Garawany • 320240032

Table of Contents

1. Introduction to Markov Chains

A Markov chain is a mathematical model for a random process that moves step by step between a set of possible "states," where the probability of the next state depends only on the current state, not on the full history.

Basic Idea

In a Markov chain, time is viewed in discrete steps n = 0, 1, 2, ..., and at each step the system is in one of a countable set of states. The defining Markov property is that the conditional distribution of the next state given the present and past depends only on the present state, which is often described as "memoryless" with respect to the past.

Formal Definition

A discrete-time Markov chain is a sequence of random variables X₀, X₁, X₂, ... taking values in a state space S such that for all times n and states:

P(Xₙ₊₁ = iₙ₊₁ | Xₙ = iₙ, ..., X₀ = i₀) = P(Xₙ₊₁ = iₙ₊₁ | Xₙ = iₙ)

Key Components

• **State space:** The set of all possible states (weather categories, web pages, integer positions) • **Transition matrix:** A matrix P = (pᵢⱼ) where pᵢⱼ is the probability of moving from state i to state j • **Initial distribution:** A probability vector specifying the starting state

Behavior Over Many Steps

Raising the transition matrix to higher powers (Pⁿ) describes the probabilities of moving between states in n steps. Under suitable conditions (irreducibility and aperiodicity), the chain converges to a stationary distribution.

2. App Navigation Theory

Markov chains model app navigation as user movements between screens, where the next screen depends only on the current one, not past ones. This forgetful trait helps predict user paths in mobile or web apps simply.

Key Ideas in Navigation

States are app screens like home, profile, or settings. The transition table shows chances, such as 0.6 from home to search and 0.4 to profile, with each row adding to 1. Starting chances set the first screen, often login or home.

Tracking User Paths

Raising the transition table to higher powers shows chances over multiple steps, like getting to checkout from home in three taps. Chains that connect fully and avoid cycles settle into a steady pattern of screen visits for better app design.

Real-World Uses

• **PageRank:** Google treats web links as moves to rank pages by long-term visit odds • **User Retention:** Spots drop-off spots between screens to improve new user guides • **A/B Tests:** Compares move tables between app versions to boost engagement

Pros and Cons

These models create path heatmaps and smart next-screen hints. Downsides include ignoring strong path links, like in shopping carts.

3. PageRank and Probability Applications

PageRank, Google's foundational algorithm, ranks web pages by modeling them as a random surfer following links, with importance derived from incoming link quality and quantity.

Link Graph to Matrix

The link graph converts to a transition matrix where each column sums to 1, representing link probabilities from one page. The matrix entries reflect outgoing link fractions, capturing the web's hyperlink structure as a Markov chain.

Damping Factor Role

The damping factor, typically 0.85, introduces randomness by letting the surfer jump to any page with probability 1-d (0.15), preventing infinite loops in disconnected graphs. Google's matrix formula becomes:

PR(p) = (1−d)/N + d × Σ PR(q)/L(q)

This blends link-following with uniform jumps. Lower damping speeds convergence but reduces internal link emphasis.

Convergence Process

PageRank iterates by multiplying the transition matrix with the prior rank vector until changes fall below a tolerance, often converging in 45-52 steps for large networks like Google's early 322 million links.

SEO Implications

SEO leverages PageRank by earning quality backlinks, as pages with authoritative inbound links gain higher scores. Anchor text relevance and link diversity further amplify this.

4. Markov Decision Processes in AI

Reinforcement Learning (RL) agents are designed to solve the problem of sequential decision-making—choosing a sequence of actions over time to maximize a long-term accumulated reward.

4.1 The MDP Framework

The essential mathematical framework governing this interaction is the Markov Decision Process (MDP), which originated in operations research in the 1950s. It transforms the RL challenge into a solvable optimization problem.

The Markov Property

The MDP relies on the Markov Property, the memoryless principle which states that the future state depends only on the current state and the action taken, independent of history.

4.2 Formalizing the MDP

An MDP is formally defined by five core components: • **State Space:** The set of all possible environment configurations • **Action Space:** The set of commands the agent can execute • **Transition Probabilities:** Probability of moving from one state to the next • **Reward Function:** Immediate scalar feedback for an action/transition • **Discount Factor:** Controls how much future rewards are valued

4.3 The Bellman Optimality Equation

The core of finding the best strategy (the optimal policy) lies in solving the Bellman Optimality Equation:

V*(s) = maxₐ [R(s,a) + γ Σ P(s'|s,a) V*(s')]

This equation is the foundation for algorithms like Q-learning.

4.4 Gridworld Example

The classic Gridworld problem demonstrates optimal policy discovery. States are discrete positions on a 2D grid, and the algorithm iteratively evaluates and improves strategies until the optimal path is found.

References

Section 1 & 2: Introduction and App Navigation

  1. 1.An introduction to Markov chains – Systematic, textbook-style introduction
  2. 2.Setosa: Markov Chains explained visually – Interactive diagrams
  3. 3.Wikipedia contributors. Markov chain. Wikipedia.
  4. 4.Sekhon, P., & Bloom, D. Applications of Markov Chains. Math LibreTexts.
  5. 5.Introduction to Markov Chains and Applications. Chalmers University.

Section 3: PageRank Applications

  1. 1.Wikipedia contributors. Markov chain. Wikipedia.
  2. 2.Sekhon, P., & Bloom, D. Applications of Markov Chains. Math LibreTexts.
  3. 3.Introduction to Markov Chains and Applications. Chalmers University.

Section 4: AI Applications (MDP)

  1. 1.Understanding the Bellman Equation in Reinforcement Learning. DataCamp.
  2. 2.Wikipedia contributors. Markov decision process. Wikipedia.
  3. 3.Markov Decision Process (MDP) in Reinforcement Learning. GeeksforGeeks.
  4. 4.Part 1: Key Concepts in RL. Spinning Up documentation. OpenAI.
  5. 5.Karpathy, A. REINFORCEjs: Gridworld with Dynamic Programming. Stanford.
Back to Top