Only if the lines are uniformly long, or you have an index to the beginning of each line. The "select a random starting byte" will unfairly bias the lines based on their size (or the size of the line ahead or behind them depending on the algorithm).

-- Randal L. Schwartz, Perl hacker