I don't think my iPod, when set on "random" is truly random. In fact, I think it's screwing with me.
Google "ipod," "playlist" and "random" sometime and you'll find thousands of postings from people who say something like "my iPod always plays Pink Floyd," or "it always plays the same song." We don't know who these people are - they could have no idea about the rules of statistics, like people who play the lottery or people who thought John McCain ever had a chance to win the 2008 Presidential election at ANY time after he locked up the nomination.
One must bring evidence into the discussion. Saying that your iPod always plays Pink Floyd when you have a hundred Pink Floyd songs and only 500 total gives us a "duh" moment. Likewise, if you notice the same song "all the time," we have to ask how many songs do you have in total, how many do you play each time when it repeats and how many times have you repeated the scenario? This argument usually shrinks away upon analysis.
However, when I first started using my iPod at work, I had about 4000 songs on it. I would hit random play and hear about 80 songs a day, or about 2% of the library. During the first weeks, I thought I heard several songs more often than others. Knowing a little about probability, I didn't think it significant. After all, playing 400 songs a week and restarting the play no less than five times means that the odds of repeating several songs each week would be pretty high.
It became an annoyance one week when I heard the same Bangles song three days in a row. Love the Bangles; can't listen to "Bell Jar" every day. So I created a smart playlist. Essentially, I took my entire library and used one rule: exclude songs played in the last three months. Simple. No hearing the same same song on successive days. I vary the exclusion by whim - generally from as low as 11 weeks to as high as five months. These days, I also filter out christmas songs when it's not christmastime, etc, but it's a low effort playlist. Every day, it adds about the same number of songs I listened to the day before.
Since my main playlist doesn't allow immediate repetition, here's where I get to say my iPod isn't truly random. Let's say, on average, I have 2000 songs in the playlist. I have, at most, 20 songs by any artist in the list. If any repeat during the day, the chance is 2 of 2000 in a subset of 80. Not impossible. But on recent days, I heard a song by Paul McCartney followed by a song by The Beatles (McCartney singing) followed by a song by Wings. Not statistically relevant but come on. The next day, I heard a song by Led Zeppelin (lead singer: Robert Plant) followed by a song by Robert Plant followed by a song by The Honeydripers (lead singer: Robert Plant). I can't prove it but deep down, you gotta believe the Apple engineers are screwing with us.