Получить случайный элемент из последовательной коллекции

Я разговариваю с API, который дает мне java.util.Iterator поверх коллекции. Это означает, что я могу перебирать его, но я не могу получить прямой / произвольный доступ к элементам.

Теперь к моей проблеме: я хочу получить один случайный элемент из этой коллекции. Как мне это сделать? Думаю, я мог бы создать новую коллекцию, которая обеспечивает прямой доступ, но разве это не потребляет немного памяти? Я также мог бы перебрать всю коллекцию и для каждого элемента «бросить кубик», чтобы увидеть, следует ли мне взять этот элемент и выйти из итерации или продолжить. Но тогда мне нужен размер коллекции, а я не могу получить его от Iterator.

Заранее спасибо.