Tre numeri a caso

ResearchBlogging.org

Nel post precedente ho enunciato quello che sembra un problemino abbastanza semplice. Talmente semplice che non è che uno ci stia a pensare più di tanto, perché la soluzione sembra ultrabanale. Ecco il problema:

Estrarre tre numeri reali positivi a caso in modo che la loro somma sia pari a 1. Fare in modo che le triplette di numeri siano distribuite uniformemente, ovvero ognuna delle possibili triplette deve avere la stessa densità di probabilità di essere estratta a caso.

Sembra talmente semplice che di solito uno applica un metodo molto intuitivo e semplice senza stare a pensarci più di tanto:

Si estraggono a caso tre numeri reali positivi tra 0 e 1, siano x1, x2 e x3, con densità di probabilità uniforme (ovvero ogni possibile reale tra 0 e 1 ha la stessa probabilità di uscire). Quindi si sommano, sia s=x1+x2+x3. I tre numeri cercati sono U1=x1/s, U2=x2/s, U3=x3/s.

Semplice ed intuitivo. Peccato che sia sbagliato: facendo così, certe triplette vengono fuori più frequentemente di altre. Come è possibile? E’ quello che si sono chiesti i miei colleghi e co-autori Enrico e Giorgio nel paper citato in fondo a questo post.

Il problema si presenta spesso nelle nostre ricerche: ci occupiamo di algoritmi per la schedulazione dei processi in sistemi in tempo reale, e spesso dobbiamo misurare e comparare le loro performance. Per fare queste comparazioni si generano a caso dei processi e si cerca di applicare un test di schedulabilità per ogni algoritmo. Spesso, il parametro più importante di un processo per noi è il carico di lavoro che impone sulla CPU. Il carico si esprime come una percentuale, quindi un numero reale tra 0 e 1. Inoltre, una CPU non puà essere caricata per più del 100%, per cui ecco che salta fuori il problema: dobbiamo generare a caso 3 (o più) numeri, uno per ogni processore, in modo che la loro somma sia un valore predeterminato e fisso non superiore a uno. Per semplicità, assumiamo qui che tale valore deve essere esattamente pari a 1.

Enrico stava appunto cercando di rifare degli esperimenti comparativi fra i due algoritmi più famosi: Fixed Priority e Earliest Deadine First, e guardando i lavori in letteratura si accorse che tutti utilizzavano il metodo di cui sopra. Al mio amico venne il sospetto che tale metodo non fosse “fair”, cioè tendesse a favorire uno dei due algoritmi contendendi. Per cui si mise a studiare il problema. Per prima cosa, generò un buon numero di triplette con il metodo della normalizzazione. Tali numeri si possono graficare in 3D, e vanno tutti a finire su un triangolo che ha i sui vertici nei punti (1,0,0), (0,1,0), (0,0,1). Ecco il triangolo che venne fuori:

Come vedete con questo metodo i punti tendono a finire più spesso verso il centro del triangolo. Come mai? C’è una spiegazione geometrica semplice: Guardate la seguente sezione in 2D (cioè, cosa succederebbe se i numeri da estrarre fossero solo 2):

I punti x1 e x2 generati a caso tra 0 e 1 stanno nel quadrato. Dopo la normalizzazione U1 e U2 vengono riportati sulla retta retta obliqua che va da (0,1) a (1,0). Quindi, tutti i punti gialli andranno sul segmento in alto; tutti i punti nell’area rossa andranno sul segmento nel mezzo. Poiché l’area rossa è molto maggiore dell’area gialla, ne consegue che molti più punti finiranno sul segmento centrale rispetto a quelli che finiscono sui segmenti laterali. Torna? Beh, ora immaginatelo in 3D.

Qualcun’altro ha proposto questo metodo:

genero solo due numeri: U1 come distribuzione uniforme tra (0,1); U2 come distribuzione uniforme tra (0, 1-x1). Infine, U3 = 1-U1-U2.

Purtroppo non va meglio, ecco cosa esce fuori:

Stanno più frequentemente da una parte! Questo perché, dopo aver generato il primo, il secondo non ha distribuzione propriamente uniforme tra 0 e 1…

Un metodo corretto è quello del rejection sampling, proposto da Alb su friendfeed, e da hronir su okpanico. Si generano punti su un rettangolo nel piano 2D che ha base e altezza pari alla base del triangolo; se il punto finisce fuori dal triangolo, si butta via e se ne genera un altro. Se invece finsce dentro il triangolo, si proietta sui tre assi per ottenere i tre numeri originari. In questo modo siamo sicur di generare uniformemente. Come riprova, ecco la figura ottenuta:

Bella vero?

C’è un solo problema: se invece di generare solo 3 numeri ne vogliamo generare N, allora il numero di punti che cascano fuori dall’iper-triangolo in N-1 dimensioni sono molti di pù di quelli che cascano dentro. Talmente tanti di più che il metodo diventa improponibile. Quindi, al crescere di N tale metodo non è utilizzabile.

E questo era proprio il problema di Enrico e Giorgio: come generare N numeri a caso tali che la somma faccia un numero fisso minore di 1? Ci sono altri due metodi possibili. Il primo è il seguente:

Generiamo N-1 numeri in maniera uniforme compresi tra (0,1), chiamiamoli x(1), x(2), … x(N-1). Poi li ordiniamo dal più piccolo al più grande, e aggiungiamo x(0) = 0 in testa, e x(N)=1 in fondo. A questo punto, i numeri richiesti saranno:
U(1)=x(1)-x(0)=x(1),
U(2)=x(2)-x(1),



U(i) = x(i) – x(i-1),


U(N)=x(N)-x(N-1)=1-x(N-1).

Per capire come funziona, pensate di avere un segmento lungo 1, e di “gettare” N-1 punti a caso su di esso. La lunghezza dei segmenti delimitati tra due punti consecutivi sono i numeri che cerchiamo.

Per N=3 si ottiene un grafico 3D proprio uguale a quello mostrato qui su: provare per credere! Inoltre il metodo ha complessità O(N log(N)), quindi va abbastanza bene. Perché funziona? Non è facilissimo fare la dimostrazione. Bisogna dimostrare che la probabilità che un segmento abbia lunghezza minore di un certo L è proporzionale a L. Facendo i conti con le probabilità nel caso N=3 se ne dovrebbe uscire facilmente. L’altra sera l’abbiamo fatto con un mio studente e ce ne siamo venuti via con un paio di paginette… :) (se qualcuno ha tirato fuori un ragionamento migliore ce lo faccia sapere!)

L’ultimo metodo lo prendo dall’articolo, Enrico e Giorgio l’hanno chiamato UUniFast.

La distribuzione di probabilità della somma di N variabili casuali è la convoluzione delle distribuzioni delle variabili sommate. La pdf uniforme è una retta di inclinazione 1: P\{x \leq a\} = a. La convoluzione di N variabili uniformi è un poliomio di grado N: P\{s \leq a\} = a^N. Si può quindi sfruttare questo fatto come segue:

  • Per prima cosa si genera un numero tra 0 e 1 uniformemente, e se ne fa la radice (N-1)-esima. Chiamiamo questo numero s(N-1).
  • Quindi si genera un secondo mumero tra 0 e s(N-1), e se ne fa la radice (N-2)-esima. Chiamiamo questo numero s(N-2).
  • E così via fino a s(1).

I numeri richiesti sono quindi:

U(1)=S(1),

U(2)=S(2)-S(1),

U(i)=S(i)-S(i-1),


U(N)=1-S(N-1).

Ok, panico, se qui non mi avete seguito è perché magari non vi ricordate bene la teoria delle probabilità! Comunque, tutti i dettagli sono nel paper qui sotto.

A proposito: Enrico e Giorgio dimostrarono che il metodo “normalizzato” era a favore dell’algoritmo EDF, e quindi rifacendo le simulazioni con il nuovo metodo di generazione ristabilirono la giustizia tra gli algoritmi! (vince sempre EDF, ma con un distacco minore…)


Bini, E., & Buttazzo, G. (2005). Measuring the Performance of Schedulability Tests Real-Time Systems, 30 (1-2), 129-154 DOI: 10.1007/s11241-005-0507-9

About these ads
Post a comment or leave a trackback: Trackback URL.

Commenti

  • medeoTL (@medeoTL)  On 15 maggio 2012 at 10:01

    Ottimo articolo, complimenti. Alla fine il penultimo metodo è elegante e efficace, poteva anche venirmi in mente (forse) :D
    L’ultimo metodo è troppo difficile per me, in matematica sono un po’ arrugginito, non ho ben chiaro il concetto di convoluzione, so solo cosa significa ‘convolare a nozze’ e me ne guardo bene :-D

  • Alberto Berretti  On 16 maggio 2012 at 10:01

    Tutto molto bello. Per generare punti in un triangolo equilatero SENZA rejection sampling, ad es. nel triangolo equilatero su piano xy che ha per base il segmento (0,1) dell’asse x, si puo’ usare questo metodo: http://borel.mat.uniroma2.it/deposito/triangle.f90

  • Alberto Berretti  On 16 maggio 2012 at 10:03

    Tutto molto bello. Per generare punti in un triangolo equilatero SENZA rejection sampling, ad es. nel triangolo equilatero su piano xy che ha per base il segmento (0,1) dell’asse x, si puo’ usare questo metodo: acca ti ti pi due punti barra barra borel mat uniroma2 it barra deposito barra triangle.f90 [mi pare che non prenda commenti con link, capisco].

  • Jean M. M.  On 26 giugno 2012 at 22:39

    Veramente interessante! Fa sempre piacere scoprire un’applicazione pratica di un problema altrimenti solo teorico. Avevo letto un articolo di de Finetti che forse potrà interessare a qualcuno, su un tema molto simile. Mi pare che tra l’altro, in sostanza, descriva il primo metodo che hai riportato, quello di generare gli x(i) e usarli come “paletti”. Consiglio l’articolo perché, oltre che gratuito, è scritto in un delizioso italiano retrò (ricordo che dice “occorre e basta” invece di “è necessario e sufficiente”). Si chiama “Alcune osservazioni in tema di “suddivisione casuale””, facilmente reperibile in rete.

    • glipari  On 27 giugno 2012 at 17:21

      Grazie per la segnalazione. Leggerò l’articolo di De Finetti appena mi sarà possibile. Tra l’altro non conoscevo De Finetti (non sono un matematico), quindi questo commento è doppiamente gradito! grazie ancora.

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

Iscriviti

Ricevi al tuo indirizzo email tutti i nuovi post del sito.

Unisciti agli altri 71 follower

%d blogger cliccano Mi Piace per questo: