Naloga 4

Naj bo \(X\) končna množica s končno kardinalnostjo \(k\). Naj bo \(A\) učenec, ki na vzorcu \(S=((x_1, y_1), \ldots, (x_m, y_m)) \in (X \times \{0,1\})^m\) vrne funkcijo \(A(S)\), za katero velja:

Če je \(x=x_i\) za neki \(i \in \{1, \ldots, m\}\), potem \(A(S)(x)= y_i\),

Če \(x \notin \{x_1, \ldots, x_m\}\), potem je \(A(S)(x)\) izbran naključno z verjetnostjo \(1/2\) za vsako oznako v \(\{0,1\}\).

Naj bo dana funkcija \(f: X \to \{0,1\}\). Definirajmo verjetnostno porazdelitev \((U,f)\) na \(X \times \{0,1\}\) tako, da vsakemu paru \((x, f(x))\) priredimo verjetnost \(1/k\), vsakemu \((x,y) \notin \{(x, f(x)): x \in X\}\) pa verjetnost 0.

Pokažite, da za vsako funkcijo \(f: X \to \{0,1\}\) in \(S=((x_1, f(x_1)), \ldots, (x_m, f(x_m)))\) velja

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

[Skupaj 7 točk]