Probability of choosing an element in an array I'm working on a randomized algorithm question that essentially applies rejection sampling, but I'm mostly struggling with the proof of a specific probability part in the algorithm.
Consider a vector $v \in \mathbb{R}^n$. Let $v_i$ denote a weight. Let $v_i \in [a, b]$, where $a$ and $b$ are positive lower and upper bounds, respectively.
We would like to choose some $v_i$ such that $i \in \{1,2,\ldots, n\}$ with probability $\frac{v_i}{\sum_{i=1}^n v_i}$. That is, we're performing weighted sampling.
An algorithm for doing so is to randomly sample an index with uniform probability. e.g., let $j$ denote the sampled index, then we sample $j \sim U(1, n)$. After we sample this index, we then sample a value $t \sim U(0, b)$. If $v_j > t$, we have found our element. If not, then we repeat the sampling of $j$ and $t$. Until we find a pair such that $v_j > t$.
So for a given iteration, the probability of deleting the $i$-th element is $\frac{1}{n}\frac{v_i}{b}$. It appears that this is independent of $a$.
I believe that the probability of succeeding in an iteration in picking an element in a single iteration is $\frac{1}{n} \sum_{i=1}^n \frac{v_i}{b}$, because if we define $E$ to be the probability of success (picking a $j$ and $t$ that satisfies the criteria) and $c_i$ be the event of choosing the $i$-th index, then we have
$$
P(E) = \sum_{i=1}^n P(E|c_i)p(c_i) = \frac{1}{n} \sum_{i=1}^n P(E|c_i) = \frac{1}{n} \sum_{i=1}^n \frac{v_i}{b} 
$$
This is where I'm getting stuck. Apparently, the probability should be $\frac{a}{b}$. This is totally different from my expression as it is independent of $n$ and dependent on $a$. What is wrong with my thought process?
 A: $P(E)$ must be strictly greater-than $\frac{a}{b}$ if any $v_i>a$; it can't be exactly $\frac{a}{b}$.
$t<a$ is an automatic success because $v_j\geq a$, which means there is an $\frac{a}{b}$ chance of success even before looking at $v_j$, and still a non-zero chance otherwise if $v_j>a$.
There is a $\frac{b-a}{b}\frac{v_j-a}{b-a}=\frac{v_j-a}{b}$ chance of success with $t\geq a$. So, your per-iteration probability for the $i$th element is $\frac{1}{n}\left(\frac{a}{b}+\frac{v_i-a}{b}\right)=\frac{1}{n}\frac{v_i}{b}$. This result is not independent of $a$, because you can't set $v_i<a$. (Framed differently, $\frac{v_i-a}{b-a}$ is only a valid probability if $v_i\in[a,b]$.)
If you substitute $v_i\geq a$ into your final result, you get $\frac{1}{n}\sum_{i=1}^n\frac{a}{b}=\frac{a}{b}$ as a lower bound for $P(E)$, given what is known a priori about $v_i$.
Further, given that all iterations are independent and that you'll iterate until you succeed, you get $P(i)=\frac{v_i}{\sum_{j=1}^n v_j}$ as expected, but again, this is not independent of $b$ because $v_i\leq b$.
