Science Focus (issue 022)

sample, and we’re willing to jump to conclusions based on those patterns [3]. Shuffling in Real World: Fisher – Yates Shuffle vs. Naïve Method Take the Fisher–Yates shuffle [2], which shuffles a sequence randomly based on the input of other random number s . Let’s say there i s an ex i s t ing sequence of the numbers 1 to 10. First pick a random number from 1 to 10, called n, and remove the nth number in the existing sequence to begin a new sequence. For the next numbers, repeat this with any n from 1 to 9, from 1 to 8, and so on, until there are no numbers left in the existing sequence (see Figure 1). This sequence is totally random if the choices of n are also random, and in a moment, we’ll look at why this is true. We can think about the algorithm in terms of a deck of cards, removing random cards one at a time and stacking up the discarded cards in order to form a new deck. Comparing this with other ways to shuffle cards makes it obvious why Fisher–Yates is truly random. A “naïve” method is to take each card in sequence one at a time and swap it with another randomly chosen card, repeating for every card in the deck [4]. In other words, if we shuffle three cards (marked #1, #2, and #3) using our naïve method, we first swap the first card in the sequence with either the first (unchanged), second or third card. Then we shuffle the second card with either one of the three cards, and repeat the process until we go through every position in the sequence. The random choice at every stage is between three cards, so shuffling three times gives 3 x 3 x 3 = 33 = 27 By Peace Foo 胡適之 A coin comes up heads five times in a row. Two accidents happen on the same train line in one day. Or a shuffled playlist plays you the same artist three times running. Sometimes it seems like something other than coincidence is at work, but true randomness may not always feel that way to us. Statistically Independent Events: The Coin Doesn’t Remember! Let’s start with the coins. Many people expect a fair coin to alternate between heads and tails and will be surprised if the coin keeps coming up heads. When you first thought about it, you might have expected heads to come up half the time and tails half the time, so if heads have come up over half the time the coin should start landing on tails more often to compensate. This isn’t true, of course, because the coin can’t remember this! If you have a fair coin which has just landed on heads 99 times in a row, you can’t say that it’s more likely to land on tails next time because it’s a fair coin [1]. Since each toss has no effect on the next, we say that they are statistically independent events. If we toss a coin twice, and each toss has an equal chance of heads (H) or tails (T), there are four possible outcomes: HH, HT, TH, TT. Each outcome has the same chance (1/4) of happening, but the chances of one head and one tail in either order are 2/4 instead of 1/4. Three times, and we have eight possible outcomes: HHH, HHT, HTH, HTT, THH, TTH, THT, and TTT, each with 1/8 probabi l ity. In a ser ies of ten tosses, the results HTHTHTHTHT and HHTHTTTTHT and TTTTTTTTTT all have the same chance of occurring – one in 210, or 1/1024 – but you’ll probably remember the last one and not the others [2]. We read too much into patterns in a random Shuffle Playlist. Shuffle Playlist. Shuffle Playlist… 這個隨機播放清單…… 不太隨機!