Archive for Monty Hall problem

blind monty hall

Posted in R, Statistics with tags , , , , , , , , on January 10, 2022 by xi'an

As I was waiting for my boat on a French Guiana beach last week, I thought back about a recent riddle from The Riddler where an item does a random walk over a sequence of N integers. Behind doors. The player opens a door at the same rate as the item, door that closes immediately after. What is the fastest strategy to catch the item? With a small value of N, it seemed that repeating the same door twice and moving from 1 to N and backward was eventually uncovering the item.

Here is the cRude code I later wrote to check whether or not this was working:

  p=1+t%%N #starting item position
  h=v=s=m=1 #h=door, v=attempt number, s=direction, m=repeat number
  while(h-p){
    p=ifelse(p==1,2, #no choice
             ifelse(p==N,N-1, #no choice
                    ifelse(p==h-1,p-1, #avoid door
                           ifelse(p==h+1,p+1, #avoid door
                                  p+sample(c(-1,1),1))))) #random
    m=m+1
    if(m>2){
      h=h+s;m=1
      if(h>N){
        h=N-1;s=-1}
      if(!h){
        s=1;h=2}
      }
    v=v+1

and the outcome for N=100 was a maximum equal to 198. The optimal strategy leads to 196 as repeating the extreme doors is not useful.

Monty Hall [몬티 홀 문제는]

Posted in Books, pictures, Statistics with tags , , , , on December 5, 2021 by xi'an

One of the episodes of the K-drama D.P. (for Deserter Pursuit) is entitled the Monty Hall problem and contains a black-board proof of the (correct) change of probability (from one third to two thirds) for the remaining door… Even though the character states that this is based on statistics (!) and that the reason for the inclusion of the scene remains unclear,  within a progressively darker series, depicting the bullying and hazing taking place within a South Korean army unit and the tragic consequences they have on the victims. (Presumably to demonstrate that the deserter was a brilliant student.)

Le Monde puzzle [#1024]

Posted in Books, Kids with tags , , , , , , , on October 10, 2017 by xi'an

The penultimate and appropriately somewhat Monty Hallesque Le Monde mathematical puzzle of the competition!

A dresser with 5×5 drawers contains a single object in one of the 25 drawers. A player opens a drawer at random and, after each choice, the object moves at random to a drawer adjacent to its current location and the drawer chosen by the player remains open. What is the maximum number of drawers one need to open to find the object?

In a dresser with 9 drawers in a line, containing again a single object, the player opens drawers one at a time, after which the open drawer is closed and the object moves to one of the drawers adjacent to its current location. What is the maximum number of drawers one need to open to find the object?

For the first question, setting a pattern of exploration and, given this pattern, simulating a random walk trying to avoid the said pattern as long as possible is feasible, returning a maximum number of steps over many random walks [and hence a lower bound on the true maximum]. As in the following code

sefavyd=function(pater=seq(1,49,2)%%25+1){
  fild=matrix(0,5,5)
  m=pater[1];i=fild[m]=1
  t=sample((1:25)[-m],1)
  nomove=FALSE
  while (!nomove){
   i=i+1
   m=pater[i];fild[m]=1
   if (t==m){ nomove=TRUE}else{
   muv=NULL
   if ((t-1)%%5>0) muv=c(muv,t-1)
   if (t%%5>0) muv=c(muv,t+1)
   if ((t-1)%/%5>0) muv=c(muv,t-5)
   if (t%/%5<4) muv=c(muv,t+5)
   muv=muv[fild[muv]==0]
   nomove=(length(muv)==0)
   if (!nomove) t=sample(rep(muv,2),1)}
  }
  return(i)}

But a direct reasoning starts from the observation that, while two adjacent drawers are not opened, a random walk can, with non-zero probability, switch indefinitely between both drawers. Hence, a sure recovery of the object requires opening one drawer out of two. The minimal number of drawers to open on a 5×5 dresser is 2+3+2+3+2=12. Since in 12 steps, those drawers are all open, spotting the object may require up to 13 steps.

For the second case, unless I [again!] misread the question, whatever pattern one picks for the exploration, there is always a non-zero probability to avoid discovery after an arbitrary number of steps. The [wrong!] answer is thus infinity. To cross-check this reasoning, I wrote the following R code that mimics a random pattern of exploration, associated by an opportunistic random walk that avoids discovery whenever possible (even with very low probability) bu pushing the object towards the centre,

drawl=function(){
  i=1;t=5;nomove=FALSE
  m=sample((1:9)[-t],1)
  while (!nomove){
    nextm=sample((1:9),1)
    muv=c(t-1,t+1)
    muv=muv[(muv>0)&(muv<10)&(muv!=nextm)] 
    nomove=(length(muv)==0)||(i>1e6)
    if (!nomove) t=sample(rep(muv,2),1,
              prob=1/(5.5-rep(muv,2))^4)
    i=i+1}
  return(i)}

which returns unlimited values on repeated runs. However, I was wrong and the R code unable to dismiss my a priori!, as later discussions with Robin and Julien at Paris-Dauphine exhibited ways of terminating the random walk in 18, then 15, then 14 steps! The idea was to push the target to one of the endpoints because it would then have no option but turning back: an opening pattern like 2, 3, 4, 5, 6, 7, 8, 8 would take care of a hidden object starting in an even drawer, while the following 7, 6, 5, 4, 3, 2 openings would terminate any random path starting from an odd drawer. To double check:

grawl=function(){
  len=0;muvz=c(3:8,8:1)
  for (t in 1:9){
    i=1;m=muvz[i];nomove=(t==m)
    while (!nomove){
     i=i+1;m=muvz[i];muv=c(t-1,t+1)
     muv=muv[(muv>0)&(muv<10)&(muv!=m)]
     nomove=(length(muv)==0)
     if (!nomove)
      t=sample(rep(muv,2),1)}
    len=max(len,i)}
  return(len)}

produces the value 14.

Monty Hall closes the door

Posted in Books, Kids, pictures with tags , , , , , , , , , on October 1, 2017 by xi'an

Among much more dramatic news today, I learned about Monty Hall passing away, who achieved long lasting fame among probabilists for his TV game show leading to the Monty Hall problem, a simple conditional probability derivation often leading to arguments because of the loose wording of the conditioning event. By virtue of Stigler’s Law, the Monty Hall game was actually invented earlier, apparently by the French probabilist Joseph Bertrand, in his Calcul des probabilités. The New York Times article linked with the image points out the role of outfits with the game participants, towards being selected by the host, Monty Hall. And that one show had a live elephant behind a door, instead of a goat, elephant which freaked out..!

Measuring statistical evidence using relative belief [book review]

Posted in Books, Statistics, University life with tags , , , , , , , , , , , , , , , , , , on July 22, 2015 by xi'an

“It is necessary to be vigilant to ensure that attempts to be mathematically general do not lead us to introduce absurdities into discussions of inference.” (p.8)

This new book by Michael Evans (Toronto) summarises his views on statistical evidence (expanded in a large number of papers), which are a quite unique mix of Bayesian  principles and less-Bayesian methodologies. I am quite glad I could receive a version of the book before it was published by CRC Press, thanks to Rob Carver (and Keith O’Rourke for warning me about it). [Warning: this is a rather long review and post, so readers may chose to opt out now!]

“The Bayes factor does not behave appropriately as a measure of belief, but it does behave appropriately as a measure of evidence.” (p.87)

Continue reading

%d bloggers like this: