simulation.Rmd

---
title: "Simulation"
author: "Dave Tang"
date: "`r Sys.Date()`"
output:
  workflowr::wflow_html:
    toc: false
editor_options:
  chunk_output_type: console
---

```{r setup, include=FALSE}
options(scipen=10000)
```

[Monte Carlo simulation](https://en.wikipedia.org/wiki/Monte_Carlo_method) are useful for estimating probablities and relies on repeated random sampling to generate a probability distribution. You may have heard of the [Monty Hall problem](https://en.wikipedia.org/wiki/Monty_Hall_problem): 

    Suppose you're on a game show, and you're given the choice of three doors: Behind one door is a car; behind the others, goats. You pick a door, say No. 1, and the host, who knows what's behind the doors, opens another door, say No. 3, which has a goat. He then says to you, "Do you want to pick door No. 2?" Is it to your advantage to switch your choice?

Let's simulate the Monty Hall problem 50,000 times each, for **not switching** and for **switching** to see if it is advantageous to switch.

```{r monty_hall_simulation}
monty_hall_game <- function(switch = TRUE){
  # randomly assign what's behind the three doors
  doors <- 1:3
  behind <- sample(c("car", "goat", "goat"))
  door_car <- doors[behind == "car"]
  
  # randomly pick a door
  my_pick <- sample(doors, 1)
  
  # if we picked the door with the car, randomly show one of the doors with the goat
  if(my_pick == door_car){
    door_show <- sample(doors[-my_pick], 1)
  # if we picked a door with a goat, show the door with the other goat
  } else {
    door_show <- doors[-c(my_pick, door_car)]
  }
  
  # if we choose to switch
  if(switch == TRUE){
    final_pick <- doors[-c(my_pick, door_show)]
  # if we stick with our original pick
  } else {
    final_pick <- my_pick
  }
  
  final_pick == door_car
}

num_rep <- 50000

result_no_switch <- replicate(num_rep, monty_hall_game(FALSE))
result_switch <- replicate(num_rep, monty_hall_game(TRUE))

paste0("If we stick with our original choice, our success rate is ", mean(result_no_switch) * 100, "% in ", num_rep, " tests.")
paste0("If we switch from our original choice, our success rate is ", mean(result_switch) * 100, "% in ", num_rep, " tests.")
```

From the Monte Carlo simulation, we see that if we don't switch, we get the door with the prize (car) 33% of the time. This makes sense because if we disregard the switch, there is a 1/3 chance of picking the prize. If we make the switch, we get the door with the prize 66% of the time! This also makes sense because before the switch, there is a 33% chance of getting the prize door. Therefore 66% of the time, the prize door is among the other two doors that you didn't pick. When the host opens the non-prize door (out of the two you didn't pick), the remaining door has a 66% chance of being the prize door.

The [Secretary problem](https://en.wikipedia.org/wiki/Secretary_problem) is defined as follows:

    Imagine an administrator who wants to hire the best secretary out of n rankable applicants for a position. The applicants are interviewed one by one in random order. A decision about each particular applicant is to be made immediately after the interview. Once rejected, an applicant cannot be recalled. During the interview, the administrator gains information sufficient to rank the applicant among all applicants interviewed so far, but is unaware of the quality of yet unseen applicants. The question is about the optimal strategy (stopping rule) to maximise the probability of selecting the best applicant. If the decision can be deferred to the end, this can be solved by the simple maximum selection algorithm of tracking the running maximum (and who achieved it), and selecting the overall maximum at the end. The difficulty is that the decision must be made immediately.

The optimal stopping rule prescribes always rejecting the first $n/e$ (`r 1/exp(1)*100`%) applicants that are interviewed and then stopping at the first applicant who is better than every applicant interviewed so far (or continuing to the last applicant if this never occurs).

```{r secretary_problem}
optimal_stopping <- function(n = 100, perc = 37){
  # create pool of randomly arranged numbers
  # where n is the best applicant, e.g. for n = 100, 100 is the best
  my_pool <- sample(1:n)
  # percentage of pool to use for comparison, i.e. reject set
  my_cutoff <- floor(perc * n / 100)
  # create comparison set
  my_comp_set <- my_pool[1:my_cutoff]
  # best applicant in the comparison set
  my_comp_best <- max(my_comp_set)
  # if the best applicant is included in the comparison set
  # then we have missed hiring the best applicant
  if(my_comp_best == n){
    return(FALSE)
  }
  # create set to search for best applicant
  my_hire_set <- my_pool[(my_cutoff+1):n]
  # applicants that are better than the best applicant in the comparison set
  my_hire_better <- my_hire_set > my_comp_best
  # first applicant that is better than the best applicant in the comparison set
  my_hire_best <- my_hire_set[min(which(my_hire_better))]
  # is this the best applicant?
  my_hire_best == n
}

num_rep <- 50000
pool_size <- 1000

start_time <- Sys.time()
perc_to_test <- 10:60
tests <- lapply(X = perc_to_test, FUN = function(x){
  replicate(num_rep, optimal_stopping(n = pool_size, perc = x))
})
end_time <- Sys.time()
end_time - start_time

test_means <- sapply(tests, mean)
names(test_means) <- perc_to_test

my_col <- (test_means == max(test_means)) + 1
barplot(test_means,
        xlab = "Percent to reject",
        ylab = "Percent success",
        cex.names = 0.5,
        cex.axis = 0.5,
        las = 2, ylim = c(0, .4),
        col = my_col,
        main = paste0("Maximum success percent: ", max(test_means)))
abline(h = max(test_means), lty = 2, col = "red")
```

We ran simulations with a hiring pool size of `r pool_size` applicants and repeated the optimal stopping strategy `r num_rep` times at a range of percentages: `r range(perc_to_test)`. We can see that the optimal solution is to reject around `r 100/exp(1)`% ($n/e$) of the total number of applicants and to use them as a comparative set.