Data & Statistics

At Least One

How many times do we need to throw two dice to have a 50% chance of getting at least double-six? We have seen several of these “at least” problems. The magic of solving those problems is to find out the probability of no chance and then apply the AND rule (the joint probability).

The probability of rolling a double-six is (1/36), and that for no double-six is (35/36). It is because there are 36 total combinations possible once you roll two dice, and one of them is the desired.

Let n be the number of rolls for the desired outcome. The probability to have n events producing no double-six is (35/36)n, which is then equated to 0.5 for 50% probability. Solve the equation for n; (35/36)n = 0.5 or n ln(35/36) = ln(0.5). n = ln(0.5)/ln(35/36) = 24.5 ~ 25 rolls.

At Least One Read More »

The Aeroplane Boarding Problem – R Code

We have seen the aeroplane boarding problem in the previous post. Let’s try and verify that using an R program. Here is the code:

x_rand <- c(1,2,3,4,5,6,7)

f_seat <- sample(x_rand, size = 1)
x_rand <- x_rand[-f_seat]
print(paste0(" Firat one takes ", f_seat))
print(paste0(x_rand, " remains"))

for (i in 2:6){
  print(paste0("Next one is   ", i))
  if(i %in% x_rand){
    x_rand <- x_rand[-which(x_rand == i)]
     print(paste0(x_rand, " remains"))
  } else {
    n_seat <- sample(x_rand, size = 1) 
    x_rand <- x_rand[-which(x_rand == n_seat)]
    print(paste0(x_rand, " remains"))
  }
}
    print(paste0(x_rand, " Seat for Last"))
    if(x_rand == 7){
      counter = 1
    }else 
      counter = 0

And the output is:

[1] " Firat one takes 5"
[1] "1 remains" "2 remains" "3 remains" "4 remains" "6 remains" "7 remains"
[1] "Next one is   2"
[1] "1 remains" "3 remains" "4 remains" "6 remains" "7 remains"
[1] "Next one is   3"
[1] "1 remains" "4 remains" "6 remains" "7 remains"
[1] "Next one is   4"
[1] "1 remains" "6 remains" "7 remains"
[1] "Next one is   5"
[1] "1 remains" "6 remains"
[1] "Next one is   6"
[1] "1 remains"
[1] "1 Seat for Last"

Now, let us run the code for 100 passengers 10000 times and estimate the proportion for the last passenger to get the last seat.

success <- replicate(10000, {
  x_rand <- seq(1:100)

f_seat <- sample(x_rand, size = 1)
x_rand <- x_rand[-f_seat]

for (i in 2:99){
  
  if(i %in% x_rand){
    x_rand <- x_rand[-which(x_rand == i)]
  } else {

    n_seat <- sample(x_rand, size = 1) 
    x_rand <- x_rand[-which(x_rand == n_seat)]

  }
}
    if(x_rand == 100){
      counter = 1
    }else 
      counter = 0
})
   mean(success)

The answer is 0.5!

The proportion for the last passenger getting seat 1 is also 0.5. Try putting any other; the answer will be zero.

The Aeroplane Boarding Problem – R Code Read More »

The Aeroplane Boarding Problem

One hundred passengers are waiting to board an aircraft. The first passenger forgets her boarding pass and therefore takes a random seat. From here on, the passengers who follow take their own, if available, or take a seat randomly. When the 100th passenger arrives, what is the probability that she gets the right spot?

The answer is a surprising 1/2, and the only seats that remain for the 100th person are the seat of the first person or her correct one. Let’s run this exercise and prove the answer by induction.

Let the seat number of the first person who lost the pass be #37. When she comes inside, she has three possibilities to select (at random).

1) Select her seat, #37: In that case, everyone else, including 100th one, will board correctly.
2) Select the seat of the 100th person, say #13. Here, everyone else will sit correctly, and the last person has #37.
3) Select a random seat other than #37 or #13. She chooses #79.

All other passengers board properly until #79 arrives. She has three choices:

1) Take #37: This is the actual seat of the first passenger. If this happens, then onwards, everyone gets their respective.
2) Take #13. It is the last one’s seat. All others, except the last, get their assigned seat and #37 is available empty for the last one.
3) Take a random one from the remaining seats other than #37 or #13, only for the next unlucky one to repeat the game!

The Aeroplane Boarding Problem Read More »

The Optimal Stopping Strategy

Optimal stopping is a powerful rule in decision-making to maximise the reward. A famous example of strategy is the secretary problem or the fussy suitor problem.

The basic idea is the following. The person wants to choose the best one from a long list of candidates. She can get relevant data (e.g. through an interview process) from each prospect, one at a time. And she must decide to select or reject immediately after the interview. Although the ranking score remains available for reference, she can’t retake the rejected one.

The odds algorithm describes the solution to this problem and says that the probability of finding the optimal solution can be as high as (1/e ~ 37%) by following a methodology. e = 2.718, which is the base of the natural logarithm. The process is simple: if you have n candidates for the selection, give the candidates a score, reject the first n/e of them and then select the one whose score is greater than the greatest of the first n/e!

Let me explain. Imagine there are ten candidates (n = 10). Start the interview and score. Record the highest score of the first three (~ 10/2.718) but reject them all. Then, from the fourth candidate onwards, whoever gets a score more than the previous highest gets selected. The probability for the selected to be the best in the group of ten is about 37%.

We will look at the proof later, but let us run a Monte Carlo that verifies this idea using the following R code. Note this is not an algorithm to find the best, but one way of getting the chance of finding the highest number from a set of randomised numbers.

iter <- 100000

suitor <- replicate(iter, {
  high_number <- 100
  x <- 1:high_number
  x_rand <- sample(x)        

  min_num <- round(high_number/2.71)
  mmx <- max(x_rand[1:min_num])

  next_one <- min_num:high_number

  for (i in next_one){
      if(x_rand[i] > mmx){break}

}

   if(x_rand[i] == high_number){
   counter = 1
   }else{
   counter = 0
   }  
})

mean(suitor)

Here is the plot representing the probability as a function of the number of candidates.

The Optimal Stopping Strategy Read More »

Guessing the Card

Andy and Becky are playing a guessing game. Andy takes a card from a standard 52-card deck. Becky is to guess the card, but she can ask one of the three questions below.

1) Is it a card red?
2) Is the card a face card (J, Q or K)?
3) Is the card an ace of spades?

Which question should Becky ask to maximise the probability of the guess being correct?

Becky may ask any of the above as her winning chance remains the same.

1) Is it a card red?

There is a (1/2) chance of getting a yes answer from Andy. If the answer is yes, Becky can guess 1 of 26 red cards, and if the answer is no, she can guess 1 of 26 black cards.

2) Is the card a face card (J, Q or K)?

The probability of Andy answering yes is 12/52, and no is 40/52. If yes is the answer, Becky can guess the correct one with a probability of (1/12), and for no, it is (1/40). So the overall probability is (12/52) x (1/12) + (40/52) x (1/40) = (1/52)+(1/52) = 1/26.

3) Is the card an ace of spades?

For the last question, the probability of yes is (1/52) and no is (51/52). Correct guessing probability if yes is 1 and if no is (1/51). The overall probability is (1/52) x 1 + (51/52) x (1/51) = 1/26.

Guessing the Card Read More »

Two-Player Monty

In a different version of the Monty Hall problem, two players are playing the game; player one chooses a door and then player two another. If the car is behind the door that no one chose, Monty eliminates one of the players at random. If one has chosen the car, Monty eliminates the other player. The survivor knows that the other was eliminated, but not the reason. Should the survivor switch?

There are multiple ways of understanding this probability. One is to follow the three possibilities
1) Player 1 selects the car, and Monty will eliminate player 2. Switching is bad
2) Player 2 selects the car, and Monty will eliminate player 1. Switching is bad.
3) None picks the car, and Monty eliminates one at random. Switching is good.

It means switching makes sense only in the case when both players select goats. The chance of this happening is one in three; this is another way of saying there is a one-in-three chance of the car not being picked by anybody (three choices are: 1 picks the car, 2 picks the car, none picks).

So here is a Monty Hall problem in which sticking to the original door is the strategy.

Two-Player Monty Read More »

Three prisoners problem

Here is another one: Three prisoners are waiting to be executed in a few days. The authorities have selected one of them at random to be pardoned, and the warden knows who.

One of the prisoners, prisoner A, begs the warden to name one to be executed from the other two. Finally, the warden relents and says it is C. Prisoner A is happy now, thinking his probability of survival has increased from one-third to half. He then secretly tells the news to B. B is super happy, as he thinks his chance has doubled from one-third to two-thirds! Who is right here?

Remember the Monty Hall problem? This one is just another version of that. In other words, A’s chance of survival remained the same (1/3) even after the new information, whereas B’s chance doubled to two in three.

Three prisoners problem Read More »

A Pair of Aces

Here is a simple probability problem that can baffle some of you. I have two decks of well-shuffled cards on the table. Take out the top card of each pack. What is the probability that at least one card is an ace of spade?

The probability of finding an ace of spades from the first deck is 1 in 52 and the same in the second deck is 1/52. Since the two decks are independent, you add the probability, i.e., 2/52 = 1/26. Right? Well, the answer is not correct! So what about (1/52)x(1/52) = 0.00037? That is something else; the probability of finding both the top cards is aces of spades. But we are interested in at least one.

You obtain the correct answer as follows:
The probability of finding no ace of spades on the top of the first deck is 51/52. The same is the chance of seeing none from the second deck. Therefore, the probability of catching no ace of spades from either deck is (51/52)x(51/52). The probability of obtaining at least one equals 1 – the probability of getting none. So, it is 1 – (51/52)x(51/52) = (52 x 52 – 51 x 51)/ (52 x 52) = 103/2704 = 0.0381.

Another way of understanding this probability is to estimate all the possible ways of pairing two cards, one from each deck, containing at least one ace of spades and then dividing it by the total number of pairs. Taking an ace from the first deck, you can have 52 combinations from the second and vice versa. So there are 52 + 52 = 104 combinations. Then you have to remove the double counting two aces, reaching 103. The total number of pairs is 52 x 52 = 2704. That leaves the required quantity to be 103/2704.

The Monty Hall Problem: Jason Rosenhouse

A Pair of Aces Read More »

Waiting for a Car

If the probability of finding at least one car on the road in 30 minutes is 95%, what is the chance of finding at least one car in 10 minutes?

Let p be the probability of not finding a car in 10 minutes so that the required probability, the probability of finding at least one car in 10 minutes, is 1- p.

The probability of finding no car in 30 minutes is a joint probability of three consecutive intervals of 10 minutes each of no cars. I.e., p x p x p = p3. But this is equivalent to 1 – the probability of finding at least one car in 30 minutes. In other words 1 – p3 = 0.95. p = cube root of (1 – 0.95) = 0.368.

So, the required probability, (1 – p) becomes 1 – 0.368 = 0.63 or 63%

Waiting for a Car Read More »

Evolution of Cooperation

The foundation of cooperation is not really trust, but the durability of the relationship

Robert Axelrod, The Evolution of Cooperation

We have seen the right strategy for the basic prisoner’s dilemma problem with one play. Defect, and get the better incentive no matter what the other player does. But when it comes to an infinite game, where the same two players play several games, there can be strategies that can make better payoffs than just defect, defect, defect!

University of Michigan Professor of Political Science and Public Policy Robert Axelrod invited experts from game theory to submit programs for a computer infinite prisoner’s dilemma game. Prof Axelrod would then pair off the strategies and find the winner. The winning design was the so-called Tit for Tat, in which the player starts with cooperation and then mirrors what the other player does.

Reciprocation

Let’s see five games between A and B in which A follows the Tit for Tat method. The payoff is similar to what we have seen in the previous post.

As expected, A starts with cooperation but, seeing B defected, changes to defect in the second game. B realises that and continues cooperating, leading to 13 points for each.

Here is the game with two Tit-for-Tat gamers, both starting with cooperation.

Very peaceful game, and each ends up with 15 points. Imagine the same game, but, for some reason, B starts with a defection.

The payoffs are fine; each defector gets five each time, but the games will follow an alternative pattern.

Evolution of Cooperation Read More »