[RISOLTO][Algoritmo]Calcolo di una Probabilita'

[fibonacci]

Codice: Seleziona tutto

Devo implementare un algoritmo di deskewing per un True Random Number Generator(TRNG).
Ma non e' questo il punto, cioe' non e' nell'implementazione. E' che devo giustificare matematicamente che funziona.
Quindi si suppone di avere un TRNG che generi un flusso di bit in cui Pr(bit=0) = Pr(bit=1)=0.5 per ogni singolo bit
Inoltre il valore di un bit non dipende dai precedenti
Il flusso di bit tuttavia non e' omogeneo, la probabilita' di avere un bit a 1 e' 0.5+k e che sia 0 e' 0.5 -k
con 0<k<0.5
Quest ultime probabilita' sono da riferirsi a una sequenza emessa (cioe' su 10 bit ad esempio (0.5+k)*10 sono ad 1)
Quindi c'è uno skew (cioe' non ci sono tanti 0 quanti 1)
Per eliminare o ridurre lo skew scarto tutte le coppie 00 e 11 (Nota bene che le coppie non sono sovrapposte cioe' 0010 sono due coppie, la coppia 00 e quella 10)
e sostituisco ogni coppia 01 con 0
e 10 con 1 Questo algoritmo so che funziona ma devo dimostrare matematicamente che
1) Quant è probabilita' di ciascuna coppia nella sequenza originale
2)Quant'è probabilita' delle cifre 0 e 1 nella sequenza modificata con l'algoritmo (dovrebbe essere vicino a 0.5)
Il punto 1 credo dovrebbe servire come punto di partenza per il calcolo del punto 2

Qualcuno che ha dimestichezza col calcolo delle probabilita' o ha intuito come dovrei procedere potrebbe darmi una mano?
Grazie

[M_A_W_ 1968]

Qualcuno che ha dimestichezza col calcolo delle probabilita' o ha intuito come dovrei procedere potrebbe darmi una mano?

Io rientro nella prima categoria, ma non vorrei fornirti la soluzione... perché è decisamente banale.
L'unica cosa che serve, in questo caso, è il teoremino della probabilità composita: dati due o più eventi indipendenti, come nelle tue ipotesi, la probabilità dell'evento composito è pari al prodotto delle singole probabilità. Non sto a spiegarti tutta la storia della sequenza di Bernoulli negli ultimi tre o quattro secoli.

Anzi, senza fare particolari conti, limitati a chiamare (con grande spicco di fantasia) p1 la probabilità di uscita del simbolo 1, e p0 la probabilità complementare inerente il simbolo 0. Chiaramente p0 è diverso da p1, come da ipotesi, ed è altresì ovvio che p0 = 1 -p1.
In base a quanto appena squadernato in merito alla probabilità composita, e con ovvio significato dei simboli:

P("00") = p0·p0
P("11") = p1·p1
P("01") = p0·p1
P("10") = p0·p1 tanto siamo chiaramente in un'algebra commutativa.

A questo punto, la dimostrazione è praticamente terminata. Cosa si nota infatti, con estrema chiarezza, riguardo ai simboli rispettivamente scartati e sostituiti?

[cuccagna]

devi pensare come se avessi una sorgente che mette simboli di bit uno con probabilità
0.5+k

[fibonacci]

grazie della risposta
il motivo per cui non ci sono arrivato io è che non consideravo la sequenza
come emessa da una nuova sorgente con p1=0.5+k
bensì cercavo di trovare tutte le sequenze con un numero di 1
Pari a 0.5+k in percentuale e lunghe N
e poi trovare di queste sequenze tutte le possibili coppie e quante di queste erano
00 01 10 e 11
insomma ricerca combinatoria
invece la soluzione era molto più semplice
quindi
come l hai impostata tu sfruttando il fatto che gli eventi sono indipendenti
p(11)=(0.5+k)*(0.5+k)
il fatto che p(01 )uguale a P(10) è immediato

[M_A_W_ 1968]

il fatto che p(01 )uguale a P(10) è immediato

Naturalmente anche un'analisi combinatoria ben impostata dovrà dare, alla fine, i medesimi risultati. Ma solo dopo un po' di conti inutili, noiosi e magari anche proni ad errori.
Invece la matematica, IMO, è un modo di vedere le cose che serve (quasi sempre) ad evitare conti complicati ed a svelare le relazioni tra enti astratti...

[fibonacci]

tutte le vie portano a Roma ma io avevo scelto quella che passava per il Circolo Polare Artico.
un ultima cosa
ho calcolato il numero atteso di bit (che chiamo N)per produrre x bit di output senza skew e viene
N=2*x/(0.5-2*(k^2))
praticamente si perdono più di metà dei bit.
per generare più bit senza skew ho pensato di usare anche il bit sovrapposti
ovvero ad esempio il primo bit in uscita dipende dai bit 1 e 2, il secondo bit in uscita dipende dai bit 2 e 3 e così via
in questo caso come imposto il
calcolo
pr(00)
pr(01)
pr(10)
pr(11)?

entrano in gioco probabilità condizionate?
a intuito mi sembrerebbe che questa volta la probabilità che si verifichi la coppia 10 Siamaggiore della probabilità che si verifichi la coppia 01
però dovrei capire e quantificare la differenza delle due probabilità per capire se lo skew che rimane è accettabile al fine di avere un maggiore bit rate

ma non riesco ad astrarre
( in realtà la soluzione migliore sarebbe usare il deskew usato nell hardware Intel per trng che usa la modalità operativa cbc doppia usando aes a 128 bit come cifrario simmetrico ma in questo caso effettuare un'analisi probabilistica sarebbe molto difficile [per me ])

[M_A_W_ 1968]

Non avevo fatto caso a quest'ultimo post, avendo solo notato il tag [RISOLTO] nell'elenco dei thread.

L'analisi probabilistica del TRNG Intel è disponibile in letteratura, perché ricordo che mi è passata per le mani qualche tempo fa, anche se non ho a disposizione le coordinate esatte.

In ogni caso, si può vedere il nuovo problema come segue. Consideriamo una terna estratta come due coppie concatenate, es. "010" ossia "01" e poi "10".
La probabilità di uscita della prima sequenza è ovvia. Per la seconda coppia, tutto dipende dal fatto che la seconda cifra della coppia precedente sia pari rispettivamente a zero o uno. Chiamiamo Px0 e Px1 tali eventi, e si ha ovviamente:

Px0 = P("00") + P("10")
Px1 = P("11") + P("01")

Le probabilità delle varie combinazioni della seconda coppia si ottengono rispettivamente moltiplicando per le "vecchie" P0 e P1 le quantità appena descritte. Purtroppo Px0 e Px1 differiscono tra loro, come è evidente ad una prima occhiata, ma questo non complica poi troppo l'analisi finale.

[fibonacci]

sì avevo messo risolto ma poi ho trovato in letteratura questo raffinamento

il ragionamento esposto non fa una grinza
ho effettuato i calcoli e p(01)=p(10) sempre anche per le coppie successive , risultato che trovo controintuitivo ma ottimo per le mie esigenze dato che effetto 1 deskew completo ma con un bit rate maggiore rispetto a prima
per quello che mi è stato chiesto ho fatto anche troppo,usare il deskew trng intel significherebbe non solo studiarsi l'analisi matematica che immagino non banale ma anche implementare l
aes
inoltre se non erro l aes cbc che fa il deskew della Intel prende 512 bit casuali e ne sputa fuori 256
quindi un rate inferiore a quello esposto

stavolta metto risolto per davvero!
grazie e complimenti per la competenza