# Generating sequence matching distribution from histogram

One of the developers of lobste.rs recently posted some interesting data showing the distribution of votes and comments for stories on the site. In particular, the posted results give a histogram of the number of stories with a given number of comments/votes rounded to the nearest 10. For example, two stories with a vote count of 7 and 12 would both add to the count of the "10" bin.

This data should allow the creation of a workload generator, a program that produces a sequence of operations that mimic the requests that would be generated by the real site. Such a tool would be very useful for evaluating, e.g., different backend databases for the site. However, this requires some analysis of the data that I can't quite wrap my head around. For clarity, let's focus on the number of votes per story. Specifically, the problem is the following:

Given a count of story IDs with a each number of votes rounded to the nearest 10 (the posted data), produce a sequence of story IDs that approximates the vote proportions in the posted data.

To make it more concrete: if the data was {{0, 10}, {10, 3}, {20, 1}} (so there must be 10+3+1 story IDs), produce a sequence like [a, a, a, b, a, a, c, a, b, d, a, ...] such that the proportion of as is $25/(1\times25 + 3\times15 + 10\times5)$, the proportion of bs is $15/(1\times25 + 3\times*15 + 10\times5)$, and similarly for c and d. e through the last story ID should each appear with probability $5/(1\times25 + 3\times15 + 10\times5)$.

We can produce such a sequence naively if we store a list of (start, id) where start is the total count of votes for all preceeding story IDs. To sample, we pick a random number r in $[0, 1\times25 + 3\times*15 + 10\times5)$, and then choose the id from the item in the list with the smallest start > r. However, this is somewhat slow, as it requires either a binary search or a tree structure. Instead, I want to know if there's a way to do this more efficiently by estimating the distribution that produced the histogram, and then sampling from that distribution?

There are a number of threads on estimating a distribution from a histogram or using fitdistr. There's even one on sampling from a distribution given by a histogram. Along similar lines, this thread on assessing approximate distribution of data based on a histogram has a number of neat examples. But none of these seem (at least to my non-statistician eyes) as though they'd be able to satisfy this particular use-case. At least not in isolation?

I'd love to hear your take on how this problem might be tackled with a more sophisticated solution than my brute-force naive solution above!

• Well, if anyone's interested, I ended up implementing the relatively naive approach here: github.com/jonhoo/histogram-sampler Mar 16, 2018 at 4:37