Как сгенерировать случайное число из указанного дискретного распределения?

Допустим, у нас есть какое-то дискретное распределение с конечным числом возможных результатов, возможно ли сгенерировать случайное число из этого распределения быстрее, чем за O (logn), где n - количество возможных результатов?

Как сделать это за O (logn):
- Создать массив с кумулятивной вероятностью (Array [i] = вероятность того, что случайное число будет меньше или равно i)
- Сгенерировать случайное число из равномерного распределения (обозначим его k)
- Найдите наименьшее i такое, что k - i - наше случайное число.