cp's OEIS Frontend

A386463 Box which a player should open at step n to catch a cat performing a random walk through 8 boxes to minimize the escape rate of the cat.

%I A386463 #26 Aug 14 2025 18:38:35
%S A386463 1,7,7,1,2,2,4,7,7,2,3,4,7,1,8,7,2,3,7,7,6,2,2,3,6,8,1,8,7,6,1,2,3,4,
%T A386463 7,1,8,7,2,3,7,7,6,2,2,3,6,8,1,8,7,6,1,2,3,4,7,1,8,7,2,3,7,7,6,2,2,3,
%U A386463 6,8,1,8,7,6,1,2,3,4,7,1,8,7,2,3,7,7,6
%N A386463 Box which a player should open at step n to catch a cat performing a random walk through 8 boxes to minimize the escape rate of the cat.
%C A386463 A cat is randomly hiding in one of 8 boxes, and a single player tries to catch the cat. In each step, the player opens a box. If the cat is found, the game ends; if not, the cat will move randomly either to the box on the left or to the box on the right. If the cat is in box 1 or 8, it has a 50% probability of escaping. By using the optimal strategy, the cat's escape rate is minimized to 0.223305988. The average duration of the game is 5.35 steps. Note that, since the problem is symmetric, a mirrored strategy also exists.
%H A386463 Ruediger Jehn, <a href="/A386463/a386463.pdf">Optimal Strategies to Detect Randomly Walking Cat</a>
%e A386463 a(1) = 1: 0.223306 is an upper bound for the minimum escape rate. If the player starts with box 2 (or 7) the escape rate exceeds this value at least after 11 steps no matter in which order the player will open the next boxes. If the player starts with box 3 (or 6) the escape rate exceeds the bound at least after 7 steps and if the player starts with box 4 (or 5) the escape rate exceeds the bound at least after 6 steps. Hence opening box 1 (or 8 for the mirrored strategy) allows the player to minimize the escape rate of the cat.
%Y A386463 Cf. A300576, A386462.
%K A386463 nonn,hard
%O A386463 1,2
%A A386463 _Ruediger Jehn_, Jul 22 2025
%E A386463 More terms from _Jinyuan Wang_, Jul 27 2025