I have an array $a$ with $n$ elements, all of which have an associated weight. For example:
$a = \{ (A,2), (B,5), (C,9), ..., (Z,1) \}$, such that element $A$ has weight $w_A=2$, element $B$ has weight $w_B=5$ and so on. The array is not necessarily sorted.
Now, I would like to obtain a sample from this array where each element is selected without repetition and the probability is proportional to the weight of the element.
My goal is to sample approximately $k < n$ elements. I am emphasizing approximately because it does not have to be exactly $k$ but something close to $k$ is good enough. More precisely, I don't care if there is a deviation in the size of the final sample of $\pm \delta$ so long as $\delta$ is not too large in comparison to $k$ or $n$.
I know how to do the sampling in time $O(n + k \log n)$ by computing the cumulative weight $W$, then generating a random value in $[0,W]$ followed by a binary search to check which element this corresponds to.
However, my goal here is to understand whether it is possible to make a sampling in $O(n)$ by defining a probability $p_i$ for each element in such a way that I can decide independently for each element whether it should belong to the sample. Meanwhile, in the end I would still have a sample with approximately the size $k$ that I am looking for. If this is possible, then I could make a single pass in array $a$ after defining the probability $p_i$ accordingly which would require the procedure to define $p_i$'s to be $O(n)$ too, of course.
In summary, my question is: is there a way of defining these probabilities $p_i$ to achieve my goal? Or am I looking for an impossible solution here?