4
$\begingroup$

So, I was in my car listening to the radio when I was listening to a story about the captured New York prison escapees, and it had me thinking:

In a hypothetical large fixed area of land, let us present a prisoner p and a cop, c. Assuming both move randomly, would a prisoner, on average, be caught quicker if they remained idle in one spot, or kept on moving?

I've taken coursework in mathematical modeling of epidemiology, and I would assume that the prisoner would be caught faster if both the cop and the prisoner were moving based on the following:

in mathematical modeling, contact rates are simplified via a simplified version of the "mass action" principle from chemistry, which states that a contact rate can be defined by the products of two concentrations. If we assume movement is a "concentration", it would imply that if a escaped prisoner and a cop were both moving, that the overall order of the reaction rate be 2nd order, as opposed to a first order system where it was just the cop moving.

Just curious, is there a probabilistic approach to this that would strengthen this argument further or maybe even give a completely different answer? Would it be dependent on their relative rates?

$\endgroup$
  • $\begingroup$ The challenge of answering this question lies in adopting a reasonable model of "move randomly" within a fixed, finite region. When an actor gets close to the boundary, motion cannot be independent of direction--but exactly how does it change? (For a practically infinite region the problem is simplified: merely analyze the differences in movements between the two actors. That would be a 2D random walk and "capture" is the event that it reaches a small neighborhood of the origin.) Even more realistically, why assume either one moves randomly? Maybe they have better strategies. $\endgroup$ – whuber Jul 6 '15 at 17:17
  • $\begingroup$ I think random movement is an okay assumption if we also assume that neither party has any information about the others position, which would mean that any strategy is (more or less) just random movement. $\endgroup$ – dsaxton Jul 6 '15 at 17:23
  • $\begingroup$ @whuber This suggests interesting variants on the problem where actors are on a torus or other interesting topological objects... $\endgroup$ – Sycorax Jul 6 '15 at 17:26
  • $\begingroup$ when constant in position, the concentration there is very high. Your reaction model is a mixture - a sum of the results of the heterogenous distribution in the domain. $\endgroup$ – EngrStudent Jul 6 '15 at 17:27
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Pursuit-evasion $\endgroup$ – Glen_b Jul 6 '15 at 18:05
1
$\begingroup$

I did a simulation of this, assuming that the two players move randomly within the area.

    ## given a single coordinate of a single player, return a new position by a valid move
moveCoord = function( playerCoord, boardSizeCoord){
    move = sample(c(-1,0,1), 1)
    newCoord = playerCoord + move
    if (newCoord < 1 || newCoord > boardSizeCoord)
        newCoord = moveCoord(playerCoord, boardSizeCoord)
    return(newCoord)
}

## given a player's location, return a new location by a valid move
movePlayer = function(playerCoord, boardSize){
    newX = moveCoord(playerCoord[1], boardSize[1])
    newY = moveCoord(playerCoord[2], boardSize[2])
    newCoord = c(newX, newY)
}

n = 10 ## board is nxn
boardSize = c(n,n) ## board size
steps = 1000000 ## how many moves to try in each run of simulation, before they fail 
copCoord <<- c(floor(n/3), floor(n/3)) ## cop is at the first third vertically and horizontally (rounding down)
prisCoord <<- c(ceiling(2*n/3), ceiling(2*n/3)) ## prisoner is at the second third vertically and horizontally (rounding up)

## how many steps until both players intersect?
simulate = function(prisMove = FALSE){
    for( i in 1:steps){
        copCoordMat[i,] = copCoord
        if(identical(copCoord,  prisCoord)){
           ## print(paste("Caught at ", i))
            return(i)
            break
        }
        else {
            copCoord = movePlayer(copCoord, boardSize)
            if(prisMove == TRUE)
                prisCoord = movePlayer(prisCoord, boardSize)
            ##print(copCoord)
          }
    }
}

reps = 1000
noMoveVec = replicate(reps, simulate(prisMove = FALSE))
yesMoveVec = replicate(reps, simulate(prisMove = TRUE))
summary(noMoveVec)
summary(yesMoveVec)

Here are the results. In noMoveVec, only the cop moves; in yesMoveVec, both players move:

   > summary(noMoveVec)
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
    7.0    71.0   131.0   176.6   231.0  1056.0 
> summary(yesMoveVec)
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
    5.0    56.0   115.0   160.0   216.2  1123.0 

In 1000 runs of the simulations on a 10x10 grid, the moving prisoner got caught a little faster on average. I wasn't sure how much of the effect was due to the initial positions. So I tried it again having the cop in the bottom left corner and the prisoner in the top right corner. There's a way bigger effect in this case.

summary(noMoveVec)
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
   25.0   195.8   410.5   561.2   758.2  3150.0 
> summary(yesMoveVec)
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
   15.0    70.0   126.5   173.2   233.2  1057.0 
$\endgroup$
  • $\begingroup$ Bravo, thank you very much for this, your time was greatly appreciated. $\endgroup$ – Alvin Nunez Jul 10 '15 at 16:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.