PAC learning: success of learning when receiving a sample from a different distribution
Let $x_1,...,x_N$ denote the elements of $\mathcal{X}$ and consider the marginal distributions $D_\mathcal{X}=(p_1,...,p_N)$ and $G_\mathcal{X}=(q_1,...,q_N)$. Recall that $p_i&gt;0$ implies that $q_i&gt;0$, hence the ratio $R=\max_i\frac{p_i}{q_i}$ is well defined. Also denote the output of the algorithm on a sample set $S$ by $h_S$, then:
\begin{align*}
err_G(h_S)&amp;=\sum\limits_{i=1}^N q_i\Pr\limits_{(x,y)\sim G}[h_S(x_i)\neq y | x=x_i]=\sum\limits_{i=1}^N q_i\Pr\limits_{(x,y)\sim D}[h_S(x_i)\neq y | x=x_i]\\
&amp;=R^{-1}\sum\limits_{i=1}^N q_iR\Pr\limits_{(x,y)\sim D}[h_S(x_i)\neq y | x=x_i]\ge
R^{-1}\sum\limits_{i=1}^Np_i\Pr\limits_{(x,y)\sim D}[h_S(x_i)\neq y | x=x_i]\\
&amp;=R^{-1}err_D(h_S)
\end{align*}
Thus, to show $err_D(h_S)$ is small with high probability when given samples from $G$, it suffices to show that $err_G(h_S)$ is small and using the bound $err_D(h_S)\le R \cdot err_G(h_S)$ where $R$ is a constant depending on the distributions. This is the standard problem of showing that the ERM is able to learn a finite hypothesis class, so I leave the details to you.