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!
