recherch_xiii.mws

Recherches sur l'intégration des équations différentielles aux différences finies, et sur leur usage dans la théorie des hasards.

P.S. Laplace

PROBLEM XIII .

I suppose a number of players (1), (2), (3),..( n ) play in this way: (1) plays with (2), and if he wins he wins the game; if he neither loses nor wins, he continues to play with (2), until one of the two wins. But if (1) loses, (2) plays with (3); if he wins it, he wins the game; if he neither loses nor wins, he continues to play with (3); but if he loses, (3) plays with (4), and thus in sequence until one of the players has defeated the one who he follows; that is to say (1) must be winner over (2), or (2) over (3), or (3) over (4), ... , or ( ) over ( n ), ( n ) or (1) over . Moreover, the probability of anyone of the players to win over the other equals , and that of neither winning nor losing equals . This put, it is necessary to determine the probability that one of these players will win the game at trial x .

One should approach the problem as a Markov chain and seek the probability of absortion from state i at time x.

Let's suppose 3 players. The 6 states are A: (1) plays with (2); B: (2) plays with (3); C: (3) plays with (1) and the absorbing states 1W, 2W and 3W in which (1), (2) and (3) win respectively. The transition matrix has a nice symmetry in that it is composed of 4 square matrices. The upper right and lower right are both diagonal matrices and the lower left is a zero matrix.

> restart:

> with(linalg):

Warning, the protected names norm and trace have been redefined and unprotected

> p:=1/3:

> T3:=array(1..6,1..6,[[p,p,0,p,0,0],[0,p,p,0,p,0],[p,0,p,0,0,p],[0,0,0,1,0,0],[0,0,0,0,1,0],[0,0,0,0,0,1]]);

Player (1) begins the game. We want the state at time x which will be given by the function .

> ini3:=matrix(1,6,[1,0,0,0,0,0]);

> f3:=x->evalm(ini3&*(T3&^x));

Now the function will produce, in the fourth component, the probability that Player (1) wins at or before time x . In the fifth component is the probability that Player (2) wins at or before time x and in the sixth component is the probability that Player (3) wins at or before time x . Therefore, to obtain the probability that each Player win at time x it is necessary to compute . It should be noted as well that Laplace's solutions are exhibited only for , n being the number of players. The pattern does not continue beyond this point.

> evalm(f3(3)-f3(2));

> evalm(f3(4)-f3(3));

Suppose 5 players. The process has 10 states analoguous to the previous example. In order to simplify matters, let's make use of some basic matrix operations in order to more efficiently create the transition matrix, T6.

> UL:=matrix(5,5,[[p,p,0,0,0],[0,p,p,0,0],[0,0,p,p,0],[0,0,0,p,p],[p,0,0,0,p]]):

> LL:=diag(0,0,0,0,0):UR:=diag(p,p,p,p,p):LR:=diag(1,1,1,1,1):

> L:=stackmatrix(UL,LL):R:=stackmatrix(UR,LR):

> T5:=augment(L,R):

Player (1) begins the game. The state of the system at time x is given by the function .

> ini5:=matrix(1,10,[1,0,0,0,0,0,0,0,0,0]);

> f5:=x->evalm(ini5&*T5&^x);

We see that the probability that player (k) win at time x is the th entry in the value of the last five columns of . For example, we examine x=5 and x=6 below.

> delcols(evalm(f5(5)-f5(4)),1..5);

> delcols(evalm(f5(6)-f5(5)),1..5);

>