Finite rejection sampler for a linear combination

Inputs: an integer $k\ge 1$, vectors $v_1,\dots ,v_k\in {\mathbb{R}}^n$ with ℓ2 sample/query access, real coefficients $w_1,\dots ,w_k$, and a positive integer cap $R$. Set $x={\sum }_{j=1}^k{w}_j{v}_j$ and $S={\sum }_{j=1}^k\mathrm{\parallel }{w}_j{v}_j{\mathrm{\parallel }}_2^2$. Output: an index $i\in [n]$ or FAIL.

If $S=0$, return FAIL. Otherwise, for each of at most $R$ trials:

1. Using fresh randomness, choose $j$ with probability $\mathrm{\parallel }{w}_j{v}_j{\mathrm{\parallel }}_2^2\mathrm{/}S$, then sample $i$ from $D_{v_j}$. A zero-weight term is never chosen, so every requested vector distribution is defined.
2. Query all $v_{h,i}$ and set $a_i:=\{\begin{array}{ll}{\displaystyle \frac{(\sum _{h=1}^k{w}_h{v}_{h,i}{)}^2}{k\sum _{h=1}^k(w_h{v}_{h,i}{)}^2}},& {\sum }_h(w_h{v}_{h,i}{)}^2>0,\\ 0,& {\sum }_h(w_h{v}_{h,i}{)}^2=0.\end{array}$ By Cauchy--Schwarz, $0\le a_i\le 1$, so this is a valid acceptance probability.
3. With a fresh independent acceptance coin, accept index $i$ with probability $a_i$ and return $i$ upon acceptance.

If all $R$ trials reject, return FAIL. When $x=0$ but $S>0$, every defined acceptance probability is zero and the cap still forces a finite FAIL output. No normalized target distribution is assigned when $x=0$. All samples, entry queries, random bits, cap, and output writing are charged. Correctness and cost of the linear-combination sampler ↗ proves the target law on the accepted branch and the failure and query bounds under its separate hypotheses on $x$, the cancellation ratio, and $R$.