Skip to Your Favorite

How Fast Can You Skip To Your Favorite Song?

There are 100 songs on your smart song device. You begin at a random song. You are allowed to push the random button or the next button. The random button will take you to a random song in the 100 song playlist, with a 1% chance that you get the same song that you are on. The next button takes you to the next song.

Your goal is to get to song 42 in as few steps as possible. What is the average number of steps it will take you if you are doing it optimally?

Starting with 20, we will build a simulation that will find the song at which pushing next every time to get to 42 will result in fewer button pushes than had pushing the random button 50% of the time.

GetToFav <- function(X,N){
  Win <- c()
  for(i in 1:N){
  x <- X
  while(x != 42){
    r <- sample(1:100, 1)
    x <- x+1
    if(r>x & r<=42){
      Win <- c(Win,0)
      break
    }
  }
  if(x==42){
      Win <- c(Win,1)
  }
}
return(sum(Win)/N)
}

## Checking a few using 50000 trials
set.seed(42)
GetToFav(29,50000)

## [1] 0.44388

GetToFav(30,50000)

## [1] 0.50242

It seems that if one lands on song 30-41, you want to push next until you arrive at 42, and if you are on song 1-29 or 43-100, you want to push random until you land in the 30-42 range at which point you push next until you get to 42.

With this rule in mind, we build a simulation that follows this rule and counts the number of steps on average it takes to get to 42.

stepAve <- function(N,low){
  stepList <- c()
  for(i in 1:N){
    s <- 1
    x <- sample(1:100, 1)
    while(x != 42){
      if(x %in% low:41){
        s <- s + 42 - x
        x <- 42
      }
      else{
        x <- sample(1:100,1)
        s <- s+1
      }
    }
    stepList <- c(stepList, s)
  }
  hist(stepList)
  return(summary(stepList))
}

set.seed(4200)

print("Simulated average for 29")

## [1] "Simulated average for 29"

stepAve(100000,29)

##    Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
##    1.00    8.00   13.00   13.63   17.00   77.00

print("Simulated average for 30")

## [1] "Simulated average for 30"

stepAve(100000,30)

##    Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
##    1.00    8.00   12.00   13.68   17.00   90.00

print("Simulated average for 31")

## [1] "Simulated average for 31"

stepAve(100000,31)

##    Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
##    1.00    8.00   12.00   13.89   18.00  126.00

By running this function a few times with 100000 as an input with 29, 30, and 31 as low values something bizzare happens. For a low of 29, we see the median increase but the mean decrease! Let’s check 28 as well.

stepAve(100000,28)

##    Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
##    1.00    8.00   13.00   13.66   17.00   70.00

This is another interesting result. Let’s try and do some calculations to make sense of this.

The calculation

Given that we land in the region L-42 for some lower limit value L, the expected number is $$\frac{L+(L+1)+\ldots + 42}{42-L+1} = \frac{42+L}{2} = 21+\frac{L}{2}.$$

If this is the expected number we land on, then the expected number of steps it will take us to reach 42 if we elect to push next until we arrive is $42 - (21 + \frac{L}{2}) = 21 - \frac{L}{2}$.

There are $42-L+1 = 43-L$ integers between L and 42, inclusive. This means that there is a $\frac{43-L}{100}$ probability that pushing random will give you a song in that region. One needs to be familiar with a geometric distribution to understand that the average number of random presses it will take to end up in that region is $\frac{100}{43-L}$.

Thus, if we follow the rule of pressing random until we have a number in L-42, and then push next until we get to 42, then we can expect to make $$f(L) = \frac{100}{43-L} + 21 - \frac{L}{2}$$ button presses.

We want to minimize this function.

library(ggplot2)
library(ggthemes)
f <- function(L){
  return(100/(43-L)+21-L/2)
}

L <- 10:35
Y <- sapply(L, f)
df <- data.frame(L = L, Y=Y)
g <- ggplot(data = df, mapping = aes(x = L, y = Y))
g + geom_line() + labs(title = "Expected Number of Steps vs Lower Limit for *Next*") + theme_fivethirtyeight()

We can see that a minimum occurs at $L=29$, with $f(29) = 13.64286$. Using calculus, one can find that the minimum of this function occurs at $L = 43 - 10\sqrt{2} \approx 28.85786$ which gives a minimum value of 13.64214.