Find the Rat

[Bob Bixler]

A rat is in one of 100 holes that are in a line.  Each night he moves to the left or right 0,1, or 2 holes randomly selected.  You pick one hole each day to look in until you find him.  What procedure do you use in order to minimize the expected number of days before you find him?

[Evilhubert]

Spoiler

Just keep looking in either of the two middle holes every day

 

[Bob Bixler]

3 hours ago, Evilhubert said:

  Hide contents

Just keep looking in either of the two middle holes every day

 

Looking in a middle hole every date has an expected time of over 1,000 days to find the rat.  There's a way to do it in less time.

Edited April 16, 2023 by Bob Bixler

[Evilhubert]

On 4/17/2023 at 4:23 AM, Bob Bixler said:

Looking in a middle hole every date has an expected time of over 1,000 days to find the rat.  There's a way to do it in less time.

I give up. What is the answer?

[Bob Bixler]

As this is an open challenge question I want to give other people plenty of time to respond.

[EventHorizon]

Hey Bob, welcome to the den.  It's been a while since I've checked this site.

This puzzle, at first glance, seemed similar to "Groundhog in a Hole." -- http://brainden.com/forum/topic/11943--/

I have posted a couple variations, too.  -- http://brainden.com/forum/topic/12010--/ and http://brainden.com/forum/topic/18524-groundhog-in-a-hole-yet-again/

 

Anyway, I thought I'd ask for some clarification.  If the rat is in hole 10 on day 1, does that mean on day 2 it has an equal chance (20% each) of having gone to holes 8, 9, 10 (stayed there), 11, or 12?  If the rat is in hole 2 on day 1, on day 2 is there an equal chance (25% each) of being in holes 1, 2, 3, or 4?  And a third chance each for holes 1, 2, and 3 if starting right on the edge in hole 1?  And does the rat have an equal chance of being in any given hole on day 1 (1% each)?  Just thought I'd nail down the way the probabilities move.

Here's a quick guess before checking... anything really...

Spoiler

Alternate checking holes 3 and 98.

Holes 3 and 98 are both two away from the edges, and it is where I assume probability of this random walk should accumulate.  Alternating might help reduce the impact of reduced probabilities due to repeatedly checking the area.  I chose two away from the edge to still have 5 holes that could go to it each day.

 

[Bob Bixler]

Yes to all your questions.  There are better ways than your initial guess.

[EventHorizon]

It seems my initial guess and idea about how the probabilities would end up were... umm,  bad.

Yay code...

Spoiler

#include <stdio.h>
#include <stdlib.h>

#include <iostream>
#include <fstream>

#include <math.h>
#include <cstring> //for memcpy

using namespace std;

const long double third = 1/3.0d;
const long double quarter = 1/4.0d;
const long double fifth = 1/5.0d;

long double probs[100];
long double probsnew[100];

long double probleft;
long double currenttaken;
long double expect;
int holechecked;
int lasthole;
int daynum;
ofstream *out;

void initprobs()
{
    probleft = 1;
    expect = 0;
    daynum = 0;
    lasthole = -1;
    for(int i = 0; i < 100; i++) probs[i] = .01d;
}

void stepprobs()
{
    probs[0] *= third;
    probs[1] *= quarter;
    probs[99] *= third;
    probs[98] *= quarter;
    for(int i = 2; i < 98; i++) probs[i] *= fifth;
    
    probsnew[0] = probs[0] + probs[1] + probs[2];
    probsnew[1] = probsnew[0] + probs[3];
    probsnew[2] = probsnew[1] + probs[4];
    probsnew[99] = probs[99] + probs[98] + probs[97];
    probsnew[98] = probsnew[99] + probs[96];
    
    long double currentprob = probsnew[2];
    for(int i = 3; i <= 97; i++)
    {
        currentprob += probs[i+2] - probs[i-3];
        probsnew[i] = currentprob;
    }
    
    memcpy(probs,probsnew,sizeof(long double)*100);
    daynum++;
}

long double checkhole(int holenum)
{
    lasthole = holechecked;
    holechecked = holenum;
    if ((holenum < 0) || (holenum >= 100)) {currenttaken = 0 ; return 0;}
    currenttaken = probs[holenum];
    probleft -= currenttaken;
    probs[holenum] = 0;
    expect += daynum * currenttaken;
    return currenttaken;
}

long double sanitycheck()
{
    long double total = probleft;
    for(int i = 0; i < 100; i++) total-=probs[i];
    return total;
}

void printstatus()
{
    *out << holechecked << "," << (holechecked-lasthole) << "," << (1-probleft) << "," << probleft << "," << currenttaken << "," << (currenttaken/probleft) << "," << sanitycheck() << "," << expect << ",";
    *out << (expect + ((daynum+1)*(probleft))) << ",";
    
    if (currenttaken>0) *out << (expect + ((daynum+((probleft/currenttaken)-1))*probleft)) << ",";
    else *out << "inf" << ",";
    
    *out << (expect + (1000000000000*probleft)) << ",";
    for(int j = 0; j < 100; j++)
    {
        *out << "," << probs[j];
    }
    *out << endl;
    if (daynum % 100 == 0) cout << daynum << "," << probleft << "," << (expect + ((daynum+((probleft/currenttaken)-1))*probleft)) << endl;
}

void printheaders()
{
    *out << "holechecked" << "," << "holediff" << "," << "taken" << "," << "probleft" << "," << "currenttaken" << "," << "currenttaken/probleft" << "," << "probleft error" << "," << "expect" << ",";
    *out << "expectmin" << ",";
    *out << "expectapprox" << ",";
    *out << "expectlarge" << ",";
    for(int j = 0; j < 100; j++)
    {
        *out << "," << "hole " << j;
    }
    *out << endl;
}

int findmax(int mode) //0leftmost,1rightmost,2closest
{
    int maxhole = 0;
    for(int i = 1; i < 100; i++)
    {
        if (probs[maxhole] < probs[i]) maxhole = i;
        else if (probs[maxhole] == probs[i])
        {
            switch (mode)
            {
                case 0://do nothing
                    break;
                case 1:
                    maxhole = i;
                    break;
                case 2:
                    if (abs(holechecked-maxhole) > abs(holechecked-i))
                        maxhole = i;
                    break;
            }
        }
    }
    return maxhole;
}

void doday(int hole) {checkhole(hole); printstatus(); stepprobs();}

int main(int argc, char *argv[])
{
    ofstream outfile;
    outfile.open("output.csv");
    out = &outfile;
    
    initprobs();
    printheaders();
    
    /* //1000 -- 81.9813
    doday(94);
    doday(97);
    for(int j = 0; j <= 33; j++)
    {
        for(int i = 2; i <= 14; i+=3) doday(i);
        for(int i = 18; i <= 30; i+=3) doday(i);
        for(int i = 34; i <= 97; i+=3) doday(i);
    }
    */
    
    
    /* //1000 -- 82.0348
    doday(92);
    doday(2);
    doday(97);
    for(int i = 0; i <= 1000; i++)
    {
        doday(findmax(0));
    }
    */
    
    /* //9000 -- 862.492
    for(int i = 0; i <= 9000; i++) doday(49);
    */
    
    /* //9000 -- 782.726
    for(int i = 0; i <= 4500; i++) {doday(2); doday(97);}
    */
    
    outfile.close();
}

 

My best approach so far...

Spoiler

I calculated an expected value for the day to catch the rat for this as about 81.9813 days.
First, check hole 95, then 98.  Then, starting with hole 3, check every third hole (moving an extra hole twice... 19 instead of 18, then 35 instead of 34).  Go back to hole 3 and begin checking every 3rd hole again with the same modifications, and repeat.

My code is 0-based, so add 1 to those if you want the holes numbered 1-100.

    doday(94);
    doday(97);
    for(int j = 0; j <= 33; j++)
    {
        for(int i = 2; i <= 14; i+=3) doday(i);
        for(int i = 18; i <= 30; i+=3) doday(i);
        for(int i = 34; i <= 97; i+=3) doday(i);
    }

It seems we calculate the expected value for the day the rat is found differently.

Spoiler

I have that Evilhubert's approach would take 862.492 days.  (And my initial guess wasn't much better, at 782.726)

 

[Bob Bixler]

Yes, you have the basic procedure which is to start at or near one end and move 3 holes each time until you reach the end and repeat at or near the start.  There are subtle modifications as you describe but they all give about the same result.  The interesting point is that there is an enormous difference between this approach and offhand initial guesses.