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);**

`> `