markov_modeling.md

# Modélisation Markovienne d'un Mélangeur DEM

## Description du projet

Ce document explique la construction d'une **matrice de transition de Markov** à partir de données de simulation DEM (Discrete Element Method).

### Objectif

Transformer les trajectoires de particules en une **chaîne de Markov discrète** où:
- La matrice $P_{ij}$ représente la probabilité qu'une particule passe de l'état $i$ à l'état $j$
- Les états sont définis par la position spatiale discrétisée (grille 5×5×5 = 125 états)

---

## 1. Fondements Mathématiques

### 1.1 Chaînes de Markov

Une **chaîne de Markov** satisfait la **propriété de Markov**:

$$P(X_{t+1} = j | X_t = i, X_{t-1} = i_{t-1}, ...) = P(X_{t+1} = j | X_t = i) = P_{ij}$$

> L'état futur ne dépend **que** de l'état présent, pas de l'historique.

### 1.2 Matrice de Transition

$$P = \begin{pmatrix} P_{11} & P_{12} & \cdots & P_{1n} \\ P_{21} & P_{22} & \cdots & P_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ P_{n1} & P_{n2} & \cdots & P_{nn} \end{pmatrix}$$

**Propriétés:**
- $P_{ij} \geq 0$ (probabilités non-négatives)
- $\sum_{j} P_{ij} = 1$ (somme par ligne = 1) → **stochasticité**

### 1.3 Formule d'Estimation de $P_{ij}$

À partir des données, on estime $P_{ij}$ par comptage empirique:

$$P_{ij} = \frac{\text{nombre de transitions } i \to j}{\text{nombre total de particules parties de } i}$$

Formulation développée:

$$P_{ij} = \frac{1}{N_i} \sum_{t=1}^{T} \sum_{p=1}^{N_p} \mathbb{1}_{s_p(t-1)=i} \cdot \mathbb{1}_{s_p(t)=j}$$

où:
- $N_i = \sum_{t} \sum_p \mathbb{1}_{s_p(t-1)=i}$ (nombre de particules dans l'état $i$)
- $s_p(t)$ = état spatial de la particule $p$ au temps $t$
- $\mathbb{1}_{condition}$ = fonction indicatrice (1 si vrai, 0 sinon)

---

## 2. Importations

```python
import polars as pl           # Lecture efficace des CSV
from huggingface_hub import HfFileSystem  # Accès fichiers distants
import torch                 # Calculs GPU (CUDA)
from tqdm import tqdm        # Barre de progression
import numpy as np            # Tableaux numériques
import matplotlib.pyplot as plt
```

| Bibliothèque | Rôle |
|-------------|------|
| **polars** | Alternative rapide à pandas pour lire les CSV |
| **huggingface_hub** | Accès stockage distant via HfFileSystem |
| **torch** | Calculs tensoriels sur GPU (CUDA) |
| **tqdm** | Barres de progression |
| **numpy** | Manipulation de tableaux |

---

## 3. Connexion au Dépôt HuggingFace

```python
fs = HfFileSystem()
folder_path = "hf://buckets/ktongue/DEM_MCM/Output Paraview"
csv_files = sorted(fs.glob(f"{folder_path}/*.csv"))
```

- `HfFileSystem()` : Interface style système de fichiers pour HuggingFace
- `fs.glob()` : Retourne les chemins matching le pattern `*.csv`
- `sorted()` : Ordonne lexicographiquement (cohérence temporelle)

---

## 4. Étape 1: Calcul des Limites Spatiales

**Objectif:** Déterminer les frontières min/max en x, y, z pour discrétiser l'espace.

```python
# Échantillonnage: 1 fichier sur 100 (limites quasi-constantes)
sample_files = csv_files[::100]

x_vals, y_vals, z_vals = [], [], []

for f in sample_files:
    with fs.open(f, "rb") as file:
        df = pl.read_csv(file)
    x_vals.extend(df["coordinates:0"].to_list())
    y_vals.extend(df["coordinates:1"].to_list())
    z_vals.extend(df["coordinates:2"].to_list())

# Calcul des min/max
xmin, xmax = min(x_vals), max(x_vals)
ymin, ymax = min(y_vals), max(y_vals)
zmin, zmax = min(z_vals), max(z_vals)

# Marge de sécurité (1mm)
margin = 0.001
xmin, xmax = xmin - margin, xmax + margin
ymin, ymax = ymin - margin, ymax + margin
zmin, zmax = zmin - margin, zmax + margin
```

**Échantillonnage `csv_files[::100]`:**
- 6000 fichiers → ~60 fichiers suffisent
- Les limites spatiales ne changent pas significativement

**Collecte des coordonnées:**
- `df["coordinates:0"]` : Sélectionne la colonne x
- `.to_list()` : Convertit en liste Python
- `.extend()` : Ajoute les éléments (plus efficace que append)

---

## 5. Étape 2: Discrétisation Spatiale

**Objectif:** Diviser l'espace 3D en grille régulière de cellules.

```python
nx, ny, nz = 5, 5, 5  # Nombre de divisions par axe
n_states = nx * ny * nz  # Total = 125 états

# Taille de chaque cellule
dx = (xmax - xmin) / nx
dy = (ymax - ymin) / ny
dz = (zmax - zmin) / nz
```

### 5.1 Formule de calcul de l'indice de cellule

Pour une coordonnée $x$:

$$i_x = \left\lfloor \frac{x - x_{min}}{\Delta x} \right\rfloor$$

Même formule pour $i_y$, $i_z$.

### 5.2 Fonction `compute_states_gpu()`

```python
def compute_states_gpu(x, y, z):
    """
    Convertit les coordonnées continues (x,y,z) en indices d'états discrets.
    
    Formule: state = ix + iy * nx + iz * nx * ny
    """
    x_tensor = torch.tensor(x, device="cuda")
    y_tensor = torch.tensor(y, device="cuda")
    z_tensor = torch.tensor(z, device="cuda")
    
    # Calcul des indices avec floor (division puis long())
    ix = ((x_tensor - xmin) / dx).long()
    iy = ((y_tensor - ymin) / dy).long()
    iz = ((z_tensor - zmin) / dz).long()
    
    # Clamp: restreint à [0, max] pour éviter out of bounds
    ix = ix.clamp(0, nx - 1)
    iy = iy.clamp(0, ny - 1)
    iz = iz.clamp(0, nz - 1)
    
    # Index linéaire (row-major order)
    return ix + iy * nx + iz * nx * ny
```

**Détail des opérations:**

1. `x_tensor - xmin` : Translation pour centrer à 0
2. `/ dx` : Normalisation par la taille de cellule
3. `.long()` : Conversion float → int (équivalent floor)
4. `.clamp(0, nx-1)` : $$\text{clamp}(ix, 0, n_x-1) = \begin{cases} 0 & \text{si } ix < 0 \\ n_x-1 & \text{si } ix \geq n_x \\ ix & \text{sinon} \end{cases}$$

**Index linéaire:**
```python
state = ix + iy * nx + iz * nx * ny
```

$$state = i_x + i_y \cdot n_x + i_z \cdot n_x \cdot n_y$$

**Exemple:** Pour nx=5, ny=5, nz=5, cellule (2, 1, 0):
$$state = 2 + 1 \cdot 5 + 0 \cdot 25 = 7$$

---

## 6. Étape 3: Initialisation des Tenseurs GPU

```python
device = torch.device("cuda" if torch.cuda.is_available() else "cpu")

# transition_counts[i,j] = nombre de transitions i → j
transition_counts = torch.zeros((n_states, n_states), dtype=torch.int64, device=device)

# state_counts[i] = nombre de particules dans l'état i
state_counts = torch.zeros(n_states, dtype=torch.int64, device=device)
```

**Explications:**
- `torch.zeros(shape)` : Crée un tensor de zéros
- `dtype=torch.int64` : Entiers 64 bits (évite overflow)
- `device=device` : Alloue sur GPU ou CPU

**Motivation int64:** 6000 timesteps × 1030 particules ≈ 6.2M transitions max.

---

## 7. Étape 4: Calcul des Transitions

```python
n_files = len(csv_files)
df_prev = None
states_prev = None

for i in tqdm(range(1, n_files), desc="Processing"):
    # Lecture du fichier courant
    with fs.open(csv_files[i], "rb") as f:
        df_curr = pl.read_csv(f)
    
    ids_curr = df_curr["Particle_ID"].to_numpy()
    
    # Calcul des états sur GPU
    states_curr = compute_states_gpu(
        df_curr["coordinates:0"].to_numpy(),
        df_curr["coordinates:1"].to_numpy(),
        df_curr["coordinates:2"].to_numpy(),
    )
    
    if df_prev is not None:
        ids_prev = df_prev["Particle_ID"].to_numpy()
        
        # Identification des particules communes
        common_ids = np.intersect1d(ids_prev, ids_curr)
        
        if len(common_ids) > 0:
            # Masques pour particules communes
            prev_idx = np.isin(ids_prev, common_ids)
            curr_idx = np.isin(ids_curr, common_ids)
            
            # États avant/après
            s_prev = states_prev[prev_idx]
            s_curr = states_curr[curr_idx]
            
            # Comptage vectorisé des transitions
            transitions = torch.stack([s_prev, s_curr], dim=1)
            unique_trans, counts = torch.unique(transitions, dim=0, return_counts=True)
            
            # Accumulation des comptages
            for j in range(len(unique_trans)):
                transition_counts[unique_trans[j, 0], unique_trans[j, 1]] += counts[j]
            
            # Comptage par état d'origine
            unique_prev, _ = torch.unique(s_prev, return_counts=True)
            for u in unique_prev:
                mask = s_prev == u
                state_counts[u] += mask.sum().item()
    
    df_prev = df_curr
    states_prev = states_curr
```

### 7.1 Identification des particules communes

```python
common_ids = np.intersect1d(ids_prev, ids_curr)
```

Où: ids commun = intersection(ids precedent, ids courant)

### 7.2 Masques booléens

```python
prev_idx = np.isin(ids_prev, common_ids)
```

Retourne True pour chaque élément de `ids_prev` qui est dans `common_ids`.

### 7.3 Comptage vectorisé

```python
transitions = torch.stack([s_prev, s_curr], dim=1)
unique_trans, counts = torch.unique(transitions, dim=0, return_counts=True)
```

**Mathématiquement:**
- `torch.stack([a, b], dim=1)` : Crée matrice `[a_i, b_i]` par ligne
- `torch.unique(..., dim=0)` : Trouve les lignes uniques
- `return_counts=True` : Compte les occurrences

**Exemple:**
```
s_prev = [0, 1, 0, 2, 1]
s_curr = [1, 1, 2, 2, 0]

transitions = [[0,1], [1,1], [0,2], [2,2], [1,0]]

unique_trans = [[0,1], [0,2], [1,0], [1,1], [2,2]]
counts =        [1,     1,     1,     1,     1]
```

### 7.4 Accumulation

```python
transition_counts[unique_trans[j, 0], unique_trans[j, 1]] += counts[j]
```

$$C[i, j] \mathrel{+=} \text{count}$$

---

## 8. Étape 5: Normalisation

```python
P = torch.zeros((n_states, n_states), dtype=torch.float64, device=device)

for i in range(n_states):
    if state_counts[i] > 0:
        P[i] = transition_counts[i].float() / state_counts[i].float()
```

### Formule de normalisation

$$P_{ij} = \frac{C[i,j]}{S[i]}$$

où C[i,j] = transition_counts[i,j] et S[i] = state_counts[i]

**Preuve de stochasticité:**

$$\sum_{j=1}^{n} P_{ij} = \frac{\sum_j C[i,j]}{S[i]} = \frac{S[i]}{S[i]} = 1$$

### Vérification

```python
row_sums = P.sum(dim=1)
visited = state_counts > 0
print(f"Somme par ligne: {row_sums[visited].min():.6f} / {row_sums[visited].max():.6f}")
```

---

## 9. Étape 6: Sauvegarde

```python
P_cpu = P.cpu().numpy()
transition_cpu = transition_counts.cpu().numpy()
state_counts_cpu = state_counts.cpu().numpy()

np.save("transition_matrix.npy", P_cpu)
np.save("transition_counts.npy", transition_cpu)
np.save("state_counts.npy", state_counts_cpu)
```

- `.cpu()` : Copie le tensor du GPU vers la mémoire CPU
- `.numpy()` : Convertit en array NumPy
- Format `.npy` : Binaire compressé, chargement rapide via `np.load()`

---

## 10. Visualisation et Analyse

### 10.1 Heatmap de la matrice

```python
plt.imshow(P_cpu, cmap='Blues')
plt.colorbar(label='P_ij')
plt.xlabel('État destination (j)')
plt.ylabel('État origine (i)')
```

**Interprétation:**
- **Diagonale forte** : Particules qui restent dans leur cellule (mélange lent)
- **Diagonale faible** : Mélange rapide
- **Structure de blocs** : Zones préférentielles

### 10.2 Distribution des probabilités

```python
P_nonzero = P_cpu[P_cpu > 0]
plt.hist(P_nonzero.flatten(), bins=50)
```

---

## 11. Propriétés Mathématiques

### 11.1 Vérifications

| Propriété | Formule | Vérification |
|-----------|---------|--------------|
| Non-négativité | $P_{ij} \geq 0$ | `np.all(P_cpu >= 0)` |
| Stochasticité | $\sum_j P_{ij} = 1$ | `np.allclose(row_sums, 1.0)` |
| Rayon spectral | $\rho(P) = 1$ | `np.linalg.eigvals(P_cpu)` |

### 11.2 Distribution Stationnaire

Un vecteur $\pi$ tel que:

$$\pi = \pi P$$

où $\pi_i$ = probabilité limite d'être dans l'état $i$.

```python
eigenvalues, eigenvectors = np.linalg.eig(P_cpu.T)
stationary_idx = np.argmin(np.abs(eigenvalues - 1.0))
pi_stationary = np.abs(eigenvectors[:, stationary_idx])
pi_stationary = pi_stationary / pi_stationary.sum()
```

---

## 12. Résumé des Formules Clés

| Concept | Formule |
|---------|---------|
| Indice cellule X | $i_x = \left\lfloor \frac{x - x_{min}}{\Delta x} \right\rfloor$ |
| Index linéaire | $state = i_x + i_y \cdot n_x + i_z \cdot n_x \cdot n_y$ |
| Transition | $P_{ij} = \frac{C[i,j]}{\sum_k C[i,k]}$ |
| Stochasticité | $\sum_j P_{ij} = 1$ |

---

## 13. Utilisations Futures

La matrice de transition peut servir à:

1. **Simulation**: Générer trajectoires avec $X_{t+1} \sim \text{Categorical}(P[X_t,])$
2. **Analyse**: Calculer temps de mélange, distributions limites
3. **Optimisation**: Améliorer la conception du mélangeur