Conceptually, there are two different types of distributions: the data distribution, i.e. so we can draw data $x\sim\mathcal{D}$, and the (various) distributions over learning models, often expressed as distributions over the parameter spaces (e.g. if you're familiar with Bayesian neural networks), so we can for example write $\theta \sim \mathcal{R}$ to draw, say, a set of random weights for a neural network.
The idea in PAC-Bayes is that you learn a distribution over predictors, $Q$, so that if you draw a random predictor $f_\theta\sim Q$ (which really means $\theta\sim Q$ I suppose but I'm following their notation), then $f_\theta$ should perform well on the data. In other words, $Q$ depends on the training data, $T=\{x_i\}_i,\,x_i\sim\mathcal{D}$. We can think of this as assuming $Q$ has parameters $\phi$, and we are learning $\phi$ from $T$. Thus, $Q$ is dependent on $T$, and thus $f_\theta\sim Q$ is dependent on it as well.
In the paper, they consider a special case, where $f_{w+u}\sim Q$, where $w$ is learned but presumably deterministic, and $u$ is random (so I'd write $w+u\sim Q$). Consider the joint distribution $p(\theta, T)$ where $\theta=w+u$. Because $\theta$ is learned, it is dependent on $T$, so we cannot say $p(\theta,T)=p(\theta|T)p(T)=p(\theta)p(T)$.
Now what do you do if you haven't seen any training data yet? You still want to be able to draw random predictors. So, as a Bayesian :), we define a prior $P$, so that we can draw $f_\psi \sim P$, where $P$ has no dependence on the data $T$, i.e. it is not learned. So we can write $p(\psi,T)=p(\psi)p(T)$, because $T$ and $\psi$ are independent.
This is confusing because to make sense of a notion of "independence" here one has to somehow first be able to imagine the "prior" and the "data" both as random variables on the same probability space. To the best of my knowledge the only formal notion of independence is that of between 2 random variables both of which are mapping from the same probability space.
The prior is not a random variable, it is a distribution. The key is that there are two spaces, the set of data $\mathcal{X}$ and that of model parameters $\Phi$, and there are distributions ($\mathcal{D}$ and $Q$ & $P$) on those spaces. Our notion of independence is on one space, if you want to think of it that way: it is on the product space, i.e. $ S= \mathcal{X}\times \Phi$, so that we can define joint distributions like $p(\psi,T)$ or $p(\theta,T)$. At least that's how I see it.
(a)
Am I allowed to include this prior in the list of K prior options? Or will that also break the assumptions of this proof?
I'm not sure about this, I don't know of the theorem you are talking about. But for this theorem or a modification of it specifically, then yes, I think it will break the proof assumptions. It would let you put $Q$ in the list for example, which probably seems problematic.
However, you might be interested in papers doing this: e.g., Parrado-Hernandez et al, PAC-Bayes Bounds with Data Dependent Priors
(b)
Am I allowed to use this prior if I say use it in a PAC-Bayes bound for the same predictor but I have say changed the changed the data distribution from which the samples are being taken (from the auxiliary experiments to the case when the bound is being evaluated) or I have thrown away from the support of the distribution the part of the data on which I did these auxiliary experiments.
Interesting question. I think this is possible but with different bounds. Specifically, maybe you could think of this as an instance of domain adaptation (for which there is a lot of work on learning bounds, which contain an additional term that is based on the difference between the old and new distributions).
Note that PAC-Bayes in the domain adaptation context (e.g., Germain et al, A New PAC-Bayesian Perspective on Domain Adaptation) still utilize a prior from before seeing the the source or the target domains. You cannot escape this, usually, in a truly Bayesian method. What I am suggesting is considering the change in distribution used in the method you proposed as a form of domain adaptation. I'm not an expert in this area though. :)
