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.
