Due tipi di funzione.
Salve a tutti. Mi sono imbattuto in un problema curioso, un po' anti intuitivo che credo di aver risolto correttamente; però magari sarebbe bello avere una conferma da tanta gente su questo forum che sarà parecchio più brava di me.
Un utente A ha a disposizione un dominio di $N$ elementi ($N$ pari). Ne invia una parte (MINORE di $N/2+1$, che si denoterà con $\chi$) ad un utente B che applica una funzione $f$ su ognuno e restituisce i valori ottenuti all'utente A. L'utente B assicura che sceglierà (equivalentemente) soltanto tra due tipologie di funzioni: la prima tipologia è quella costante (restituisce o tutto 0 o tutto 1), la seconda è "bilanciata" e restituisce per metà dei valori del dominio il risultato 0 e per l'altra metà il risultato 1.
L'utente A deve capire qual é stata la scelta di B. Il caso, chiaramente, spiacevole è quello in cui A si ritrovi una sequenza costante. In tal caso A assume che la tipologia di funzione sia costante; qual é la probabilità che A abbia commesso un errore di valutazione? Bene. Il numero di configurazioni totali è $N!$ a cui bisogna moltiplicare un fattore 2 che tiene conto delle due tipologie di funzioni. Bisogna calcolare, adesso, il numero di configurazioni relative alla tipologia $f$ bilanciata con i primi $\chi$ termini uguali (e di un solo tipo):
\begin{equation}
\dfrac{\frac{N}{2}! (N-\chi)! }{(\frac{N}{2}-\chi)!}
\end{equation}
La formuletta è semplice da ricavare però c'è un'osservazione importante da fare. Il risultato è quello (e non moltiplicato per un fattore 2) perché contano le sequenze costanti di un solo tipo (o solo 0 o solo 1). Quindi complessivamente:
\begin{equation}
P[N,\chi]=\dfrac{\frac{N}{2}! (N-\chi)! }{(\frac{N}{2}-\chi)!2(N!)}
\end{equation}
Facciamo due verifiche. Una prima banale prendiamo $N=2$, quindi {$x_1$ , $x_2$} e $\chi=1$ (una sola estrazione). Chiaramente l'utente A sa se $f$ ha restituito 0 o 1. Si suppone 1 (con 0 ovviamente la logica è identica). Le combinazioni possibili in totale sono:
\begin{align}
f_{cost}(x_1) , f_{cost}(x_2) = 11 \\
f_{cost}(x_2) , f_{cost}(x_1) = 11 \\
f_{bal}(x_1) , f_{bal}(x_2) = 10 \\
f_{bal}(x_2) , f_{bal}(x_1) = 01
\end{align}
Ossia l'evento 10 si manifesta il 25% delle volte (lo stesso si trova con $P[N, \chi]$; che però intuitivamente infastidisce). Un'altra prova (non so se significativa però) è in corrispondenza di $\chi=0$ (nessuna estrazione). In tal caso è restituito 1/2 che dovrebbe avere il significato di probabilità a priori dovuta alla scelta della tipologia di funzione da parte di B. Che ne pensate?
Salve a tutti e grazie in anticipo.
Un utente A ha a disposizione un dominio di $N$ elementi ($N$ pari). Ne invia una parte (MINORE di $N/2+1$, che si denoterà con $\chi$) ad un utente B che applica una funzione $f$ su ognuno e restituisce i valori ottenuti all'utente A. L'utente B assicura che sceglierà (equivalentemente) soltanto tra due tipologie di funzioni: la prima tipologia è quella costante (restituisce o tutto 0 o tutto 1), la seconda è "bilanciata" e restituisce per metà dei valori del dominio il risultato 0 e per l'altra metà il risultato 1.
L'utente A deve capire qual é stata la scelta di B. Il caso, chiaramente, spiacevole è quello in cui A si ritrovi una sequenza costante. In tal caso A assume che la tipologia di funzione sia costante; qual é la probabilità che A abbia commesso un errore di valutazione? Bene. Il numero di configurazioni totali è $N!$ a cui bisogna moltiplicare un fattore 2 che tiene conto delle due tipologie di funzioni. Bisogna calcolare, adesso, il numero di configurazioni relative alla tipologia $f$ bilanciata con i primi $\chi$ termini uguali (e di un solo tipo):
\begin{equation}
\dfrac{\frac{N}{2}! (N-\chi)! }{(\frac{N}{2}-\chi)!}
\end{equation}
La formuletta è semplice da ricavare però c'è un'osservazione importante da fare. Il risultato è quello (e non moltiplicato per un fattore 2) perché contano le sequenze costanti di un solo tipo (o solo 0 o solo 1). Quindi complessivamente:
\begin{equation}
P[N,\chi]=\dfrac{\frac{N}{2}! (N-\chi)! }{(\frac{N}{2}-\chi)!2(N!)}
\end{equation}
Facciamo due verifiche. Una prima banale prendiamo $N=2$, quindi {$x_1$ , $x_2$} e $\chi=1$ (una sola estrazione). Chiaramente l'utente A sa se $f$ ha restituito 0 o 1. Si suppone 1 (con 0 ovviamente la logica è identica). Le combinazioni possibili in totale sono:
\begin{align}
f_{cost}(x_1) , f_{cost}(x_2) = 11 \\
f_{cost}(x_2) , f_{cost}(x_1) = 11 \\
f_{bal}(x_1) , f_{bal}(x_2) = 10 \\
f_{bal}(x_2) , f_{bal}(x_1) = 01
\end{align}
Ossia l'evento 10 si manifesta il 25% delle volte (lo stesso si trova con $P[N, \chi]$; che però intuitivamente infastidisce). Un'altra prova (non so se significativa però) è in corrispondenza di $\chi=0$ (nessuna estrazione). In tal caso è restituito 1/2 che dovrebbe avere il significato di probabilità a priori dovuta alla scelta della tipologia di funzione da parte di B. Che ne pensate?
Salve a tutti e grazie in anticipo.
Risposte
Risolto. Il ragionamento è sbagliato. Salve e alla prossima 
.
.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo