Independent vs Overall Percentage of Turns in Game where Next Player is Probabilistically Determined.

Question

I'm writing a program in which there are n "players". On each player's turn, the next player is randomly determined with a weight. My goal is to have each player have it be their turn a certain percentage of the time (e.g. Player 1 gets 0.20 of all turns).

If there were three players, [1, 2, 3] and I would like each of them to have it be their turn [0.20, 0.50, 0.30] of the total number of turns respectively. When I run this simulation several thousand times and count up the number of turns each player takes, however, I get a distribution of [0.258, 0.403, 0.339] of the turns for each player.

I am picking the next player by repeatedly sampling the list of players until I get one that is not the current player.

I think this is being complicated by the fact that the next player must not be the player whose turn it currently is, but I am unsure why this. How can I sample the next player and achieve some specific proportion of turns in the long run?

Answer 1

Player $2$ will get $\frac {0.5}{0.5+0.3}=\frac 58$ of the turns after player $1$ and $\frac 57$ of the turns after player $3$. If player $1$ gets $a$ of the turns, player $2$ gets $b$ of the turns, and player $3$ gets $c$ of the turns, we can solve the equations for the steady state $$a=\frac 25b+\frac 27c\\ b=\frac 58a+\frac 57c\\ c=\frac 38a+\frac 35b\\ a+b+c=1$$ Which gives $a=\frac {16}{62}\approx 0.258,b=\frac{25}{62}\approx 0.403,c=\frac{21}{62}\approx 0.339$. Your simulation works quite well.

With your constants, the simple thing is to realize that if player $2$ is going to get half the turns and cannot have two in a row, he must get every other turn. Let player $2$ go after both $1$ and $3$, then after player $2$ pick the next to play with $0.4$ for player $1$ and $0.6$ for player $2$.

Answer 2

If we don't change your picking algorithm, then I only have a partial solution for the case $n = 3$.

Let's say you want a distribution of $[u, v, w]$ with $u + v + w = 1$ and $u, v, w < 0.5$.

Then you should defined the weights $[a, b, c]$ as follows. First calculate $p = \frac 1 {1 - 2u}$, $q = \frac 1 {1 - 2v}$, $r = \frac 1 {1 - 2w}$, then define $$a = \frac p{p + q + r}, b = \frac q{p + q + r}, c = \frac r{p + q + r}.$$

Now you may use your algorithm with the new weights $[a, b, c]$ to pick the players, and the resulting distribution will be exactly $[u, v, w]$.

---

Currently I don't know if this method can be extended to more than $3$ players.