Detyra 4

Le të jetë \(X\) një bashkësi e fundme me madhësi të fundme \(k\). Le të jetë \(A\) një nxënës i cili, për një mostër \(S=((x_1, y_1), \ldots, (x_m, y_m)) \in (X \times \{0,1\})^m\), prodhon një funksion \(A(S)\) të tillë që:

 Nëse \(x = x_i\) për ndonjë \(i \in \{1, \ldots, m\}\), atëherë \(A(S)(x) = y_i\),
 
 Nëse \(x \notin \{x_1, \ldots, x_m\}\), atëherë \(A(S)(x)\) zgjidhet rastësisht me probabilitet \(1/2\) për secilën etiketë në \(\{0,1\}\). 

Duke pasur një funksion \(f: X \to \{0,1\}\), përcaktoni një shpërndarje probabiliteti \((U,f)\) mbi \(X \times \{0,1\}\) duke i caktuar probabilitetin \(1/k\) çdo çifti \((x, f(x))\) dhe probabilitetin 0 çdo \((x,y)\) që nuk është në \(\{(x, f(x)): x \in X\}\).

Tregoni se për çdo \(f: X \to \{0,1\}\) dhe \(S=((x_1, f(x_1)), \ldots, (x_m, f(x_m)))\),

\[L_{(U,f)}(A(S)) - L_S(A(S)) \geq \frac{(k - m)}{2k}.\]

[Gjithsej 7 pikë]