Expectation is a funny thing; we have expectations about how things will change, even if there is no data to suggest it will. We expect the next hand to be a winner after a strong of losses, we expect the roulette table to deliver a black number after a long run of reds and we expect the dice to finally give us a six after a long run of ones and twos. Yet in reality, dice will give a six one in 6 times and a roulette table, a black number one in two (ignoring 0 and 00 for simplicity).
It seems users of iTunes have been having a similar problem with expectation.
If you imagine the list of tracks you have in iTunes, when you play them randomly, they should play in a different order every time. And like the runs of ones and twos in dice, some tracks should come up more frequently than others, perhaps even 3 or 4 times in a row.
When that used to happen, users complained that iTunes was broken - randomness shouldn't behave so oddly. So randomly.
And so at some point a change was made so that when you now press shuffle, the list of tracks is reorganized into a new list to played one by one. That prevents the same track coming up repeatedly. It is less random, but it feels more random to users.
Unfortunately there is a problem with this. iTunes will recreate this list every time it has been played in its entirety. If you have a lot of music, it's unlikely you will get to the end, and so every time you revisit your list, it will still be in the same shuffled order. If you want to recreate 'randomness' each time, turn shuffle off and on again each time you start listening.