Probabilità della somma
Ciao a tutti!
Ho bisogno del vostro aiuto non essendo molto bravo in probabilità e statistica.
Siano $ c: {0, 1}^n \to {0, 1}$ una funzione booleana e $x$ un vettore scelto secondo una distribuzione di probabilità $D$ in ${0, 1}^n$. Sia $l \in {0, 1}$ tale che $l = c(x)$ con probabilità $1-\epsilon$ e $l = 1- c(x)$ con probabilità $\epsilon$ ($\epsilon$ è l'error-rate).
Denotiamo con $x_1+x_2$ e $l_1+l_2$ la somma modulo 2 rispettivamente dei vettori e dei punti.
Allora vale il seguente risultato:
Siano $(x_1, l_1)$, $(x_2, l_2)$, ..., $(x_m, l_m)$ $ m$ coppie ottenute a partire da una data funzione booleana $c$ con error- rate $\epsilon$ (avendo scelto gli $x_i AA i=1,...m$ in maniera indipendente); allora $l_1+l_2+...+l_m = c(x_1+x_2+...+x_m)$ con probabilità $\frac{1}{2}+\frac{1}{2}(1-2\epsilon)^m$.
La dimostrazione è la seguente:
Ragioniamo per induzione.
Per $m=1$ è vera. Supponiamo che vale per $m-1$ e dimostriamolo per $m$. Allora la probabilità che $l_1+l_2+...+l_m = c(x_1+x_2+...+x_m)$ è $(1-\epsilon)(\frac{1}{2}+\frac{1}{2}(1-2\epsilon)^{m-1}) + \epsilon(\frac{1}{2}-\frac{1}{2}(1-2\epsilon)^{m-1})$.
Scusate ma perchè quest'ultima probabilità si calcola così? Mi trovo col primo addendo ma il secondo? Forse non so proprio come si ragiona.
Ho bisogno del vostro aiuto non essendo molto bravo in probabilità e statistica.
Siano $ c: {0, 1}^n \to {0, 1}$ una funzione booleana e $x$ un vettore scelto secondo una distribuzione di probabilità $D$ in ${0, 1}^n$. Sia $l \in {0, 1}$ tale che $l = c(x)$ con probabilità $1-\epsilon$ e $l = 1- c(x)$ con probabilità $\epsilon$ ($\epsilon$ è l'error-rate).
Denotiamo con $x_1+x_2$ e $l_1+l_2$ la somma modulo 2 rispettivamente dei vettori e dei punti.
Allora vale il seguente risultato:
Siano $(x_1, l_1)$, $(x_2, l_2)$, ..., $(x_m, l_m)$ $ m$ coppie ottenute a partire da una data funzione booleana $c$ con error- rate $\epsilon$ (avendo scelto gli $x_i AA i=1,...m$ in maniera indipendente); allora $l_1+l_2+...+l_m = c(x_1+x_2+...+x_m)$ con probabilità $\frac{1}{2}+\frac{1}{2}(1-2\epsilon)^m$.
La dimostrazione è la seguente:
Ragioniamo per induzione.
Per $m=1$ è vera. Supponiamo che vale per $m-1$ e dimostriamolo per $m$. Allora la probabilità che $l_1+l_2+...+l_m = c(x_1+x_2+...+x_m)$ è $(1-\epsilon)(\frac{1}{2}+\frac{1}{2}(1-2\epsilon)^{m-1}) + \epsilon(\frac{1}{2}-\frac{1}{2}(1-2\epsilon)^{m-1})$.
Scusate ma perchè quest'ultima probabilità si calcola così? Mi trovo col primo addendo ma il secondo? Forse non so proprio come si ragiona.
Risposte
Scusate ma il fatto che nessuno mi risponde significa che la domanda è troppo sciocca o troppo difficile (o incomprensibile)?
Nessuno mi può aiutare?
Nessuno mi può aiutare?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo