cp's OEIS Frontend

A336233 a(n) is the player who has highest winning probability in the "Random Josephus Game" with n players.

%I A336233 #19 Jan 11 2021 22:59:56
%S A336233 1,1,3,1,2,3,4,6,8,1,1,2,3,4,5,6,8,9,11,12,14,16,17,19,21,23,25,1,1,1,
%T A336233 2,3,4,5,6,7,8,10,11,12,13,15,16,17,19,20,22,23,25,26,28,29,31,32,34,
%U A336233 36,37,39,41,42,44,46,47,49,51,53,55,56,58,60,62,64,66,68
%N A336233 a(n) is the player who has highest winning probability in the "Random Josephus Game" with n players.
%C A336233 The "Random Josephus Game" is a random variety of Josephus problem. Here, there are n players arranged in a loop labeled 1,2,...,n, and on every player's turn, he kills one of the players except himself equiprobably randomly and then gives the turn to the next living player in order of the loop, started by player 1. The winner is the last survivor.
%C A336233 Note that in the case with 3 players, both player 2 and player 3 have a winning probability of 1/2, and a(3) can be either 2 or 3.
%H A336233 <a href="/index/J#Josephus">Index entries for sequences related to the Josephus Problem</a>
%e A336233 For example, a "Random Josephus Game" with 4 players has 6 possible results, the probability of each is 1/6 respectively:
%e A336233 1) Player 1 kills player 2 and gives the turn to player 3. Then player 3 kills player 4 and gives the turn to player 1. Finally, player 1 kills player 3 and becomes the winner.
%e A336233 2) Player 1 kills player 2 and gives the turn to player 3. Then player 3 kills player 1 and gives the turn to player 4. Finally, player 4 kills player 3 and becomes the winner.
%e A336233 3) Player 1 kills player 3 and gives the turn to player 2. Then player 2 kills player 4 and gives the turn to player 1. Finally, player 1 kills player 2 and becomes the winner.
%e A336233 4) Player 1 kills player 3 and gives the turn to player 2. Then player 2 kills player 1 and gives the turn to player 4. Finally, player 4 kills player 2 and becomes the winner.
%e A336233 5) Player 1 kills player 4 and gives the turn to player 2. Then player 2 kills player 3 and gives the turn to player 1. Finally, player 1 kills player 2 and become the winner.
%e A336233 6) Player 1 kills player 4 and gives the turn to player 2. Then player 2 kills player 1 and gives the turn to player 3. Finally, player 3 kills player 2 and becomes the winner.
%e A336233 One can see, player 1 wins in three of the cases above, while player 3 wins in one of those, player 4 wins in two, and Player 2 wins in none. Thus, the winning probability of the four players are 1/2, 0, 1/6 and 1/3 respectively. Therefore a(4)=1.
%t A336233 table1 = NestList[
%t A336233   Prepend[(Range[0, Length[#] - 1] Prepend[Most[#], 0] +
%t A336233        Range[Length[#] - 1, 0, -1] #)/Length[#], Last[#]] &, {1.},
%t A336233   1000];
%t A336233 First[Ordering[#, -1]] & /@ table1
%Y A336233 Cf. A006257, A334473.
%K A336233 nonn
%O A336233 1,3
%A A336233 _Yancheng Lu_, Jul 13 2020