Setup
Background context, see latest comment on answer dated 'Apr 30 at 20:46'.
You have documents $d_0$ to $d_{n-1}$ each randomly assigned an integer $k$ from the range [0, $2^{64}$), with a new value for $k$ randomly generated for each document.
The documents are arranged in order of lowest $k$ to highest, and in cases of the same $k$ value they are placed in lexicographical order by document name (document names are unique).
Documents are then selected randomly by
- randomly selecting $s$ from the range [0, $2^{64}$)
- randomly selecting a direction $C$ either $≥$ or $≤$
- Selecting document $d_s$ with a value for $k$ closest to $s$ in the direction $C$
- If there are no documents in that direction, repeat selection but with the other direction.
Problem
Given $n > 2$ documents, an ideal distribution of $k$ values would result in the probably of selecting any document being as close to $P(d_a) = 1/n$ as possible.
What is the probably that $k$ values are selected such that the probability of $P(d_a) ≥ 2/n$?