# Equivalence of RKHS with high probability

Suppose you have two PSD kernels $$k(x,y)$$ and $$k'(x,y)$$. Let $$\mathcal{H}_k(\mathcal{D})$$ and $$\mathcal{H}_{k'}(\mathcal{D})$$ be the corresponding RKHS's.

Now, if we know that for all $$f \in \mathcal{H}_k(\mathcal{D})$$ if $$||f||_{k'}$$ is bounded (here $$||.||_k$$ denotes the norm w.r.t kernel $$k$$), then $$\mathcal{H}_{k'}(\mathcal{D}) = \mathcal{H}_k(\mathcal{D})$$.

However, now suppose $$k'(x,y)$$ is created from a randomized algorithm and we can prove that with probability $$1 - \delta$$, $$(1 - \epsilon) k(x,y) \leq k'(x,y) \leq (1 + \epsilon) k(x,y)$$ for all $$x,y$$, for a fixed $$\epsilon$$.

In this case, can we conclude that with probability $$1 - \delta$$, $$\mathcal{H}_{k'}(\mathcal{D}) = \mathcal{H}_k(\mathcal{D})$$. I am not even sure whether such a statement is theoretically sound.

If I understand your question correctly, you are asking if $$k'\le ck$$ for a constant $$c\ge1$$ implies that $$\mathcal{H}_{k'}\subset \mathcal{H}_{k}$$. Now Theorem 3.11 in V.I. Paulsen, M. Raghupathi, An Introduction to the Theory of RKHS, Cambidge Univ. Press 2016 says the following: $$f\in \mathcal{H}_{k'}$$ with norm $$\le1$$ iff $$(x,y)\mapsto k'(x,y) - f(x)\overline{f(y)}$$ is a kernel function. I think this implies the claim.

If your set of inequalities holds for $$k'=k'_\omega$$ for $$\omega$$ in a measurable subset of the underlying probability space of probability $$\ge 1-\delta$$, then on this subset $$\mathcal{H}_{k'_\omega} = \mathcal{H}_{k}$$. In this sense the equality of RHKS (which might or might not be an event) occurs with probability $$\ge 1-\delta$$.