Overbooking

Il forum di Base5, dove è possibile postare problemi, quiz, indovinelli, rompicapo, enigmi e quant'altro riguardi la matematica ricreativa e oltre.

Moderatori: Gianfranco, Bruno

franco
Livello 9
Livello 9
Messaggi: 1438
Iscritto il: mar dic 12, 2006 12:57 pm
Località: Bèrghem (Sardegna)

Overbooking

Messaggio da franco »

Un ristoratore ha un locale con 20 coperti.
Un'agenzia di viaggi noleggia un aereo da 200 passeggeri.
Una società sportiva ha in gestione uno stadio con 2000 posti.

Tutti quanti hanno verificato che, in media, il 5% delle persone che prenotano un posto non si presentano il giorno dovuto e di conseguenza fanno "overbooking" accettando rispettivamente 21, 210 e 2100 prenotazioni.

Chi dei tre ha la maggiore probabilità di trovarsi nei guai con un cliente che aveva prenotato e per cui non c'è più posto?



l'originale è qui: surréservation
Franco

ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician

Daniela
Livello 6
Livello 6
Messaggi: 456
Iscritto il: lun nov 21, 2005 9:40 am

Re: Overbooking

Messaggio da Daniela »

Un problema molto bello, grazie! Bisognerebbe pero' saperne di piu' sulle distribuzioni. Altrimenti si puo' tirare soltanto a indovinare e supporre che al palazzetto dello sport rimborseranno dei biglietti :)
Daniela
"L'essenza della libertà è la matematica"

delfo52
Livello 9
Livello 9
Messaggi: 1556
Iscritto il: mer mag 25, 2005 4:19 pm
Località: bologna

Re: Overbooking

Messaggio da delfo52 »

Invece di parlare di "in media". consideriamo che la quota dei "mancati presenti" sia proprio il 5%.
Significherebbe (significa?) che nelle tre ipotesi di 21-210-2100 prenotati, gli assenti sarebbero
1,05-10,5 e 105

Ragionando in modo poco matematico, e senza sapere quanto è "larga" la distribuzione (come richiede Daniela), possiamo però dire anche solo con questi pochi dati qualche cosa.
Innanzitutto che ci deve essere per forza una "distribuzione" attorno al dato medio. non esistono infatti i "ventesimi di cliente" e i "mezzi viaggiatori".
Nel caso dei 20 coperti al ristorante, viene da supporre che la "moda" corrisponda all'assenza di 1 prenotato. Qualunque soluzione in cui i mancanti siano di più, ci va bene. Dobbiamo preoccuparci solo dei casi in cui il numero degli assenti sia zero.
Considerando che i casi di assenti plurimi, anche se pochi, contribuiscono ad alzare assai la media, e considerando che i numerosi casi di "1 assente" già si posizionano più in basso della media, ne deduciamo(?) che i casi di zero assenti saranno pochini.
Non è difficile calcolarne la probabilità: basta moltiplicare 20/21 per sè stesso 21 volte.
Nel caso dei 210 posti, la media è di 10,5 assenti. Tali in modo preciso non saranno mai, ma pobssamo aspettarci un buon numero di casi in cui gli assenti saranno 10 o 11 (con una qual forzatura, potremmo parlare di doppia moda). Poi avremo, sempre più rari, i casi che si discostano. Se si discostano in più, nessun problema, ma basta che il loro numero sia di una sola unità inferiore alla moda (impropria), e...casca l'asino.
Con numeri più grandi (2100 iscritti), ci aspettiamo 105 assenti (moda ?). In questo caso possiamo tollerare, almeno in termini assoluti, un discreto margine di oscillazione sia in eccesso (che non ci interessa nè impressiona) sia in difetto.
Concludendo, pur senza alcuna motivazione strettamente matematica, mi sento indotto a considerare più probabile che l'overbooking provochi più problemi nella simulazione intermedia
Enrico

Pasquale
Livello 12
Livello 12
Messaggi: 2853
Iscritto il: mer mag 25, 2005 2:14 am

Re: Overbooking

Messaggio da Pasquale »

Potrei ragionare in quest'altro modo:


in media il 5% non si presenta, ma supponiamo che la forbice sia larga abbastanza e tale per cui nel caso specifico sia l'1% quello che non si presenta.
In tale caso, per le tre attività elencate, avremo la seguente situazione, ammettendo che si debba arrotondare sempre all'intero:

21-1%=20,79, cioè 1 in più rispetto ai posti disponibili, pari al 5% in più
210-1%=207,9, cioè 8 in più, pari al 4% in più
2100-1%=2079, cioè 79 in più, pari al 3,95% in più

Nel caso descritto, grazie all'arrotondamento, il primo sarebbe quello più svantaggiato.


Se venisse rispettato il 5%, sempre arrotondando all'intero:

21-5%=19,95, cioè nessun posto in più da occupare, 0% in meno
210-5%=199,5, cioè nessun posto in più da occupare, 0% in meno
2100-5%=1995, 5 posti in meno,pari allo 0,25% in meno

corrono più rischio le prime due attività, ma la prima di più



Se invece non si presentasse il 9%:

21-9%=19,11, cioè 1 in meno rispetto ai posti disponibili, pari al 5% in meno
210-9%=191,1 , cioè 9 in meno, pari al 4,5%
2100-9%=1911, cioè 89 in meno, pari al 4,45% in meno

in questo caso, sarebbe più a rischio la terza attività.

In definitiva sarei portato a pensare che corre più rischi la prima attività.

Una simulazione al computer, sempre con arrotondamenti all'unità delle frazioni, conduce alla stessa conclusione:


randomize
FOR m=1 TO 1000000 !'calcolo posti in esubero 1^ attività
LET x=1+INT(RND*9)
LET a=20-(21-INT(21*x/100))
LET esua=esua+a
NEXT M

FOR m=1 TO 1000000 !'calcolo posti in esubero 2^ attività
LET x=1+INT(RND*9)
LET b=200-(210-INT(210*x/100))
LET esub=esub+b
NEXT M

FOR m=1 TO 1000000 !'calcolo posti in esubero 3^ attività
LET x=1+INT(RND*9)
LET c=2000-(2100-INT(2100*x/100) )
LET esuc=esuc+c
NEXT M

PRINT "esubero medio posti nella 1^ attività -> ";esua/1000000
PRINT "esubero medio posti nella 2^ attività -> ";esub/1000000
PRINT "esubero medio posti nella 3^ attività -> ";esuc/1000000

Comunque, nella simulazione senza arrotondamento (togliere INT dal codice), la prima attività resta egualmente più a rischio.
_________________

$\text { }$ciao Immagine ciao
E' la somma che fa il totale (Totò)

delfo52
Livello 9
Livello 9
Messaggi: 1556
Iscritto il: mer mag 25, 2005 4:19 pm
Località: bologna

Re: Overbooking

Messaggio da delfo52 »

il"bello" del poroblema sta , a mio parere, proprio nel fatto che, simulazioni a parte, non si possono considerare le "frazioni di persone" e anche l'arrotondamento è una finzione rozza e grossolana. Bisognerebbe, in ogni caso, arrotondare (per forza), ma avolte per eccesso e a volte per difetto, in modo tale da ottenere il risultato medio che abbiamo calcolato, e che dobbiamo mantenere.
Enrico

Pasquale
Livello 12
Livello 12
Messaggi: 2853
Iscritto il: mer mag 25, 2005 2:14 am

Re: Overbooking

Messaggio da Pasquale »

Si Delfo, poi è tutta una questione sul come vengono utilizzati i dati ed impostato un ragionamento (a parte eventuali errori banali ed evidenti).
A seguito dei due interventi precedenti (quello di Daniela e il tuo) mi sono soffermato sulla questione e mi sono convinto di dover procedere con gli arrotondamenti, anche perché mi sembrava che in modo diverso la probabilità cercata fosse la stessa per tutti i tre casi.
Restava comunque il dato medio del 5% da interpretare.
Per me derivava da uno studio statistico, in base al quale si possono prendere più prenotazioni, tanto poi il 5% "in media" non si presenta.
Il 5% è il dato statistico osservato su una serie di eventi significativa, a volte a favore , a volte a sfavore dell'azienda, tale che nel lungo periodo risulta come se si fosse fatto sempre il pieno dei posti disponibili.
Io ho considerato che il 5% è la media fra tutti i valori casualmente distribuiti fra 1 e 9: solo l'1% non si presenta (c'è gente in esubero); il 9% non si presenta, restano posti non occupati.
In sostanza non ho considerato il 5% come obbligo, ma come risultato nel tempo; comunque nei diversi casi fra l'1% ed il 9%, automaticamente gli arrotondamenti non sono sempre della stessa natura (come tu auspicavi).
Operando gli arrotondamenti, si generano squilibri fra le tre diverse situazioni, nei diversi casi, ed ho pensato che fosse necessario farli.
Quando sono passato alle simulazioni con 1.000.000 di reiterazioni, a titolo di controllo dei risultati, ho trovato che il rischio percentuale pendeva verso la prima azienda (quella con 20 posti), ma quando ho tolto l'arrotondamento mi sono meravigliato nel trovare lo stesso risultato, in base al quale,in media, nel lungo periodo, tutte le aziende, ogni volta fanno il pieno preciso (quasi) e nessun cliente resta fregato.

Ho effettuato nuove simulazioni, riducendo la forbice fra 4% e 6% e la tendenza non cambia.
Imponendo invece sempre il 5% fisso, con gli arrotondamenti, restano 0 posti per la prima e seconda attività e 5 per la terza; senza arrotondamenti, per la prima attività restano 0,05 posti liberi (quindi 0);
per la seconda 0,5 (quindi 0); per la terza sempre 5.
Dunque diventerebbero 2 le aziende a rischio.
_________________

$\text { }$ciao Immagine ciao
E' la somma che fa il totale (Totò)

infinito
Livello 5
Livello 5
Messaggi: 339
Iscritto il: mer mag 25, 2005 5:02 pm

Re: Overbooking

Messaggio da infinito »

Devo dire che ho capito poco delle interpretazioni di Delfo e di Pasquale (e sì: si invecchia).
Però mi sembra che si diano per scontate condizioni che non capisco
(per esempio credo che questo sia il motivo per cui Delfo ha detto che «Non è difficile calcolarne la probabilità: basta moltiplicare 20/21 per sé stesso 21 volte»).

A me sembra abbastanza chiara una cosa: in mancanza di informazioni specifiche è “naturale” (cioè anche “corretto”, “conforme alla mia visione della realtà, salvo casi molto particolari”) considerare che la gente che non si presenta lo faccia con una certa casualità,

come dire che, nonostante ogni volta chiunque possa essere presente o assente, in generale il numero totale di presenti e di assenti segue la distribuzione gaussiana, e in particolare è “abbastanza vicino a quello medio (nella fattispecie al 95% e al 5% del totale).

Comunque è chiaro che in pratica, differentemente da quanto appena detto, è falso che la probabilità di essere presente o assente per una persona è indipendente dal fatto che gli altri siano presenti o assenti (per esempio potrebbe essere che i clienti dell'agenzia viaggi disdicono una prenotazione all'estero principalmente per motivi di non sicurezza nel paese dove deve andare, il che implicherebbe che gli assenti o sono pochissimi o sono tantissimi).

Noi qui consideriamo che le il comportamento dei singoli individui sia indipendente, cioè casuale.




Invece, fissata una popolazione, se la gente fosse presente o assente “in blocchi” di più individui (invece che in singoli individui), allora “in media” il numero di presenti ed assenti discosterebbe maggiormente dalla media .
(Cerco di chiarire intuitivamente questo concetto: il dato reale si avvicina alla media se le varie discordanze si compensano, come dire che se uno fa eccedere il totale un altro (o “altri”) si comportano in modo “opposto” e compensano; è quindi intuitivo che se più individui si comportano nello stesso identico modo (perché fanno parte dello stesso gruppo) si ostacola questo fenomeno di compensazione.)

Considerando ovvio quanto sopra, ne segue che , partendo dal caso di 2000 persone (società sportiva), il caso di 200 persone (agenzia viaggi) è analogo, ma dove ad ogni persona del secondo corrisponde un gruppo di 10 persone del primo che sono presenti o assenti contemporaneamente;
e il caso di 20 persone (locale del ristoratore) è ancora analogo, ma qui ad ogni persona corrispondono un gruppo di 10 persone del secondo e uno di 100 persone del primo.

Non so se sono stato abbastanza chiaro, ma mi pare evidente che quanto più è grande il numero di persone, tanto più la probabilità sarà vicina al valore medio teorico, e quanto più è piccolo il numero, tanto più saranno numerose le volte in cui la differenza fra tali valori supererà qualunque valore percentuale previsto (in questo caso l' 1% in più).




Resta da valutare se il comportamento dei singoli individui è davvero casuale, io sarei portato a pensare che nei tre è proprio quello del ristorante, dove spesso non ci si va come singoli, ma come famiglie, gruppi, ecc., a volte anche di 21 persone. In questo caso è chiaro che non è infrequente che disdica tutto il gruppo, il che porterebbe inevitabilmente a “penalizzare” ulteriormente il padrone del ristorante.


Conclusione: «la maggiore probabilità di trovarsi nei guai con un cliente che aveva prenotato e per cui non c'è più posto» la ha “sicuramente” il ristoratore.
Gaspero

delfo52
Livello 9
Livello 9
Messaggi: 1556
Iscritto il: mer mag 25, 2005 4:19 pm
Località: bologna

Re: Overbooking

Messaggio da delfo52 »

Gaspero ha spiegato proprio quello che intendevo io.
Dal momento che, per restare nel caso da 20, il dato osservato può discostarsi dal valore atteso solo di una unità, mentre nel versante "assenti maggiori della media" il dato può eccedere la media anche di 2, 3, 4... ne consegue che, per mantenere la media dove deve stare, i casi di "un solo presente più del previsto" saranno alquanto numerosi. Con dispiacere del ristoratore, a cui potremmo consigliare di "overbookare" più largamente.
Enrico

franco
Livello 9
Livello 9
Messaggi: 1438
Iscritto il: mar dic 12, 2006 12:57 pm
Località: Bèrghem (Sardegna)

Re: Overbooking

Messaggio da franco »

Ho provato a lavorare anch’io su questo quesito, in maniera totalmente indipendente dalle considerazioni di Enrico, Pasquale e Gaspero.
In verità poi ci sarebbe anche la possibilità di sbirciare la soluzione nel sito Francese (ormai siamo a dicembre) ma resisto alla tentazione.

Ho cambiato, a mio rischio e pericolo, i termini del problema ipotizzando che “ogni persona che ha prenotato il posto abbia il 5% di probabilità di dare buca”.
Credo (non sono un esperto) che non sia la stessa cosa rispetto al dire che “il 5% dei prenotati non si presenta”, però in questo modo sono riuscito ad approcciare il problema che altrimenti mi sembrava troppo vago.
A questo punto provo a generalizzare il problema:
p = probabilità d’assenza del singolo prenotato = 0,05
A = numero dei posti disponibili
B = numero delle prenotazioni accettate
C = A-B = numero minimo di assenze per evitare il fenomeno dell’overbooking
In generale, la probabilità che vi siano n assenti e B-n presenti è data da:
$$$ P_n = \left( {\matrix{ B \cr n \cr } } \right)p^n \left( {1 - p} \right)^{B - n} $$$
L’overbooking si verifica in tutti i casi in cui N<C
$$$ P_{n < C} = \sum\limits_{n = 0}^{C - 1} {\left( {\matrix{ B \cr n \cr } } \right)p^n \left( {1 - p} \right)^{B - n} } $$$
Forte di questa formula vado quindi ai casi del problema.
Per il ristorante è semplice: B=21, C=1. L’overbooking si verifica solo quando si presentano tutti i prenotati e questo evento ha una probabilità che si poteva calcolare anche molto più semplicemente:
$$$ P_{n < 1} = \left( {1 - p} \right)^{21} = 34,06\% $$$
Per l’aereo B=210, C=10. Abbiamo overbooking quando:
$$$ P_{n < 10} = \sum\limits_{n = 0}^9 {\left( {\matrix{ {210} \cr n \cr } } \right)p^n \left( {1 - p} \right)^{210 - n} } = 39,26\% $$$
Per lo stadio B=2100, C=100. Abbiamo overbooking quando:
$$$ P_{n < 100} = \sum\limits_{n = 0}^{99} {\left( {\matrix{ {2100} \cr n \cr } } \right)p^n \left( {1 - p} \right)^{2100 - n} } = 29,45\% $$$

Incredibilmente (per me) il caso più a rischio è quello intermedio.

Se avessi dovuto dare un giudizio senza fare calcoli era l’unico che avrei escluso “a priori”!

ciao
Franco

ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician

Pasquale
Livello 12
Livello 12
Messaggi: 2853
Iscritto il: mer mag 25, 2005 2:14 am

Re: Overbooking

Messaggio da Pasquale »

Strano...un calcolo che conferma quanto anticipato da Delfo nel suo primo intervento.
_________________

$\text { }$ciao Immagine ciao
E' la somma che fa il totale (Totò)

delfo52
Livello 9
Livello 9
Messaggi: 1556
Iscritto il: mer mag 25, 2005 4:19 pm
Località: bologna

Re: Overbooking

Messaggio da delfo52 »

Mai escludere a priori che la matematica "un tanto al chilo" possa dare risultati corretti... :P :lol: :P :D
Enrico

franco
Livello 9
Livello 9
Messaggi: 1438
Iscritto il: mar dic 12, 2006 12:57 pm
Località: Bèrghem (Sardegna)

Re: Overbooking

Messaggio da franco »

Ho provato a fare anche altri casi, mantenendo fisso il 5% di prenotazioni accettate in più rispetto ai posti disponibili.
Per avere numeri interi ho considerato i posti disponibili a multipli di 20.

Il risultato, sempre considerando che ogni persona prenotata abbia il 5% di probabilità di non presentarsi, è rappresentato da questo grafico:

Immagine
In ascisse i posti disponibili e in ordinate la probabilità che si presentino più persone dei posti a disposizione.

Il massimo della curva corrisponde a 140 posti disponibili (e 147 prenotati).

ciao
Franco

ENGINEER
noun. (en-juh-neer)
someone who does precision guesswork based on unreliable data provided by those of questionable knowledge.
See also wizard, magician

Pasquale
Livello 12
Livello 12
Messaggi: 2853
Iscritto il: mer mag 25, 2005 2:14 am

Re: Overbooking

Messaggio da Pasquale »

Scusa Franco, un ultimo dubbio:

il testo iniziale del quesito dice : "in media, il 5% delle persone che prenotano un posto non si presentano"; adesso dici: "sempre considerando che ogni persona prenotata abbia il 5% di probabilità di non presentarsi".

Le due frasi, da un punto di vista matematico, si equivalgono?
_________________

$\text { }$ciao Immagine ciao
E' la somma che fa il totale (Totò)

delfo52
Livello 9
Livello 9
Messaggi: 1556
Iscritto il: mer mag 25, 2005 4:19 pm
Località: bologna

Re: Overbooking

Messaggio da delfo52 »

dal punto di vista matematico, nn lo so.
Certamente differiscono a livello logico.
Da una parte si discute del tasso di assenza dei singoli, che andrà sommato (anzi moltiplicato) per la numerosiyà del campione.
La lettura "letterale" del testo, fa invece riferimento al tasso di assenza media registrato. Un dato misurato a livello "cumulativo". In pratica io ho letto il testo come se dicesse.
"il padrone di un ristorante ha preso ogni giorno un numero x di prenotazioni, e ha constatato ogni sera ill tasso di presenze. Tale valore risulta (dopo un ragionevole e significativo numero di giorni) mediamente del 95%
Con ciò che ne consegue; inclusa la necessità che la distribuzione dei valori non può essere espressa da una curva continua, ma solo da valori interi. Mi sembra peraltro che questa "difficoltà" sia rilevante solo per il campione più piccolo.
Enrico

panurgo
Livello 9
Livello 9
Messaggi: 1521
Iscritto il: sab nov 19, 2005 3:45 pm
Località: Padova

Re: Overbooking

Messaggio da panurgo »

Voglio aggiungere anch’io il mio contributo alla soluzione di questo problema, nel quale ci troviamo assai a corto di informazioni ma non abbastanza.

In situazioni come questa viene del tutto naturale fare affidamento sull’intuito e sull’esperienza per creare uno o più scenari che diano un senso all’affermazione “il 5% delle persone che prenotano un posto non si presentano”.
Salta subito all’occhio che la somiglianza tra i tre casi è abbastanza superficiale: non si va al ristorante come si va in aereo. Persone diverse hanno esigenze diverse: possiamo facilmente immaginare qualcuno che, per non rimanere a piedi, prenoti il posto sull’aereo anche se non è sicuro di poter o dover partire; oppure, se il membro di una coppia non si può più recare al ristorante è naturale che anche l’altro non possa.
Ancora! Indichiamo con $n_{\script 0}$ il numero di posti disponibili, con $n$ il numero di posti prenotati, con $k$ il numero di persone che non si presentano e con $\alpha$ la frazione $k/n$: sicuramente la verifica è stata effettuata a partire da distribuzioni statistiche nella forma $\left\{k_{\script i},\/n_{\script i}\right\}$ per $1\/\leq\/i\/\leq\/N$ che contengono molte informazioni in più. Come, per esempio, $\overline{n}$ e se $\overline{n}\/\ll\/\left(1\/-\/\alpha\right)\/n_{\script 0}$, cioè se il numero di prenotazioni è quasi sempre inferiore ai posti disponibili, il problema dell’overbooking neanche si pone.
Ma, attenzione: non conosciamo $\left\{k_{\script i},\/n_{\script i}\right\}$! Non conosciamo $N$! Non sappiamo neppure se $\alpha\/=\/\overline{k/n}$ oppure $\alpha\/=\/\overline{k}/\overline{n}$. Ehi, chi vi ha autorizzato a introdurre nuovi dati nel problema?

Mi spiego: se vi dicessi

“dato un cerchio di diametro $\overline{\text BC}$ si scelga il punto $\text A$ a caso sulla circonferenza e si dimostri che la probabilità che il triangolo ${\text ABC}$ sia ottusangolo è pari a quella che sia acutangolo”

voi potreste tranquillamente utilizzare il fatto che ${\text ABC}$ è rettangolo per costruzione per dimostrare che $p\left({\text ottus.}\/\middle|\/I\right)\/=\/p\left({\text acut.}\/\middle|\/I\right)\/=\/0$ perchè si tratta di una proprietà geometrica che stava già lì, nascosta nella formulazione del problema, e non di un nuovo dato.
Viceversa le ipotesi su $\left\{k_{\script i},\/n_{\script i}\right\}$ sono nuovi dati che non possono essere introdotti senza modificare il problema: il nostro compito è quello di assegnare una distribuzione $p\left(k\/\middle|\/n\/\alpha\/I\right)$ in base ai dati che sono in nostro possesso.

Quindi cominciamo col non considerare affatto $\alpha$, l’expectation che la distribuzione deve avere.

Facciamo questo perché tutte le ipotesi viste sopra (e le infinite altre, più o meno plausibili, che si possono fare) nascono dal fatto che noi sappiamo qualcosa, abbiamo un dato. Se lasciamo perdere tale dato dobbiamo ammettere di non saper nulla; a parte le cose che sono già dentro la formulazione del problema: cioè che sono disponibili $n_{\script 0}$ posti e che ne vengono prenotati $n$.
Supponiamo che $k$ persone non si presentino: che valori potrà assumere $k$? Evidentemente tutti i valori tra $0$ e $n$; vediamo che distribuzione $m\left(k\/\middle|\/n\/I\right)$ si adatta meglio a rappresentare la situazione.
Assegnamo una probabilità all’ipotesi che le persone che mancano siano quelle ai posti $1,\/2,...,\/k$: se qualcuno ci dicesse che la persona mancante del posto $1$ dovrebbe, in realtà, essere seduta al posto $n$ questo ci farebbe cambiare la probabilità che abbiamo assegnata? Evidentemente, se ne sappiamo così poco, il posto da cui una persona manca non può influenzare le nostre previsioni. Questo implica che l’unica cosa sensata sia assegnare una distribuzione di probabilità uniforme non sugli $n\/+\/1$ possibili valori di $k$ ma sui $2^{\script n}$ modi in cui possono essere combinati, quindi

$m\left(k\/\middle|\/n\/I\right)\/=\/{n \choose k}\/\frac 1{2^{\script n}}$

Osserviamo che non si è assunto che ciascuna persona abbia indipendentemente una probabilità di non presentarsi pari a $1/2$: la distribuzione binomiale si impone per motivi puramente combinatori ed è la più dispersa possibile.
Questa distribuzione di massima ignoranza è una sorta di misura dello spazio di campionamento, onde il nome $m\left(k\/\middle|\/n\/I\right)$, e come tale è indipendente anche dalle ipotesi che possono farsi per distinguere i tre casi.

All’improvviso ci ricordiamo che un dato, $\alpha$, lo abbiamo: come facciamo per trovare una distribuzione la più dispersa possibile ma con expectation

$\left\langle k\right\rangle\/=\/\sum_{\script k=0}^{\script n}k\/p\left(k\/\middle|\/n\/\alpha\/I\right)\/=\/\alpha\/n$

Nella nostra cassetta degli attrezzi abbiamo lo strumento giusto: Claude Shannon nel 1948 e Edwin Jaynes nel 1957 hanno posto le basi del metodo MAXENT.
La distribuzione che cerchiamo è quella che massimizza l’entropia di Jaynes-Shannon, altrimenti detta divergenza di Kullback-Leibler

$S\/=\/-\/\sum_{\script k=0}^{\script n}p\left(k\/\middle|\/n\/\alpha\/I\right)\,\log\frac{p\left(k\/\middle|\/n\/\alpha\/I\right)} {m\left(k\/\middle|\/n\/\alpha\/I\right)}$

soggetta ai vincoli

$\sum_{\script k=0}^{\script n}p\left(k\/\middle|\/n\/\alpha\/I\right)\/=\/1$

e

$\sum_{\script k=0}^{\script n}k\/p\left(k\/\middle|\/n\/\alpha\/I\right)\/=\/\alpha\/n$

Osserviamo innanzitutto che la conoscenza di $\alpha$ non altera la “metrica” dello spazio di campionamento, cioè la distribuzione che assegnamo se decidiamo di ignorare $\alpha$ stesso, quindi

$m\left(k\/\middle|\/n\/\alpha\/I\right)\/=\/m\left(k\/\middle|\/n\/I\right)\/\propto\/{n \choose k}$

La massimizzazione viene effettuata con il metodo dei moltiplicatori di Lagrange e la funzione da massimizzare è

$Q\/=\/-\/\sum_{\script k=0}^{\script n}p_{\script k}\/\log\frac{p_{\script k}}{m_{\script k}}\/+\/\lambda_{\script 0}\left(1\/-\/\sum_{\script k=0}^{\script n}p_{\script k}\right)\/+\/\lambda\left(\alpha\/n\/-\/\sum_{\script k=0}^{\script n}k\/p_{\script k}\right)$

Deriviamo rispetto a $p_{\script k}$ e uguagliamo a $0$

$\frac {dQ}{dp_{\script k}}\/=\/-\/\log\frac{p_{\script k}}{m_{\script k}}\/-\/1\/-\/\lambda_{\script 0}\/-\/\lambda\/k\/=\/0$

ottenendo

$p\left(k\/\middle|\/n\/\alpha\/I\right)\/\propto\/m\left(k\/\middle|\/n\/\alpha\/I\right)\/e^{\script -\left(1+\lambda_{\tiny 0}\right)}\/e^{\script -\lambda k}$

cioè, dato che $\exp\left\{-\left(1\/+\/\lambda_{\script 0}\right)\right\}\/=\/{\text cost.}$

$p\left(k\/\middle|\/n\/\alpha\/I\right)\/=\/\frac 1 {Z\left(\lambda\right)}\/{n \choose k}\/e^{\script -\lambda k}$

dove $Z\left(\lambda\right)$, la funzione di partizione, vale

$Z\left(\lambda\right)\/=\/\sum_{\script k=0}^{\script n} {n \choose k}\/e^{\script -\lambda k}\/=\/\left(1\/+\/e^{\script -\lambda}\right)^{\script n}$

per il teorema binomiale. Per trovare il valore di $\lambda$ si utilizza il vincolo sull’expectation

$\sum_{\script k=0}^{\script n}k\/p\left(k\/\middle|\/n\/\alpha\/I\right)\/=\/\alpha\/n$

A questo punto è utile sapere che, nel formalismo del MAXENT, abbiamo

$-\frac d {d \lambda}\log Z\left(\lambda\right)\/=\/\alpha\/n$

e quindi

$\frac{e^{\script -\lambda}}{1\/+\/e^{\script -\lambda}}\/=\/\alpha\qquad\Longrightarrow\qquad e^{\script -\lambda}\/=\/\frac \alpha {1\/-\/\alpha}$

Sostituendo questo valore nell'espressione della $p_{\script k}$ otteniamo con facile algebra la distribuzione binomiale

$p\left(k\/\middle|\/n\/\alpha\/I\right)\/=\/{n \choose k}\/\alpha^{\script k}\/\left(1\/-\/\alpha\right)^{\script n-k}$

Ancora una volta vi prego di notare che non è stata fatta alcuna assunzione di indipendenza: i dati in nostro possesso non indicano correlazioni quindi la distribuzione MAXENT non le contiene. Notate anche che una distribuzione con correlazioni è in generale più concentrata di una analoga ma senza correlazioni quindi assegnare una distribuzione correlata ci avrebbe fornito un risultato dotato di una minore dispersione, una precisione non supportata dai dati.
Notate inoltre che la distribuzione $p\left(k\/\middle|\/n\/\alpha\/I\right)$ non ha nulla in comune con la distribuzione $\left\{k_{\script i},\/n_{\script i}\right\}$, a parte l'expectation, $\alpha$: è una distribuzione che non rappresenta dati oggettivi ma solamente ciò che onestamente si può dire data la struttura del problema e $\alpha$. Essa è il punto di partenza per incorporare nuovi dati, mediante il teorema di Bayes, mano a mano che vengono raccolti (ad ogni pasto, viaggio o partita).

Cosa sarebbe successo se avessimo assegnato una distribuzione uniforme su $k$ come distrbuzione di “massima ignoranza”? Formalmente, la soluzione è uguale con

$q\left(k\/\middle|\/n\/\alpha\/I\right)\/\propto\/m^{\script \prime}\left(k\/\middle|\/n\/\alpha\/I\right)\/e^{\script -\left(1+\lambda_{\tiny 0}\right)}\/e^{\script -\lambda k}$

ma ora è $m^{\script \prime}\left(k\/\middle|\/n\/\alpha\/I\right)\/\exp\left\{ -\left(1+\lambda_{\script 0}\right)\right\}\/=\/{\text cost.}$ quindi

$q\left(k\/\middle|\/n\/\alpha\/I\right)\/=\/\frac 1 {Z\left(\lambda\right)}\/e^{\script -\lambda k}$

con

$Z\left(\lambda\right)\/=\/\sum_{\script k=0}^{\script n}\/e^{\script -\lambda k}\/=\/\frac{1\/-\/e^{\script -\lambda\left(n+1\right)}}{1\/-\/e^{\script -\lambda}}$

e

$-\frac d {d \lambda}\log Z\left(\lambda\right)\/=\/\frac{1\/-\/e^{\script -\lambda}}{1\/-\/e^{\script -\lambda\left(n+1\right)}}\/\times\/\frac{n\/ e^{\script -\lambda\left(n+2\right)}\/-\/ \left(n+1\right)\/e^{\script -\lambda\left(n+1\right)}\/+\/e^{\script -\lambda}}{\left(1\/-\/ e^{\script -\lambda}\right)^{\script 2}}\/=\/\alpha\/n$

Per semplicità poniamo $\exp\left\{-\/\lambda\right\}\/=\/q$ ottenendo

$\frac{n\/q^{\script n+2}\/-\left(n\/+\/1\right)\/q^{\script n+1}\/+\/q}{\left(1\/-\/q\right)\/\left(1\/-\/q^{\script n+1}\right)}\/=\/\alpha\/n$

questo è un polinomio in $q$ i cui zeri possono essere trovati per via numerica. Tuttavia, perchè l’expectation di una distribuzione esponenziale troncata sia inferiore a metà del range è necessario che sia $q\/<\/1$ e allora, con ottima approssimazione, $q^{\script n}\/\ll\/1$ e l’espressione può essere semplificata

$\frac{\cancel{n\/q^{\script n+2}\/-\left(n\/+\/1\right)\/q^{\script n+1}}\/+\/q}{\left(1\/-\/q\right)\/\cancel{\left(1\/-\/q^{\script n+1}\right)}}\/\approx\/\frac q{1\/-\/q}\/\approx\/\alpha\/n\qquad\Longrightarrow\qquad q\/\approx\/\frac{\alpha\/n}{\alpha\/n\/+\/1}$

L’approssimazione è così buona che, sostituendo il valore di $q$, per $n\/=\/1$ l’espressione differisce da $\alpha\/n$ di meno del $2%$.

La distribuzione esponenziale concentra la probabilità ad un estremo mentre la distribuzione binomiale la concentra intorno all’expextation

Immagine

Secondo il primo modello, al crescere di $n$ dovrebbero esservi sempre meno persone assenti (in proporzione) mentre per il secondo il numero degli assenti tende a stabilizzarsi su $\alpha\/n$: ciò si adegua meglio alla nostra intuizione che un campione composto di un gran numero di persone si avvicina statisticamente alla popolazione da cui proviene, per la quale ha senso parlare di “medie” (se raduniamo molte persone è facile che troviamo qualcuno che sia alto un metro e ottantacinque o che sia nato di mercoledì delle ceneri o che abbia gli occhi marroni ecc.).

Concludo dicendo che la pratica dell’overbooking è una cosa seria, dai viaggi aerei alla gestione del network computing (la “nuvola”), e che le varie cose su cui ho buttato l’occhio, sebbene utilizzino distribuzioni complesse, partono sempre dalla nostra umile binomiale.
il panurgo

Principio di Relatività: $\mathbb{m} \not \to \mathbb{M} \, \Longleftrightarrow \, \mathbb{M} \not \to \mathbb{m}$
"Se la montagna non va a Maometto, Maometto NON va alla montagna"

Rispondi