===== Background on the issue
RandomInCategory uses the `cl_timestamp` field to draw a random page. Because this field is not uniformly distributed it also uses some additional logic to make all entries likely to be drawn but for small- to medium-size categories (think hundred of pages, not tens of thousands) this does not seem to work.
===== Impacted use cases
On enwiki: The draft review process on en uses [[:Category:Pending AfC submissions]] to keep track of all the drafts awaiting review, and Special:RandomInCategory to let reviewers pick the next draft to work on. The problem is, the results are very much non-random. See [[ https://en.wikipedia.org/w/index.php?title=Wikipedia:Village_pump_(technical)&oldid=911424503#Picking_a_draft_to_review:_RandomInCategory_isn't_very_random | this Village Pump thread ]] for my analysis of the problem.
On Commons: I (DerHexer) use RandomInCategory for some of the categories on Commons of images which I uploaded, bookmarked in my browser. E.g. [[https://commons.wikimedia.org/wiki/Special:RandomInCategory/Files_by_DerHexer/Internationales_Deutsches_Turnfest_Berlin_2017|this]], even more obvious in smaller categories like [[https://commons.wikimedia.org/wiki/Special:RandomInCategory/Elisabeth_Seitz_at_Internationales_Deutsches_Turnfest_Berlin_2017|this]]. Unlike expected, I do not get random images but some very often, sometimes even in the similar order when I click the bookmark, sometimes it opens only subcategories but not files. How can this happen? The function is very helpful and I would very much appreciate to promote this onwiki but this broken I am a bit hesitant.