Задача 4

Нека \(X\) е конечен множествен со некоја конечна големина \(k\). Нека \(A\) е учач што на примерок \(S=((x_1, y_1), \ldots, (x_m, y_m)) \in (X \times \{0,1\})^m\) излезно дава функција \(A(S)\) така што:

Ако \(x=x_i\) за некое \(i \in \{1, \ldots, m\}\) тогаш \(A(S)(x)= y_i\),

Ако \(x \notin \{x_1, \ldots, x_m\}\), тогаш \(A(S)(x)\) се избира случајно со веројатност \(1/2\) за секоја ознака во \(\{0,1\}\).

Дадена е функција \(f: X \to \{0,1\}\), дефинирај веројатносна распределба \((U,f)\) над \(X \times \{0,1\}\) со доделување веројатност \(1/k\) на секој пар \((x, f(x))\) и веројатност 0 на секој \((x,y) \notin \{(x, f(x)): x \in X\}\).

Покажи дека за секоја \(f: X \to \{0,1\}\) и \(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}.\]

[Вкупно 7 поени]