Let $\mathcal{X}$ be a subset of $\mathbb{R}^n$ and let $\mathcal{F}$ be a space of functions: $$\mathcal{F} = \{f | f: \mathcal{X} \to \mathbb{R} \}$$ Let $P_\mathcal{X}$ be a probability distribution over $\mathcal{X}$ and let $P_\mathcal{F}$ be a probability distribution over $\mathcal{F}$. Consider $$\mathbb{P} \left( F(X^n) > a \right)$$ where $F$ is a random function picked according to $P_\mathcal{F}$ and $X^n$ is a random sequence picked according to $P_\mathcal{X}$. Now suppose I showed that $$\mathbb{P} \left( F(X^n) > a \right) \leq \frac{1}{n}$$ This implies (for $n \geq 2$) that there exists a deterministic function $f$ and a deterministic $x^n \in \mathcal{X}$ such that $f(x^n) \leq a$.
But I want to make the following statement: for sufficiently large $n$, there exists a deterministic function $f$ such that with high probability, $f(X^n) \leq a$, where $X^n$ is random. I call this partial derandomization.
Can I make this statement from what I have? If not, what other ways I could explore?
PS: $\mathcal{X}$ is compact.
By the law of total expectation, $$ \mathbb P(F(X^n) > a) = \mathbb E(1_{F(X^n) > a}) = \mathbb E(\mathbb E(1_{F(X^n) > a} \mid F)). $$ In order for the expected value $\mathbb E(\mathbb E(1_{F(X^n) > a} \mid F))$ to be at most $\frac1n$, there must be at least one outcome $\omega$ for which the random variable $\mathbb E(1_{F(X^n) > a} \mid F)$ is at most $\frac1n$. The value of $\mathbb E(1_{F(X^n) > a} \mid F)$ at $\omega$ is $\mathbb E(1_{F(X^n) > a} \mid F = f)$, where $f$ is the value of the random variable $F$ at $\omega$. So there must be $f \in \mathcal F$ such that $\mathbb E(1_{F(X^n) > a} \mid F = f) \le \frac1n$.
This is the $f$ you wanted, since $\mathbb E(1_{F(X^n) > a} \mid F = f) = \mathbb E(1_{f(X^n) > a}) = \mathbb P(f(X^n) > a)$.