Timeline for Cops and drunken robbers
Current License: CC BY-SA 2.5
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 16, 2019 at 12:00 | review | Close votes | |||
| Apr 16, 2019 at 15:41 | |||||
| Nov 27, 2014 at 16:01 | answer | added | Michał Kukieła | timeline score: 5 | |
| Mar 14, 2011 at 0:49 | vote | accept | Ross Churchley | ||
| Mar 13, 2011 at 19:51 | answer | added | Kristal Cantwell | timeline score: 10 | |
| Mar 13, 2011 at 16:38 | comment | added | Ross Churchley | @Nick My curiosity is strongest in the case where the cop has to move every turn and only catches the robber when they occupy the same vertex. But to be honest, I'd be interested to hear about any work that has been done on any variation of this problem. | |
| Mar 13, 2011 at 1:38 | comment | added | Nick S | There are two things unclear in the problem: 1) Can the cop skip a move? i.e. Does he have to move any turn, or if this is his best move he stays put in one turn? If the answer is yes, the bipartite graphs are not a problem anymore. 2) What happens if the cop and robber walk on the same edge in opposite direction? Did the cop catch the rober or did he got away? | |
| Mar 12, 2011 at 18:25 | history | edited | Ross Churchley | CC BY-SA 2.5 |
Added clarification based on comments
|
| Mar 11, 2011 at 16:53 | comment | added | Ross Churchley | @Anthony Quas For general graphs, I had been thinking of the cop and robber acting asynchronously; moving back and forth between the same two vertices has essentially the same effect as standing still. But I'd actually be more interested in synchronous movement, in which case we'd assume that the graph is either nonbipartite or the cop and robber start at an even distance apart. | |
| Mar 11, 2011 at 13:25 | comment | added | Douglas Zare | @Anthony Quas: If the cop doesn't move, then the expected time for the drunken robber to reach the cop would depend on $n$. That formula assumes the cop starts an even distance away and follows in that direction, so that it takes $d/2$ steps toward the cop to get caught, and $n$ does not matter. | |
| Mar 11, 2011 at 13:19 | comment | added | Robert Bell | The question makes sense as stated. The cop is playing intelligently, while the robber plays randomly. On an $n$ cycle, if the cop always moves clockwise, and the robber choses randomly which way to move, the distance between the cop and robber will equal zero in finite time almost surely. The second part is a very good question: if the graph is copwin-- meaning there is a strategy for catching an intelligent robber-- is following this strategy the best way to catch a drunken robber? I have not read about this result in the literature, but I have only dabbled in this area. | |
| Mar 11, 2011 at 8:27 | comment | added | Anthony Quas | I think you're not reading the paper correctly. I think the paper is about the sleeping cop and the drunken robber. As Gerry says if they are both moving on an even cycle the drunken robber gets to go forever as long as they move synchronously and start on opposite parity sites and so the expected time is infinite. | |
| Mar 11, 2011 at 7:32 | comment | added | Thomas Bloom | Presumably the drunken robber can also run right into the policeman. | |
| Mar 11, 2011 at 6:26 | comment | added | Gerry Myerson | What's it mean for cop to catch robber? They land on the same vertex? So if they start an odd distance apart on an even cycle, cop can't ever catch robber? | |
| Mar 11, 2011 at 5:21 | history | asked | Ross Churchley | CC BY-SA 2.5 |