Metadata-Version: 2.4
Name: markovpath
Version: 2.0.2
Summary: Fast, production-ready Markov Chain library for navigation path prediction, trail likelihood estimation, AI agent trajectory modeling, and attribution.
Author-email: Ishan Jain <visitishan@gmail.com>
License-Expression: MIT
Project-URL: Homepage, https://github.com/visitishan/Navigation-path-prediction-and-probability
Project-URL: Repository, https://github.com/visitishan/Navigation-path-prediction-and-probability
Project-URL: Bug Tracker, https://github.com/visitishan/Navigation-path-prediction-and-probability/issues
Keywords: markov-chain,path-prediction,clickstream,web-usage-mining,attribution-modeling,removal-effect,agent-trajectories,ai-planning,link-prediction
Classifier: Development Status :: 5 - Production/Stable
Classifier: Intended Audience :: Developers
Classifier: Intended Audience :: Science/Research
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.8
Classifier: Programming Language :: Python :: 3.9
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Topic :: Scientific/Engineering :: Artificial Intelligence
Classifier: Topic :: Scientific/Engineering :: Information Analysis
Requires-Python: >=3.8
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: numpy>=1.20.0
Requires-Dist: pandas>=1.3.0
Provides-Extra: dev
Requires-Dist: pytest>=7.0.0; extra == "dev"
Requires-Dist: twine>=4.0.0; extra == "dev"
Requires-Dist: build>=0.10.0; extra == "dev"
Dynamic: license-file

# markovpath

[![PyPI version](https://badge.fury.io/py/markovpath.svg)](https://pypi.org/project/markovpath/)
[![PyPI - Status](https://img.shields.io/badge/pypi-available-brightgreen?logo=pypi)](https://pypi.org/project/markovpath/)
[![Python Versions](https://img.shields.io/badge/python-3.8%20%7C%203.9%20%7C%203.10%20%7C%203.11%20%7C%203.12-blue?logo=python)](https://pypi.org/project/markovpath/)
[![License: MIT](https://img.shields.io/badge/License-MIT-yellow.svg)](https://opensource.org/licenses/MIT)
[![Tests](https://img.shields.io/badge/tests-10%20passed-brightgreen.svg)]()

> 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).

`markovpath` is officially published and available on [PyPI (Python Package Index)](https://pypi.org/project/markovpath/).

Rooted in peer-reviewed Web Usage Mining research ([Sarukkai, 2000](https://doi.org/10.1016/S1389-1286(00)00044-X)), `markovpath` provides a clean, vectorized, Scikit-learn-style API to model user navigation sessions, clickstreams, or AI decision traces.

<p align="center">
  <img src="https://raw.githubusercontent.com/visitishan/Navigation-path-prediction-and-probability/main/assets/markov_user_path_flow.jpg" alt="Markov Navigation Path Prediction and User Trail Flow" width="95%" />
</p>

---

## 🚀 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 & PyPI Availability

The library is officially available on **PyPI**: 👉 **[https://pypi.org/project/markovpath/](https://pypi.org/project/markovpath/)**

Install it directly via `pip`:

```bash
pip install markovpath
```

To install or upgrade to the latest release:
```bash
pip install markovpath --upgrade
```

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

---

## ⚡ Quickstart

### 1. Basic Fitting & Next-State Prediction

```python
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

```python
# 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

```python
# 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:

```python
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)

```python
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:

```python
# 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:
```python
# 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](https://doi.org/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:
```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}
}
```

---

## 📄 License

Distributed under the **MIT License**. See [LICENSE](LICENSE) for details.
