 Solution

Let $Z_p={\sum }_x\tilde{p}(x)$ and $Z_q={\sum }_x\tilde{q}(x)$, both finite and positive as required for normalization. A sufficient envelope condition is $\boxed{M\ge \underset{x\in \Omega }{\sup }\tilde{p}(x)/\tilde{q}(x)}$ with finite $M>0$. Use independent proposals and independent uniforms on each trial. This guarantees an acceptance probability in $[0,1]$ for every state. Choose the smallest certified upper bound on that ratio, since increasing $M$ decreases the overall acceptance rate. The ratio must be bounded for this particular proposal to admit such an envelope.