Suppose that we have
$$
\frac{p(x)}{q(x)} \propto \exp(\tau f(x)),
$$
where we can sample from $q$ but not from $p$. Our goal is to generate a set of particles $\{x\_i\}\_{i=1}^n$ such that $n^{-1}\sum\_{i=1}^n \delta\_{x\_i}$ approximates $p$.


Does the following procedure work with an approximation error between $n^{-1}\sum\_{i=1}^n \delta\_{x\_i}$ and $p$ in total variation distance (or any distance/divergence between distributions) **that decays in $\tau$ (as $\tau\rightarrow \infty$)**?


(i) sample $m$ particles $\{x\_i\}\_{i=1}^m$ from $q$;


(ii) keep the "winning" particle $x\_i^\*$ that has the largest value $f(x\_i^\*) = \max\_{i \in \{1, \ldots, m\}} f(x\_i) $ and discard others;


(iii) repeat (i) and (ii) for $n$ times and output $\{x\_i^\*\}\_{i=1}^n$.



Importance resampling with exponential weighting
$\newcommand{\de}{\delta}\newcommand\ep\varepsilon\newcommand{\R}{\mathbb R} $First of all, the total variation distance between any empirical distribution (which is discrete) and the (absolutely continuous) distribution (say $P$) with pdf $p$ is always $1$, since these two distributions are mutually singular. So, these two distributions cannot be close to each other in the total variation metric.


If we now talk about the closeness of your empirical distribution to $P$ in the [Lévy--Prokhorov metric](https://en.wikipedia.org/wiki/L%C3%A9vy%E2%80%93Prokhorov_metric) $LP$ (metrizing the convergence in distribution), then your procedure will work if $n\to\infty$, $m\to\infty$, and
the function $f$ and the pdf $q$ are such that for some point $a$ and any real $\de>0$ we have
\begin{equation\*}
 Q(B\_a(\de))>0 \tag{1}\label{1}
\end{equation\*}
and
\begin{equation\*}
 I(\de)>S(\de), \tag{2}\label{2}
\end{equation\*}
where $Q$ denotes the distribution with pdf $q$,
\begin{equation\*}
 I(\de):=\inf\_{B\_a(\de)}f,\quad S(\de):=\sup\_{B\_a(2\de)^c}f,
\end{equation\*}  

$B\_a(\de)$ is the open ball of radius $\de$ centered at $a$, and the superscript $^c$ denotes the complement. (The condition \eqref{2}--\eqref{1} may be referred to as the condition that $f$ have only one $q$-essential point of maximum.)


Indeed, then (writing $x^\*$ instead of the meaningless $x^\*\_i$), in view of \eqref{2}, \eqref{1}, and the condition $m\to\infty$, for any real $\de>0$ we have
\begin{equation\*}
 \Pr\nolimits\_Q(x^\*\notin B\_a(2\de))\le \Pr\nolimits\_Q(x\_1\notin B\_a(\de),\dots,x\_m\notin B\_a(\de)) 
 =(1-Q(B\_a(\de)))^m\to0, 
\end{equation\*}
where $\Pr\_Q$ is a probability measure with respect to which $x\_1,\dots,x\_m$ are iid random variables each with distribution $Q$.
So, $x^\*\to a$ in probability and hence
\begin{equation\*}
 LP(P\_{x^\*},\de\_a)\to0, \tag{3}\label{3}
\end{equation\*}
where $P\_{x^\*}$ is the distribution of $x^\*$.


Next,
\begin{equation\*}
 p=e^{\tau f}q/C\_\tau,
\end{equation\*}
where
\begin{equation\*}
 C\_\tau:=\int e^{\tau f}q. \tag{3.5}\label{3.5}
\end{equation\*}
Take any continuous function $h$ such that $|h|\le c$ for some real $c>0$, and then take any real $\ep>0$. Then for some real $\de>0$ we have $|h-h(a)|<\ep$ on $B\_a(2\de)$. So,
\begin{equation\*}
 \Big|\int\_{B\_a(2\de)} hp-\int\_{B\_a(2\de)} h(a)p\Big|\le\ep\int\_{B\_a(2\de)}p\le\ep. \tag{4}\label{4}
\end{equation\*}
For $\tau>0$,
\begin{equation\*}
 C\_\tau\ge\int\_{B\_a(\de)} e^{\tau f}q\ge e^{\tau I(\de)}Q(B\_a(\de)).
\end{equation\*}
So,
\begin{equation\*}
 \int\_{B\_a(2\de)^c}|h|p\le c\int\_{B\_a(2\de)^c}e^{\tau f}q/C\_\tau
 \le c e^{\tau S(\de)}/C\_\tau
 \le\frac c{Q(B\_a(\de))}\, e^{\tau(S(\de)-I(\de))}\to0, \tag{5}\label{5}
\end{equation\*}
in view of \eqref{2} and the condition $\tau\to\infty$.
Similarly (or in particular),
\begin{equation\*}
 \int\_{B\_a(2\de)^c}|h(a)|p\to0. \tag{6}\label{6}
\end{equation\*}
Collecting \eqref{4}, \eqref{5}, and \eqref{6}, we see that $\int hp\to\int h(a)p=h(a)$, for any bounded continuous function $h$. That is, $P\to\de\_a$ weakly, that is, $LP(P,\de\_a)\to0$.


So, in view of \eqref{3}, we get $LP(P\_{x^\*},P)\to0$. If now $\hat P^\*\_n$ is the empirical distribution based on an iid sample of size $n$ from the distribution $P\_{x^\*}$ of $x^\*$, then
$LP(\hat P^\*\_n,P\_{x^\*})\to0$ almost surely (a.s.), in view of the condition $n\to\infty$.


We conclude that $LP(\hat P^\*\_n,P)\to0$ a.s., as desired. More precisely,
\begin{equation}
 \lim\_{\tau,m\to\infty}\,\lim\_{n\to\infty}LP(\hat P^\*\_n,P\_{x^\*})=0 \tag{7}\label{7} 
\end{equation}
a.s.




---


With some regularity assumptions on $f$ and $q$, conclusion \eqref{7} will hold if $f$ has more than one $q$-essential points of maximum.


Indeed, suppose that


* (i) the functions $q$ and $f$ are defined on $\R$;
* (ii)
\begin{equation\*}
 M:=\max f\in\R,\quad \{x\colon f(x)=M\}=\{a\_1,\dots,a\_k\}
\end{equation\*}
for some distinct $a\_1,\dots,a\_k$;
* (iii) for some $\de\_0>0$ the function $f$ is twice continuously differentiable on the set $U\_{\de\_0}$, where
\begin{equation\*}
 U\_\de:=\bigcup\_{j\in[k]}B\_{a\_j}(\de); 
\end{equation\*}
* (iv)
\begin{equation\*}
 c\_j:=-f''(a\_j)>0
\end{equation\*}
for all $j\in[k]:=\{1,\dots,k\}$;
* (v) for each real $\de>0$ there is some real $\ep>0$ such that
\begin{equation\*}
 f<M-\ep \quad\text{on } U\_\de^c; 
\end{equation\*}
* (vi) the function $q$ is continuous and strictly positive on $U\_{\de\_0}$.


$$\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*$$


By (ii), (iii), and (iv), for each $j\in[k]$ and all $x\in B\_{a\_j}(\de\_0)$ we have
\begin{equation\*}
f(x)=M-(c\_j+o(1))(x-a\_j)^2/2 \tag{8}\label{8}
\end{equation\*}
as $x\to a\_j$. So, taking also (v) into account, for all $y<M$ close enough to $M$ we have
\begin{equation\*}
 \{x\colon f(x)\ge y\}=\bigcup\_{j\in[k]}[x\_{j-}(y),x\_{j+}(y)] \tag{9}\label{9}
\end{equation\*}
for some real $x\_{j\pm}(y)$'s such that
\begin{equation\*}
 x\_{j\pm}(y)=a\_j\pm\sqrt{\frac{2(M-y)}{c\_j+o(1)}} \tag{10}\label{10}
\end{equation\*}
for each $j\in[k]$ as $y\uparrow M$.


Since $x\_1,\dots,x\_m$ are iid each with pdf $q$, for all real $\de>0$ we have
\begin{equation\*}
\begin{aligned}
 \Pr\nolimits\_Q(x^\*\in B\_{a\_1}(\de))&=\int\_{B\_{a\_1}(\de)}\Pr\nolimits\_Q(x^\*\in dx) \\ 
 &=m\int\_{B\_{a\_1}(\de)}\Pr\nolimits\_Q(x\_1\in dx,\,f(x)>f(x\_j)\ \forall j\ge2) \\ 
 &=m\int\_{B\_{a\_1}(\de)}\Pr\nolimits\_Q(x\_1\in dx)\,\Pr\nolimits\_Q(f(x)>f(x\_2))^{m-1} \\ 
 &=m\int\_{B\_{a\_1}(\de)}dx\,q(x)\,\Pr\nolimits\_Q(f(x)>f(x\_2))^{m-1} \\ 
 &=m(q(a\_1)+o\_\de(1))\int\_{B\_{a\_1}(\de)}dx\,\Pr\nolimits\_Q(f(x)>f(x\_2))^{m-1}, 
\end{aligned} 
\end{equation\*}
where $o\_\de(1)\to0$ as $\de\downarrow0$.
By \eqref{9}, (vi), \eqref{10}, and \eqref{8}, for all small enough $\de>0$ and $x\in B\_{a\_1}(\de)$ we have  

\begin{equation\*}
\begin{aligned}
 1-\Pr\nolimits\_Q(f(x)>f(x\_2))&=\sum\_{j\in[k]}Q([x\_{j-}(f(x)),x\_{j+}(f(x))] \\ 
 &\sim\sum\_{j\in[k]}q(a\_j) (x\_{j+}(f(x))-x\_{j-}(f(x))) \\ 
 &\sim\sum\_{j\in[k]}q(a\_j) 2\sqrt{\frac{c\_1}{c\_j}}\,|x-a\_1| \\ 
 &=C\sqrt{c\_1}\,|x-a\_1| 
\end{aligned}
\end{equation\*}
as $x\to a\_1$, where
\begin{equation\*}
 C:=\sum\_{j\in[k]}2\sqrt{\frac1{c\_j}}\, q(a\_j). 
\end{equation\*}
So, for $m\to\infty$ (and $\de\downarrow0$ slowly enough)
\begin{equation\*}
\begin{aligned}
&\Pr\nolimits\_Q(x^\*\in B\_{a\_1}(\de))\\ 
&=m(q(a\_1)+o\_\de(1))
\int\_{B\_{a\_1}(\de)}dx\,\exp\Big(-\frac{m-1}{2+o\_\de(1)}\,C\sqrt{c\_1}\,|x-a\_1|\Big) \\ 
&\sim(m-1)q(a\_1)
\int\_\R dx\,\exp\Big(-\frac{m-1}{2+o\_\de(1)}\,C\sqrt{c\_1}\,|x-a\_1|\Big) \\ 
&\sim \frac{2\,q(a\_1)/\sqrt{c\_1}}C =p\_1, 
\end{aligned}
\end{equation\*}
where
\begin{equation\*}
 p\_i:=\frac{q(a\_i)}{\sqrt{c\_i}}\Big/\sum\_{j\in[k]}\frac{q(a\_j)}{\sqrt{c\_j}}. \tag{11}\label{11}
\end{equation\*}
Similarly, for $m\to\infty$ (and $\de\downarrow0$ slowly enough)
\begin{equation\*}
 \Pr\nolimits\_Q(x^\*\in B\_{a\_i}(\de))\to p\_i
\end{equation\*}
for each $i\in[k]$.  

So, for the distribution $P\_{x^\*}$ of $x^\*$ we have
\begin{equation\*}
 LP\Big(P\_{x^\*},\sum\_{j\in[k]}p\_j\de\_{a\_j}\Big)\to0 \tag{12}\label{12}
\end{equation\*}
as $m\to\infty$.


On the other hand, for $C\_\tau$ as in \eqref{3.5}, in view of (vi) and \eqref{8}, for $\tau\to\infty$ (and $\de\downarrow0$ slowly enough)
\begin{equation\*}
\begin{aligned}
 P(B\_{a\_1}(\de))&=\frac1{C\_\tau}\,\int\_{B\_{a\_1}(\de)}e^{\tau f}q \\ 
 &\sim\frac{q(a\_1)}{C\_\tau}\,
 \int\_{B\_{a\_1}(\de)}dx\,\exp\Big(\tau M-\tau\,(c\_1+o\_\de(1))(x-a\_1)^2/2\Big) \\ 
 &\sim\frac{q(a\_1)}{C\_\tau}\,e^{\tau M}
 \int\_\R dx\,\exp\Big(-\tau\,(c\_1+o\_\de(1))(x-a\_1)^2/2\Big) \\ 
 &\sim\frac{q(a\_1)}{C\_\tau}\,e^{\tau M}
 \frac{\sqrt{2\pi}}{\sqrt{c\_1\tau}}. 
\end{aligned} 
\end{equation\*}
Similarly, for $\tau\to\infty$ (and $\de\downarrow0$ slowly enough)
\begin{equation\*}
 P(B\_{a\_i}(\de))\sim\frac{q(a\_i)}{C\_\tau}\,e^{\tau M}
 \frac{\sqrt{2\pi}}{\sqrt{c\_i\tau}} 
\end{equation\*}
for each $i\in[k]$.
Also, by (v), for each real $\de>0$ there is some real $\ep>0$ such that
\begin{equation\*}
 P(U(\de)^c)\le\frac{e^{\tau(M-\ep)}}{C\_\tau}=o\Big(\frac{e^{\tau M}}{C\_\tau\sqrt\tau}\Big) 
\end{equation\*}
$\tau\to\infty$ (and $\de\downarrow0$ slowly enough).
So, in view of \eqref{11},
\begin{equation\*}
 LP\Big(P,\sum\_{j\in[k]}p\_j\de\_{a\_j}\Big)\to0 \tag{13}\label{13}
\end{equation\*}
as $\tau\to\infty$.
By \eqref{12} and \eqref{13}, $LP(P\_{x^\*},P)\to0$ as $m,\tau\to\infty$. Thus, \eqref{7} again follows, indeed.


