markovpath

A high-performance Python library for sequence probability estimation, next-state prediction, Markov attribution modeling, and AI agent trajectory analysis using Discrete-Time Markov Chains (DTMC).

Rooted in peer-reviewed Web Usage Mining research (Sarukkai, 2000), markovpath provides a clean, vectorized, Scikit-learn-style API to model user navigation sessions, clickstreams, or AI decision traces.

---

🚀 Key Capabilities

• State Probability (Prior Distribution): Calculates the relative frequency distribution of states across all sessions.
• Transition Probability Matrix ($P$): Computes normalized, row-stochastic transition probabilities ($\sum_j P_{ij} = 1.0$) with optional self-loop modeling.
• Path / Trail Probability Scoring: Evaluates the joint probability $P(\text{Path})$ using the probability chain rule, with optional log-scale scoring to avoid numerical underflow on long sequences.
• Top-K Next-Link Prediction: Predicts and ranks the most probable next pages or actions given the current state.
• Multi-Touch Attribution (Removal Effect): Uses Absorbing Markov Chains $(I - Q)^{-1} R$ to calculate the exact conversion drop when a touchpoint is removed.
• Monte Carlo Path Simulation: Generates realistic synthetic user trails from learned transition distributions.
• Laplace Smoothing: Prevents zero-probability crashes on previously unseen state transitions.

---

🎯 Applications & Use Cases

1. 🤖 AI & Autonomous Agent Systems

• LLM Agent Trajectory Analysis & Pruning: Autonomous agents (e.g., ReAct, Tool-Calling Agents) follow sequential decision paths: [Thought -> Search -> Read -> Code -> Test -> Exit]. markovpath models agent traces to detect infinite loops ($A \to B \to A \to B$), score trajectory likelihood, and prune low-probability exploration branches in agent planning trees.
• Model-Based Reinforcement Learning (RL): Bootstraps empirical transition matrices $P(s' \mid s, a)$ as environment priors for Markov Decision Processes (MDPs).
• Behavioral Anomaly & Bot Detection: Natural user navigation trails have high likelihood under the trained Markov model. Malicious bots or scrapers follow unnatural patterns that register as anomalous low-probability outliers.
• Synthetic Data Generation: Simulates realistic clickstreams for privacy-safe machine learning model training without exposing raw user logs.

2. 📊 Web Analytics & Marketing Attribution

• Multi-Touch Attribution (MTA): Moves beyond naive "first-click" or "last-click" heuristics by mathematically quantifying each marketing channel's true contribution via the Removal Effect.
• Conversion Rate & Funnel Optimization (CRO): Pinpoints friction points where users drop off from the purchase funnel to exit.
• Predictive Pre-fetching & Caching: Web browsers and CDNs can pre-load top predicted next pages (model.predict_next()) to achieve near-instantaneous page transitions.

---

📦 Installation

pip install markovpath

Requirements: Python >= 3.8, NumPy >= 1.20, Pandas >= 1.3

---

⚡ Quickstart

1. Basic Fitting & Next-State Prediction

from markovpath import MarkovPath

# Plain Python lists, NumPy arrays, or Pandas Series
paths = [
    ["Home", "Products", "Cart", "Checkout"],
    ["Home", "Products", "Reviews", "Products", "Cart"],
    ["Home", "Blog", "Home", "Products"],
    ["Home", "About"]
]

# Initialize and fit
model = MarkovPath(smoothing=1e-4)
model.fit(paths)

# Predict top 3 most likely next pages from "Products"
predictions = model.predict_next("Products", top_k=3)
print("Top next pages from 'Products':", predictions)
# -> [('Cart', 0.6666), ('Reviews', 0.3333)]

2. Inspecting Probabilities & Matrices

# Empirical State Probabilities
print("State Probabilities:")
print(model.state_probabilities)

# Transition Probability Matrix (Pandas DataFrame)
print("\nTransition Probability Matrix:")
print(model.transition_matrix)

3. Evaluating Path / Trail Probabilities

# Calculate joint trail probability
test_path = ["Home", "Products", "Cart"]
prob = model.score_path(test_path)
print(f"Path Probability: {prob:.6f}")

# Long sequences: Use log-scale to avoid underflow
log_likelihood = model.score_path(test_path, log_scale=True)
print(f"Log-Likelihood: {log_likelihood:.4f}")

# Batch scoring for multiple paths
scores = model.score_paths(paths)

4. Multi-Touch Attribution via Removal Effect

Quantify which touchpoints drive final conversions:

paths = [
    ["Facebook", "Google", "Cart"],
    ["Google", "Cart"],
    ["Organic", "Cart"],
    ["Facebook", "Organic"]
]
# 1 = converted, 0 = dropped off
conversions = [1, 1, 1, 0]

attribution_df = model.removal_effect(paths, conversions=conversions)
print(attribution_df)

Output:

    channel  removal_effect  attribution_weight  conversions_attributed
0    Google            0.60                0.40                     1.2
1  Facebook            0.50                0.33                     1.0
2   Organic            0.40                0.27                     0.8

5. Simulating User Journeys (Monte Carlo)

simulated_journey = model.simulate(
    start_state="Home",
    max_steps=10,
    stop_states={"Checkout", "About"},
    seed=42
)
print("Simulated Journey:", simulated_journey)
# -> ['Home', 'Products', 'Reviews', 'Products', 'Cart', 'Checkout']

---

📐 Mathematical Formulation

1. Markov Property

The probability of transitioning to state $S_{t+1}$ depends solely on the current state $S_t$: $$P(S_{t+1} = j \mid S_t = i, S_{t-1}, \dots, S_0) = P(S_{t+1} = j \mid S_t = i) = P_{ij}$$

2. Maximum Likelihood Transition Probability with Laplace Smoothing

$$P_{ij} = \frac{N(i \to j) + \alpha}{\sum_{k} N(i \to k) + |V| \alpha}$$ Where:

• $N(i \to j)$ is the frequency of observed transitions from $i$ to $j$.
• $|V|$ is the total number of distinct states.
• $\alpha \ge 0$ is the Laplace smoothing parameter (default 0.0).
• Guarantee: For every non-terminal state $i$, $\sum_j P_{ij} = 1.0$.

3. Path / Trail Probability (Chain Rule)

$$P(S_0, S_1, \dots, S_T) = P(S_0) \times \prod_{t=0}^{T-1} P(S_{t+1} \mid S_t)$$ In log space: $$\ln P(\text{Path}) = \ln P(S_0) + \sum_{t=0}^{T-1} \ln P(S_{t+1} \mid S_t)$$

4. Absorbing Markov Chains for Attribution

Transition matrix partitioned into transient ($Q$) and absorbing ($R$) states: $$P = \begin{bmatrix} Q & R \ 0 & I \end{bmatrix}$$ The fundamental matrix $N = (I - Q)^{-1}$ yields absorption probabilities $B = N R$. Removing state $k$ recomputes conversion rate $CR_{-k}$, giving removal effect: $$RE_k = \frac{CR_{\text{total}} - CR_{-k}}{CR_{\text{total}}}$$

---

🔄 Legacy Migration from path_nav

If you previously used path_nav.py, your existing functions are fully supported with corrected mathematics:

# Legacy procedural style (still supported via path_nav)
import path_nav as nv

state_prob = nv.state_probability(df, 'path')
df = nv.add_start_end(df, 'path', 'conversions')
trans_df = nv.transition_probability(df, 'path')
path_df = nv.path_probability(df, 'path', trans_df)

To migrate to the modern OOP API:

# Recommended modern style
from markovpath import MarkovPath

model = MarkovPath().fit(df['path'])
matrix = model.transition_matrix
predictions = model.predict_next('Cart', top_k=3)

---

📚 Academic Citations & References

If you use markovpath in academic research or production systems, please cite the foundational literature:

1. Primary Reference (Link Prediction & Trail Modeling):

   Sarukkai, R. R. (2000). Link prediction and path analysis using Markov chains. Computer Networks, 33(1–6), pp. 377–386.
   DOI: 10.1016/S1389-1286(00)00044-X

2. Web Navigation Mining Reference:

   Borges, J., & Levene, M. (2000). Data mining of user navigation patterns. Advances in Web Usage Mining and Information Retrieval (WEBKDD'99), Springer LNAI 1836, pp. 92–112.

BibTeX:

@article{sarukkai2000link,
  title={Link prediction and path analysis using Markov chains},
  author={Sarukkai, Ramesh R},
  journal={Computer Networks},
  volume={33},
  number={1-6},
  pages={377--386},
  year={2000},
  publisher={Elsevier},
  doi={10.1016/S1389-1286(00)00044-X}
}

---

🛠️ Publishing to PyPI

To build and publish this package to PyPI:

1. Install build tools:

   python3 -m pip install --upgrade build twine
   

2. Build source distribution and wheel:

   python3 -m build
   

3. Upload to PyPI:

   python3 -m twine upload dist/*
   

---

📄 License

Distributed under the MIT License. See LICENSE for details.