Grabbing a new song with probabilities weights based on past outcomes is just as "truly random" as picking a new song with a uniform distribution on all songs every time. https://en.wikipedia.org/wiki/Stochastic_process