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.