Why is iPhone Shuffle not really random?

Theorectically, if Shuffle were truly random (computers are only capable of pseudo-randomness), you could hear every album you have in track order. It is unlikely but no more unlikely than any other combination of songs. What you want is not truly random, you want a more even mixture. Once upon a time, there was a setting in iTunes that made shuffle less random by creating a better mix. I don't recall if it's still there or if it carried over, in any way, to iOS devices.

https://itunes.apple.com/app/true-shuffle-pro/id355913111?mt=8

You're welcome.

This issue is a perennial issue which has never been resolved. Using an add-on App may improve the experience for some but does not resolve the issue. The True Shuffle Pro "solution" doesn't address the overall issue of shuffling your entire music collection across several devices.

Let's take another case. Say you primarily use an iPod running iOS 2.0 or earlier. Apple currently sells three different styles of iPods that won't run True Shuffle Pro to hack the issue discussed here. Meg was pointing out that while "true" randomness wouldn't be expected, the annoying state of Shuffle is that even if you left that one iPod Classic playing for a year and you had over 100G of music on it you could expect to hear some songs consistently — on some days two or three times in the same day — where other songs would NEVER get selected.

Some have suggested resetting the counters, but besides being another ineffective hack, it entirely misses the point. I think if the Apple iTunes developers tried, they could develop a solution to a 10+ year issue.