This (old) post details how to interfere with randomness to make it feel more random to the end user.
This reminded me of how many games “cheat” in a similar way to make critical hits seem more fair (increase the probability when it has not triggered for too long and decrease it when it just triggered)
I don’t know this for sure, but I think it’s something along the lines of certain record companies can pay to have their artists played more often than others so when you start a playlist on shuffle it’s biased toward those higher “tier” songs. I think caches also plays into it to a degree, but it’s definitely not just an issue with a lack of randomness. I think they do the same thing with the “AI DJ” which will play completely irrelevant songs to your tastes in a small group and then go back to normal at intervals. “Hey this is your DJ X, you just heard Kat Stevens so now I’m gonna play Kendrick Lamar (which you’ve never once played willingly) and I’ll be following that with a few other things that are currently being promoted”
In my case, I had local music synced up in a playlist, and the playlist still did shuffle though my music. (which Spotify didn’t know the artist of given that it wasn’t part of their library.) The broken shuffle was just one of many reasons why I stopped using streaming and went with local music players back in the day.