I have an algorithmic problem and I am curious if a solution is known in the literature, because I cannot find it. I came up with an algorithm of my own, but would be curious if something is known.

I have a unimodal sequence of real numbers $x_1, \cdots, x_n$. Assume $n$ is so large I cannot afford time linear in $n$. I know what the mode is. I would like to approximately sample a position in the sequence proportionally to the values. That is, I want to sample $i$ with probability $x_i/\sum_j x_j \pm \delta$ for $\delta$ being some parameter which determines how accurate the sampling should be.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.