Matematici, fatevi avanti

[MAT]

Allora, per eseguire i calcoli di cui ho bisogno mi occorrerebbero variabili a millemila bit. Una stima perciò è d'obbligo prima di pigiare i tasti della calcolatrice.
Voglio calcolare la probabilità che k elementi siano uguali in un insieme di n. Per far ciò occorre calcolare le combinazioni con ripetizione di questi elementi e dividerli per n^k, come mostrato in figura (grazie LaTeX):


Il problema è che i numeri sono:
n = 2^160
k = 2^30

Qualcuno ha qualche idea di come farlo? Chiaramente bisogna prima lavorarci su carta e trarne una stima. Che approssimazioni potrei assumere qui? Mi servirebbe una stima per eccesso, dato che devo dimostrare che tale probabilità è bassa.

[elettronicha]

Ciao esiste la formula di Stirling che approssima n! con n^n (cercala con google...) da cui si ottiene che:

- n! è un o-piccolo di (n^n)
- n! è un omega-piccolo di 2^n
- log2(n!) cresce come n*log2(n) (ovviamente a meno di una cost moltiplicativa, ma ti vuoi formalizzare con un per 3 o per 4,5 con quei numeracci?)

Prova a estrarre il log2 di tutta la formula della probabilità, svolgere i calcoli con l'ultima approx che ti ho dato e usando le proprietà dei logaritmi e poi fai 2 ^ (il risultato che hai ottenuto). Non ho provato a fare i conti a mano perché è una certa ora...

Fammi sapere.

[elettronicha]

PS: non sono un matematico e sono anche mezzo fuso adesso, potrei essermi sbagliato, abbi pietà di me in quel caso.
L'idea è quella di ridurre coi log l'ordine dei numeri da trattare per poi elevare a potenza un 2 con un numero "più piccolo".

[MAT]

Grazie mille elettronicha!! Domani ci ragiono su (anche io ora sono piuttosto cotto).
E complimenti per la velocità!!

[elettronicha]

In realtà appena vedo i fattoriali mi viene in mente la formula di Stirling, quindi appena ho letto il post è stata la prima cosa che ho pensato, me la sono rivista e mi sono chiesto se si poteva utilizzare.

[absinthe]

bella sfidazza :P
mi ci sono messo con con matlab e la wiki e a me non torna tanto piccolo :(.
dunque la wiki dice che la formula di Stirling è:

x! = sqrt(2*pi*x) * (x/e)^x

se non ho sbarellato i calcoli:

n!/k!= sqrt(2*pi*2^160) / sqrt(2*pi*2^30) * [(n/e)^n / (k/e)^k]

ovvero:

n!/k!= sqrt(2^130) * n^n/k^k * e^(k-n)

ora

sqrt(2^130)=3.7*10^19

inoltre

160=2^5*5
30=2*5*3=2*15

quindi

n^n=(2^160)^(2^160)=2^(160*2^160)=2^[(2^165)*5]
k^k=(2^30)^(2^30)=2^(30*2^30)=2^[(2^31)*15]

ne segue che

n^n/k^k=2^[(2^165)*5] / 2^[(2^31)*15]= 2^ [(2^165)*5- (2^31)*15] = 2^(2.43*10^50)

mentre

e^(k-n)=e^(2^30-2^160) = e^(-1.5*10^48)

riassumendo:

n!/k! = 3.7*10^19 * 2^(2.43*10^50) * e^(-1.5*10^48)

l'ordine di grandezza è quindi

n!/k!= 10^19 * 2^( 10^50) * e^(-10^48)

mente

n^k= (2^160)^(2^30)=2^(160*1.07*10^7)

il cui ordine è

n^k=2^(10^9)

mo:

10^19 * 2^(10^50)/2^(10^9) *e^(-10^48) = 10^19 * 2^(10^50)/2^(10^9) * 1

che piccolo a occhio non è...
se qualcuno trova l'errore me lo indichi per pietà... :)

M

[first]

Non esiste una soluzione scappatoia al tuo problema. Mi spiace devi calcolarti il risultato.

[elettronicha]

che piccolo a occhio non è...
se qualcuno trova l'errore me lo indichi per pietà...

Certo, te lo indico :P Non hai fatto un'analisi critica del problema Il numero che deve venir fuori è una probabilità, quindi minore di 1!! Impossibile che venga un numero enormemente grande, piuttosto può essere un numero enormemente piccolo.

Scusa first, ci puoi speigare perché non esiste soluzione al problema? Così ci mettiamo l'anima in pace e non ci scervelliamo oltre MAT voleva solo una stima grezza.

PS: ma che ca**o stai calcolando MAT? Mi dici dove hai trovato quei numeri?

[MAT]

che piccolo a occhio non è...
se qualcuno trova l'errore me lo indichi per pietà...

Certo, te lo indico :P Non hai fatto un'analisi critica del problema Il numero che deve venir fuori è una probabilità, quindi minore di 1!! Impossibile che venga un numero enormemente grande, piuttosto può essere un numero enormemente piccolo.

Giusta considerazione. Inoltre la formula n!/(n^k * k!) deriva dal prodotto di termini tutti inferiori all'unità, quindi è un numero inferiore all'unità.

Tuttavia avevo omesso un piccolo particolare nella prima formulazione del problema. La formula che io ho scritto indica la probabilità che due valori NON coincidano. Infatti, fisso un valore fra n, poi analizzo gli altri (k-1) valori. La probabilità che il primo sia diverso da quello selezionato è (n-1)/n; la probabilità che il secondo sia diverso dagli altri due è (n-2)/n. Per l'i-esimo è (n-i)/n. Quindi per l'ultimo, il (k-1)-esimo è (n-k+1)/n. La probabilità congiunta che accadano questi (k-1) eventi INDIPENDENTI è data dal prodotto delle singole probabilità, il che porta alla formula indicata nel primo post.
A me interessa dimostrare che la probabilità che due valori coincidano sia bassa, che è pari al complementare a 1 di quella scritta, quindi 1-n!/(n^k * k!). Mi servirebbe quindi una funzione f(n, k) più semplice tale per cui
0 < n!/(n^k * k!) < f(n,k)
e che rimanga "bassa" per i valori di n e k specificati.

Scusa first, ci puoi speigare perché non esiste soluzione al problema? Così ci mettiamo l'anima in pace e non ci scervelliamo oltre MAT voleva solo una stima grezza.

Sì, a me serve solo una semplificazione. I calcoli così sono inaffrontabili, nessun calcolatore al mondo potrebbe calcolare il fattoriale di 2^160.

PS: ma che ca**o stai calcolando MAT? Mi dici dove hai trovato quei numeri?

Voglio calcolare la probabilità che due stringhe, date in pasto alla funzione hash SHA1 (che ritorna valori a 160 bit), vengano mappate sullo stesso valore. Le stringhe vengono prese in un insieme di k elementi che non si conoscono a priori. Per questo calcolerei la probabilità, altrimenti con le stringhe fissate l'evento non sarebbe incerto.

[elettronicha]

Scusa MAT, ma sei sicuro di quella formula? Io dovrei rispolverare le nozioni di calcolo combinatorio, forse tu le hai più fresche. Se provi a calcolare il limite della formula per n che tende a infinito e supponi n>>k, usando l'approx di Stirling per il fattoriale, ti accorgi che è infinito. Da qui il numero molto grande trovato da absinthe, col quale mi scuso. Se è una probabilità dovresti trovare un numero tra 0 e 1.

[MAT]

Hai ragione! ERRORE MADORNALE!!!!

Anche le mie nozioni di calcolo combinatorio sono remote, ma qui non si trattava di quello, solo di un "banalissimo" errore di distrazione.

Ecco la versione corretta.. scusatemi

La probabilità che questi k elementi siano tutti diversi è

Moltiplico e divido per n/n e ((n-k)!)/((n-k)!) (lecito perché sono uguali a 1)

il numeratore è n!


quindi io devo dimostrare che questo numero è "grande" (resta comunque inferiore a 1), quindi il suo complemento a 1 è "piccolo".

[Paoletta]

elettronicha, complimenti! il mio ricordo dell'esisternza della funzione di Stirling era finito nel dimenticatoio...ora me l'hai rammentato!

[elettronicha]

Sono cose che servono nella vita. La studiai forse in Analisi I per i limiti o Calcolo delle probabilità.
A parte gli scherzi, dovrebbe essere utile anche nell'analisi di alcuni algoritmi per classi di problemi NP e cose simili
Mai stato un mostro agli esami di matematica, eh!

[first]

puo procedere cosi:

P < [(n-1)/n]^k (nb che con i tuoi dati tale maggiorante e circa 1 quindi inutile)

e procedi cosi fiche trovi il grado di approsimazione spannometrico che ti interessa

P < [(n-1)(n-2)/n^2]^(k/2)
ma anche cosi il maggiorante e' praticamente uguale a 1


se ti interessa solo dire che P "e' grande" allora il problema mi sembra banale, ogni fattore moltiplicativo (compreso quello "piu piccolo" (n-k+1)/n) che compone P giace in un intorno sinistro di 1 di raggio infinitesimo. Puoi cosi' scommetterci 100 euro che P e' "sicuramente" > di 0.9 e avresti ancora un gigantesco margine di errore. Per capirci P> [(n-k+1)/n]^k>(1-10^(-5))

[MAT]

se ti interessa solo dire che P "e' grande" allora il problema mi sembra banale, ogni fattore moltiplicativo (compreso quello "piu piccolo" (n-k+1)/n) che compone P giace in un intorno sinistro di 1 di raggio infinitesimo. Puoi cosi' scommetterci 100 euro che P e' "sicuramente" > di 0.9 e avresti ancora un gigantesco margine di errore. Per capirci P> [(n-k+1)/n]^k>(1-10^(-5))

Non credo che nella tesi di laurea accettino una scommessa al posto di una dimostrazione matematica