Una catena di Markov è un modello matematico che descrive un sistema che si muove da uno stato all’altro in modo casuale, ma con una particolarità fondamentale:
La probabilità di passare a uno stato dipende solo dallo stato attuale, non da come ci sei arrivato. (Questo si chiama proprietà di Markov, o “assenza di memoria”).
Componenti di una Catena di Markov
Stati: i possibili scenari in cui il sistema può trovarsi.
Probabilità di transizione: la probabilità di passare da uno stato a un altro.
Matrice di transizione: una tabella che raccoglie tutte le probabilità di passaggio tra stati.
Esempio Semplice: Il Tempo Atmosferico
Immaginiamo un sistema con due soli stati:
Sole ☀️
Pioggia 🌧️
Supponiamo che:
Se oggi è sole, c’è il 90% di probabilità che domani sia ancora sole, e il 10% di probabilità che piova.
Se oggi è pioggia, c’è il 50% di probabilità che domani sia sole, e il 50% che piova di nuovo.
Costruiamo la matrice di transizione [math]P[/math]:
La distribuzione stazionaria di una catena di Markov è un vettore di probabilità che rimane invariato nel tempo dopo l’applicazione della matrice di transizione:
[math]\pi P = \pi[/math]
In altre parole, se il sistema parte dalla distribuzione [math]\pi[/math], allora anche dopo 1 passo, 2 passi, … e infiniti passi, le probabilità di essere in ciascuno stato non cambiano mai.
Immagina che il sistema “salti” da uno stato all’altro in modo casuale secondo certe probabilità. Dopo un po’ di tempo, il sistema si “stabilizza” su una certa distribuzione delle probabilità tra gli stati, indipendentemente da dove è partito.
🔁 Questa distribuzione stabile è proprio [math]\pi[/math]: indica la probabilità a lungo termine di trovarsi in ciascuno stato.
✅ Condizioni per l’esistenza (e unicità)
Una catena di Markov ha una distribuzione stazionaria unica se è:
Irriducibile: ogni stato è raggiungibile da ogni altro stato
Aperiodica: il sistema non rimbalza in cicli fissi
Quando queste due condizioni sono soddisfatte, la catena è detta ergodica, e garantisce che:
Una distribuzione stazionaria esiste
Ogni distribuzione iniziale [math]\pi_0[/math] converge a [math]\pi[/math] al crescere di [math]n[/math]:[math]\pi_n = \pi_0 P^n \longrightarrow \pi \quad \text{quando } n \to \infty[/math]
Come si calcola la distribuzione stazionaria
Risolvi il sistema:[math]\pi P = \pi[/math]che equivale a:[math]\pi_1 P_{11} + \pi_2 P_{21} + \cdots + \pi_n P_{n1} = \pi_1[/math][math]\pi_1 P_{12} + \pi_2 P_{22} + \cdots + \pi_n P_{n2} = \pi_2[/math]… e così via …
Aggiungi la condizione di normalizzazione:[math]\sum_i \pi_i = 1[/math]
In pratica, stai cercando il vettore proprio sinistro di [math]P[/math] associato all’autovalore 1, normalizzato in modo che la somma degli elementi sia 1.
Una catena è irriducibile se è possibile arrivare da qualunque stato a qualunque altro in un numero finito di passi.
📌 Esempio:
Se da Pioggia si può arrivare a Sole (magari dopo più di un passo), e viceversa, allora la catena è irriducibile.
🔹 Catena ergodica
Una catena è ergodica se:
È irriducibile
Non è “bloccata” in cicli deterministici (cioè è aperiodica)
💡 A cosa serve?
Se una catena è ergodica, allora:
Esiste una distribuzione stazionaria
Converge sempre a quella distribuzione a lungo termine, qualunque sia [math]\pi_0[/math]
🔹 Tempo medio di ritorno
È il numero medio di passi necessari per tornare a uno stato, partendo da quello stesso stato.
📌 Formula:
[math]\mu_i = \frac{1}{\pi_i}[/math]
Dove [math]\pi_i[/math] è la probabilità stazionaria di quello stato.
📌 Esempio:
Se a lungo termine un sistema si trova nello stato Sole il 25% delle volte ([math]\pi_i = 0.25[/math]), allora il tempo medio per ritornare a “Sole” è:
Esercizio 1 : Gestione delle Scorte con Politica di Riordino
Contesto
Un magazzino ha una capacità massima di 2 unità di un certo prodotto.
Ogni giorno:
La domanda può essere di 1 o 2 unità:
1 unità con probabilità 0.6
2 unità con probabilità 0.4
Le scorte vengono controllate all’inizio della giornata.
Se le scorte sono a 0, il magazziniere ordina 2 unità, con consegna immediata (lead time = 0).
Obiettivo
Costruire una catena di Markov per modellare l’evoluzione giornaliera delle scorte, e determinare la distribuzione stazionaria (cioè le probabilità a lungo termine di trovarsi in ciascuno stato).
1. Definizione degli Stati
Definiamo lo stato del sistema come la quantità di scorte disponibili all’inizio della giornata (prima della domanda), quindi:
[math]S = \{0, 1, 2\}[/math]
2. Politica di Riordino
Se le scorte sono 0, si ordina 2 unità, con consegna immediata.
Se le scorte sono 1 o 2, non si ordina nulla.
3. Analisi delle Transizioni
Ora analizziamo cosa accade partendo da ciascuno stato.
Stato 0: nessuna scorta
Il magazziniere ordina 2 unità.
Quindi disponibilità effettiva = 2.
Poi arriva la domanda:
Se domanda = 1 (probabilità 0.6): resta 1 unità → transizione a stato 1
Se domanda = 2 (probabilità 0.4): resta 0 unità → transizione a stato 0
Transizioni da 0:
a 0 con probabilità 0.4
a 1 con probabilità 0.6
Stato 1: una sola unità in magazzino
Nessun ordine
La domanda arriva:
Se domanda = 1 (0.6): resta 0
Se domanda = 2 (0.4): si vende solo 1 → resta comunque 0
Ora possiamo scrivere la matrice di transizione [math]P[/math], dove l’elemento [math]P_{ij}[/math] è la probabilità di passare dallo stato [math]i[/math] allo stato [math]j[/math]:
Il sistema si trova nel 62.5% dei casi ([math]\frac{5}{8}[/math]) nello stato 0 → magazzino vuoto (subito rifornito)
È nello stato 1 nel 37.5% dei casi ([math]\frac{3}{8}[/math]) → magazzino con una sola unità
Lo stato 2 non viene mai raggiunto a lungo termine
Motivo: non esiste alcuna transizione verso lo stato 2 → la catena non è irriducibile. Una volta che il sistema entra nello stato 0 o 1, non può più raggiungere lo stato 2.
Spunto Finale
Per rendere irriducibile la catena, servirebbe una politica diversa, ad esempio:
ordinare anche in stato 1
introdurre lead time casuale
modellare la quantità ordinata come parte dello stato
Esercizio 2 (Medio): Fidelizzazione clienti
Contesto: Un’azienda modella la fedeltà dei clienti come una catena di Markov con due stati:
Cliente fedele (F).
Cliente perso (P).
Ogni anno:
Un cliente fedele rimane tale con probabilità 0.8, altrimenti diventa “perso”.
Un cliente perso ritorna fedele con probabilità 0.4.
Domanda: Qual è la probabilità a lungo termine che un cliente sia fedele?
La catena è irriducibile (è possibile passare da F a P e da P a F) e ergodica (gli stati sono aperiodici). La probabilità a lungo termine che un cliente sia fedele è di circa il 66.7%. Questa informazione è cruciale per valutare l’efficacia delle strategie di fidelizzazione e per la previsione dei ricavi futuri.
Esercizio 3 – Manutenzione Industriale: Ottimizzazione delle Politiche
Contesto Operativo
Immaginiamo un impianto produttivo con un solo macchinario importante, che può trovarsi ogni giorno in uno dei tre stati seguenti:
Stato
Produttività
Costo Giornaliero
Descrizione
Ottimale (O)
100%
€0
Funziona perfettamente
Degradato (D)
70%
€500
Funziona ma va sistemato (manutenzione ordinaria)
Guasto (G)
0%
€2000
Fermato, serve una riparazione urgente
Come Cambia lo Stato del Macchinario Giorno per Giorno?
Le probabilità di passaggio da uno stato all’altro sono:
Da Ottimale (O):
Resta Ottimale: 90%
Diventa Degradato: 10%
Non può passare direttamente a Guasto.
Da Degradato (D):
Torna Ottimale: 70%
Diventa Guasto: 30%
Non può restare Degradato per due giorni consecutivi.
Da Guasto (G):
Torna sempre a Ottimale (100%) dopo la riparazione.
Modello di Markov
Questo processo può essere descritto con una catena di Markov, cioè un modello matematico in cui il prossimo stato dipende solo dallo stato attuale (non dal passato).
Gli stati sono: [math]S = \{O, D, G\}[/math]
La matrice di transizione mostra le probabilità di passaggio tra stati:
Supponiamo che, grazie a un sistema di monitoraggio migliore, si riesca a intervenire prima quando il macchinario è degradato. Questo riduce la probabilità di guasto.
Quindi l’investimento conviene se il risparmio annuo è superiore al costo.
Estensioni Possibili
MDP (Processi Decisionali di Markov): si possono inserire decisioni (es. fare o no la manutenzione) per trovare la politica migliore.
Sensibilità: si può vedere come cambiano i risultati se variano le probabilità.
Modelli più complessi: più stati, tempi variabili (Markov a tempo continuo), ecc.
Conclusioni
Questo esercizio dimostra come:
Le Catene di Markov aiutano a prevedere il comportamento di un sistema nel tempo.
Possiamo calcolare costi medi, probabilità di guasti e impatti economici.
Si possono simulare miglioramenti e capire se convengono economicamente.
Esercizio 4 (Molto Avanzato): Ottimizzazione di una politica di produzione
Contesto: Un’azienda produce un bene deperibile con domanda stocastica. Gli stati sono il livello di inventario [math]S = \{0, 1, 2\}[/math]. Azioni possibili: Produrre 0, 1, o 2 unità (costo: [math]c \cdot a[/math]). Domanda: 0 o 1 unità al giorno ([math]p = 0.5[/math]).
Costi:
Mantenimento: [math]h \cdot i[/math] (dove [math]i[/math] = livello inventario).
Stock-out: [math]b[/math] se domanda non soddisfatta.
Obiettivo: Trovare la politica di produzione ottimale (minimizzare costo medio giornaliero) usando Markov Decision Processes (MDP).
Soluzione:
Spazio degli stati e azioni:
Da ogni stato [math]i \in \{0, 1, 2\}[/math], si può scegliere un’azione [math]a \in \{0, 1, 2\}[/math] che rappresenta il numero di unità da produrre.
Funzione di costo immediato:
Il costo immediato [math]C(i, a)[/math] nello stato [math]i[/math] prendendo l’azione [math]a[/math] è dato da:
[math]C(i, a) = c \cdot a + h \cdot (i + a) + b \cdot E[\text{stock-out}][/math]
Dove l’aspettativa del costo di stock-out dipende dalla domanda e dal livello di inventario dopo la produzione ([math]i + a[/math]). Se la domanda è 1 e [math]i + a = 0[/math], si ha uno stock-out. Se la domanda è 1 e [math]i + a > 0[/math], non c’è stock-out. Se la domanda è 0, non c’è stock-out.
Dove [math]\gamma[/math] è il fattore di sconto (per il costo medio giornaliero, si considera [math]\gamma \approx 1[/math] e si cerca la differenza tra [math]V(i)[/math] per stati diversi) e [math]P_{ij}(a)[/math] è la probabilità di transizione dallo stato [math]i[/math] allo stato [math]j[/math] dopo aver intrapreso l’azione [math]a[/math] e osservato la domanda.
Le probabilità di transizione [math]P_{ij}(a)[/math] dipendono dallo stato corrente [math]i[/math], dall’azione [math]a[/math] (produzione) e dalla domanda (0 o 1 con probabilità 0.5 ciascuna). Il nuovo livello di inventario [math]j[/math] sarà [math]\max(0, i + a – d)[/math], dove [math]d[/math] è la domanda.
Per risolvere questa equazione, si possono utilizzare metodi iterativi come value iteration o policy iteration.
Commento: Questo esercizio introduce i Processi Decisionali di Markov (MDP), un’estensione delle catene di Markov che permette di modellare decisioni sequenziali ottimali in ambienti stocastici. È fondamentale per la gestione dinamica degli inventari, considerando costi di produzione, mantenimento e stock-out.
