Simulation of relay-races
Автор: Larkin E.V., Kotov V.V., Ivutin A.N., Privalov A.N.
Рубрика: Программирование
Статья в выпуске: 4 т.9, 2016 года.
Бесплатный доступ
It is shown that multistage concurrent games, or relay-races, are widely used in practice. It is proposed to model relay-races in the state space, in which discrete co-ordinates are the mathematical analogue of stages, which participants pass in the current time, and basic principle of modelling of residence of participant in space states is the M-parallel semi-Markov process. With use of the proposed formalisms formulae for evaluation of stochastic and time characteristics of relay-races evolution are obtained. For arbitrary realization of switching trajectory the recurrent procedure of evolution with evaluation of stochastic and time characteristics of realization under investigation is worked out. Conception of distributed forfeit, which depends on difference of stages of participants compete in pairs is introduced. Dependence for evaluation of total forfeit for every participant is obtained.
Relay-race, concurrent game, m-parallel semi-markov process, distance, stage, state space, evolution, distributed forfeit, trajectory realization, recurrent procedure, m-параллельный полумарковский процесс
Короткий адрес: https://sciup.org/147159390
IDR: 147159390 | DOI: 10.14529/mmp160411
Текст научной статьи Simulation of relay-races
Multistage concurrent games, in which situation develops in physical time, or relayraces objectively exist in different fields of human activity, such as sport, economics, politics, defense etc. [1-4]. In games of this type "distance" that should be overcome by participants is broken down into "stages", and efficiency of "distance" passage depends not only on overall "winning" the whole "distance", but also on "winning" the "stages" (below terms "distance", "stage", "winning", "forfeit" etc. will be used without inverted commas).
In the paper assumptions are as follows [5]:
-
1) relay-race is considered as passing by participants of equal distance in real physical time;
-
2) distance of every participant is divided onto stages, every of which has a number equal for all participants;
-
3) stages with the same numbers have equal length;
-
4) all participants start at once;
-
5) time of passing of every stage by the participant is a random one and is de-fined individually for him with accuracy to density;
-
6) after completion of a current stage the participant starts the next one without a lag;
-
7) winning or losing of a stage competition is understood as completion of the stage being the first or not the first;
-
8) winner’s forfeit is distributed in time and depends on difference of stages, which winner and losers pass.
-
1. Relay-Race as М-Parallel Semi-Markov Process
Distance, stages and participants are shown on Fig. 1, where the following indexes are used: 1 < m, n < M are numbers of participants under competition; 0 < i, j < J are numbers of stages, or numbers of changeover points. Point 0 is the start one, point J is the final one. Number of stage is cpiite similar with number of starting points. Indexes of stages are performed as functions. Bracketed part of index are points of participants.
* 1 2 ... m ... v: M |
0(1) |
i (1) |
... |
J (1)-1 |
J (1) |
|
0(2) |
i (2) |
... |
J (2)-1 |
J (2) |
||
0( m ) |
... |
i ( m ) |
... |
J ( m )-1 |
J ( m ) |
|
0( M ) |
... |
i ( M ) |
... |
J ( M )-1 |
J ( M ) |
|
0 1 |
... |
i i + |
... J -1 J |
Stage’s Number
Fig. 1. Distances, stages and participants of relay-race
Model of relay-race with M participants may be performed as M-parallel semi-Markov process h (t) = [ h i( t) ,...,hm (t) ,...,hn (t),... hM (t)], (1)
where t is the time: h m ( t ) is the m -th semi-Markov nratrix [6. J of size ( J + 1) x ( J + 1). which describes passing the stages of distance by m -th participant;
h m ( t ) — Vhj ( m ) ,l ( m )( t ) J, (-)
h ( t ) = / fi ( m )( t ) , when / ( m )— j ( m ) + 1 ,
j ( m ) ,l ( m )( о , ^ ац other cases.
fi ( m )( t ) is density of tinie of passing the Ftli stage by the m -tli participant. For densities fi ( m )( t ) the following restrictions are performed:
∞ j tfi(m)(t)dt < ^ ^hen 0 < i (m) < J, 1 < m < M, 0
fj(m)(t) = lim §(t - т), 1 < m < M, τ→∞ where §(t — т) is a, shifted Dirac 5-function.
The first restriction means that all participants pass all stages, except the J -th, during a finite time. The second restriction means that the J -th stage may be considered as stage with infinite time of passing.
Numbers of stages may be performed as the cortege p — (0 ,... ,i,..., J ), the M -th Cartesian degree of which gives an M -dimensional space s — pM of states of process (1) (Fig. 2). Coordinates of space are fixed on the participants, discrete coordinate values define numbers of changeover points, or current stages of participants. In the space s an M -dimensional vector of states is defined
S = [г(1),...,г(т),...,г(М)], where i ( m ) is the number of a current stage of the m-th participant.

Fig. 2. Space s of states
The total number of states is equal to ( J + 1) M. Initial meaning of vector S b = (0 ,..., 0 ,..., 0). Wandering through M -parallel semi-Markov process has the character of evolution, in which after every switch some element of vector S increments by a unit. For any switches incremental element is the only one. Switches last till state S e = ( J,..., J,..., J ). The total number of switches during evolution is R = JM.
-
2. Common Formulae for Evolution Parameters
During evolution the ordinary semi-Markov processes, described by (1), compete between them [2,5]. Let us consider the common case, when processes under competition are described with densities 9 1( t ) ,..., 9 a ( t ) ,..., 9 A ( t ). In such a case density of time till a first switching is defined as
A AA
9w ( t ) = ^9wa ( t ) = 9a ( T ) П [1 - 6 в ( t )] ,
a =1 a =1 в =1
в=a where 9wa(t) is the weighted density of time of winning the a-th density: 6в(t) = ft 9в(т)dT is distribution function.
The probability of win of the а -th density and pure density of time of winning the а -th density are, correspondingly, equal to:
πwα
∞
9 wa ( t ) dt ;
φwα
9 wa ( t ) n wa ( t )
The following proposition is quite correct.
Proposition 1. If density 9a(t) is under restriction (3), i.e. 9a(t) = limт,.x 5(t — т), then nwa = 0.
Really, in this case
∞A
A
= lim n i1 - 6 в ( т )] • τ →∞
β =1
β ̸ = α
nwa = / lim 5 ( t — т ) П [1 - 6 в ( t )] dt τ →∞
β =1
0 β ̸ = α
If among the functions 6 в ( t ) there are functions, for which 6 в ( t ) = lim тx^ n ( t - т ), where n ( t — т ) is shifted Heaviside function, then one can always demand the solution of indeterminacy as lim т ,. x. J^ 5 ( t — т ) n ( t — т ) dt = 0. So, proposition 1 may be considered to be proven.
The second formula, necessary for relay-races simulation, is the dependence for waiting time density. If from competing processes of 9 a ( t ) and 9в ( t ) , 9в ( t ) wins the process, it waits until 9 a ( t ) will be completed, which may be evaluated as [2,5]
n ( t ) f 9в ( e ) 9a ( t + e ) de
9 •■ ( t ) = ----- ^----------------------
f 6 в ( t ) d 6 a ( t )
Proposition 2. If 9a ( t ) is restricted by (3), then the lower boundary of the domain and expectation of 9в^а ( t ) tend to infinity.
∞
Really, in that case denominator of (7) is equal to J 6 в ( t ) lim т^^ 5 ( t — т ) dt = 1. Lower 0
boundary of 9в(t) is min {агд^9в(t) > 0J} = Tвmin > 0. So lower boundary of numerator of ( ?) is min arg J 6в (e) limт .. 5(t — т + e)d( > 0 = limт.. (Тв min + т) ^ го.
It is known [8], that for every random value expectation ranges in domain T min < T < T max, where T is an expectation, T min , T max are lower and upper boundaries of domain. Consequently, if Tв min ^ го , then Tв ^ го , where Tв = J^ t9в ( t ) dt is an expectation of time of completion 9в ( t ).
So, proposition 2 may be considered to be proven.
Proposition 3. If lower boundary of density 9a ( t ) is as Ta min ^ го, then
π wα
∞A
= / 9a ( t ) П [1
β =1
0 β ̸ = α
— 6 в ( t )] dt = 0 •
Really, density 9 a ( t ) may be performed as a result of ideal multiplicative sampling with the infinitesimal sampling period:
∞
9a ( t )= lim E 9a ( t ) 5 ( t — Zl ) , (8)
ζ →∞ l =0
where Z ^ го is the sampling period.
All readouts of function (8) belong to t > T a min ^ to, thus
∞
9a ( t ) — lim lim ^ 9a ( t ) 5 ( t - Ta min - Zl ) •
T a min '^ Z '^ j=J
So, according to proposition 1,
∞
— z l ) П[1 - 0 в ( t )] dt — 0 , в =1 в = a
n wa —
lim lim ^ 9 a ( t ) 5 ( t — Ta min
J T a min '^ Z '^ 2=0
and proposition 3 is proved.
Proposition 4. If density distribution 9a ( t ) has the property min arg 9a ( t ) — Ta min ^ to, then lower boundary of domain and mathematical expectation of 9pia ( t ) tend to infinity.
Really, in accordance with intermediate result of proposition 2, in this case the de-∞∞ nominator of (7) J 0в(t) lim lim 9a(t)5(t — Tamin — Zl)dt — 1- Lower boundary of
0 T a min '^ Z '^ l =0
numerator of (7) in this case
∞∞ min arg / 9 в (f) lim lim ^^ 9a (t) 5 (t — Ta min
— Zl ) d( > 0 — Ta min ^ TO,
0 Ta min'^ Z '^ ^=J and proposition 4 is proved.
With use of dependences obtained and propositions proved a recursive procedure of relay-race evolution analysis may be formed.
-
3. Recursive Procedure of Relay-Race Evolution Analysis
Evolution of relay-race develops as competition in M -parallel semi-Markov process [912]. Let us introduce the concept of switching trajectory in the space s of states (Fig. 2) as the realization of stochastic sequence of vector S from state S b till state S e. The trajectory as a whole is occasional, the realization is quite deterministic for every concrete case of evolution [6,8].
Let us consider some (f.e. fc -th) case of evolution, which starts from state S b — (0 , • • •, 0 , • • •, 0). When no switches took place, the total number of switches is equal to r — 0, and participants pass zero stages of their distances. Initial densities from zero rows of matrices hm ( t ) , 1 < m < M participate in competition.
Let the n -th participant win in the fc -th realization under consideration. Probability of his winning may be obtained from (5) [13]:
∞M n0,k — / 0g0(n) (t) П [1 - 0GJ(j)(t)] dt, ^
0 j =1, j=n
∞ where '"G...(t) — Jgg.„(т)dx is the distribution function; 0g0(j)(t) — f0(j)(t),
0(1) < 0(j) < 0(M), upper left index points to the number of previous switches; lower right index points to the number of stage, in which the j-th participant stays in current moment of time.
Density of time spent by the winner for passing zero stage is equal to (5)
M
0 9 0( n )( t ) П [1 - ° G 0( j )( t )] j =1 , j =n
Ф ° ,k = ---------------------------- П ° ,k
After winning of the n -th participant on the zero stage he begins to pass the first stage, although all others continue passing their zero stages. This is why after the first switch the following densities participate in the competition:
gi ( j )( t )
g °( n ) ^ °( j )( t ) , when j = n, f 1( n )( t ) , when j = n,
(П)
where g °( n ) ^ °( j )( t ) is the density of waiting time for tire n -tli participant until the j -tli participant completes his zero stage.
Lower right indexes of 1 gi ( j )( t ) in the switching trajectory realization are as follows:
i (1) = 0 ,..., i ( m ) = 0 ,..., i ( n ) = 1 ,... i ( M ) = 0 .
Let us analyze the situation after r switches of the fc -th realization. In accordance to conditions of evolution total number of switches is equal to
M
^ i ( j ) = r, j =1
where i (1) ,..., i ( m ) ,..., i ( n ) ,..., i ( M ) are different, in common case, nominations of indexes, which define numbers of stages, passed by participants in the fc -th realization after r switches.
Let us denote the densities, which participate in competition after r switches, as r gi (i)( t ) , ..., r gi ( m )( t ) , ..., r gi ( m )( t ) , ..., r gi ( M )( t ). and suppose. that the Z -tli participant wins.
The probability of his winning is equal to
∞M nr,k = / r gi (l)(t) П [1 ~ rGi(j)(t)] dt,
° j ==1, j =l where rgi(j)(t) are densities, which participate in competition after r switches.
In particular, if after r switches in the fc -th realization the first participant wins, then the probability of his winning is equal to
∞M nr,k = /rgi(i)(t) П [1 - rGi(j)(t)] dt.
° j=1, j =1
Density of between switches in a general case is equal to фг,к
M rgi(i)(t) П [1 j=1, j =l
-
r Gi ( j )( t )]
.
πr,k
Let us note, that after J switches in M cases from the MJ realization, there emerges a situation, when vector S takes one of the next nominations: ( J, 0 ,..., 0 ,..., 0) ,..., (0 ,..., 0 , J, 0 ,..., 0) ,..., (0 ,..., 0 ,..., 0 , J Y After that quantity of possible competition outcomes from denominated sates decreases to unit. If the m -th participant gets the state J , then the probability of outcome from this state, according to propositions 1 and 3 is equal to zero.
After winning of the Z -tli participant for the r -th switching, he starts the [ i ( Z ) + 1]-th stage of his distance. All other participants continue the i ( j )-th stage, 1 < j < M,j _ Z. This is why in competition for the ( r + 1)-th switching the next densities participate:
r+П, ,(о -1 rgi< 1)^(j>(t)■ "lien j _ l, gi1 j)(t) I fi(i)+i(t), when j' = Z, where gi(l).,(j)(t) is the waiting time (7).
In particular, if in the fc -th realization the first participant wins, for ( r + 1)-th switching the next densities contend:
r +1 , . ( t ) _ { rgi (1) ^ i ( j )( t ) , when j = 1 , i ( j ) \fi (i)+i( t ) , when j = 1 .
And lastly, let us assume, that in the fc -th realization after the ( R — 1)-th switching the state
\ J, when I _ m , i
i ( l )_t J — 1 , when / _ m, \ i ( l )_ R — 1
emerges.
Probability of winning of the m -th participant is as follows:
П R — 1 ,k
∞M
_ / R-1 gj(m)-1(t) П [1 — о j-• j=m
R 1 Gj ( i )( t )] dt.
Due to propositions 1 and 3, n R- 1 , k _ 1. Probabilities of winning of all other participants (they reach the states J ) are equal to zeros. Densities of residence in states after R switchers are as follows:
, _ J Rgj ( m ) - 1 ^ J ( i )( t ) , when j _ Z _ m ;
'gi ( j )( t ) 1 f J ( j )( t ) , j _ l _ m .
Results of the fc -th recursive procedure are shown in Table 1.
The probability of the fc -th realization of evolution and the time density for finishing of the fc -th realization of relay-race are as follows:
R - 1
Пк _ П Пк,г, r =0
R - 1
Фк ( t ) _ L - 1 П L [ фк, ( t )] , r =0
Table 1
fc -th recursive procedure
-
4. Evaluation of Effectiveness of Relay-Race Strategy
It is quite natural for evaluation of effectiveness to use the model, in which
-
• the pairs of part.icipants. f.e. the m -th and the n -th are considered:
-
• participant, who gets a stage with higher number, acquires a forfeit from participants, who get a stage with lower number;
0
...
0
е forfeit is defined as a distributed payment ci ( m ) ,i ( n ) ( t ), value of which depends on time.
Elements ci ( m ) ,i ( n )( t ) are stacked into four-dimensional matrix of size
( J + 1) X ( J + 1) X M X M:
e( t ) — [ e mn ( t ) J, 1 < m,n < M. (19)
where e m , n ( t ) is a symmetrical matrix of size ( J + 1) X ( J + 1), which characterizes payments of the m -th participant to the n -tlr one:
c 0( m ) , 0( n )( t ) . |
. c 0( m ) ,i ( n )( t ) . |
■ c 0( m ) ,j ( n )( t ) |
||
c m,n ( t ) |
ci ( m ) , 0( n )( t ) . |
... . ci ( m ) ,i ( n )( t ) . |
. ci ( m ) ,j ( n )( t ) |
; (20) |
cj ( m ) , 0( n )( t ) . |
... . cJ ( m ) ,i ( n )( t ) . |
. cj ( m ) ,j ( n )( t ) |
Cm,n ( t ) = ... , 1 < m < M.
0 ... 0
Let us extract from the general fc -th realization only participants m and n and tabulate the к 2 , m , n -th realization of pair evolution.
к 2 , m , n -th realization of pair evolution
r |
S |
Densities |
0 |
0 , 0 |
f 0( m ) , f 0( n ) , 0 g 0( m ) , 0 g 0( n ) |
1 |
0 , 1 |
g 0( n ) ^ 0( m ) , f 1( n ) , g 0( m ) , g 1( n ) |
2 |
1 , 1 |
f 1( m ) , g 0( m ) ^ 1( n ) |
• I I |
||
r |
i ( m ) , i ( n ) |
g i ( m ) , g i ( n ) |
Table 2
r |
S |
Densities |
r + 1 |
i ( m ) + 1 , i ( n ) |
f i ( m )+1 , g i ( m ) ^ i ( n ) r +1 gi ( m )+1 ,r +1 gi ( n ) |
. • • |
||
R - 2 |
J ( m ) — 1 , J ( n ) — 1 |
R - 2 gj ( m ) - 1 ,R - 2 gj ( n ) - 1 |
R - 1 |
J ( m ) — 1 , J ( n ) |
R - 2 g J ( m ) - 1 ^ J ( n ) - 1 , fj ( n ) R - 1 gj ( m ) - 1 ,R - 1 gj ( n ) |
R |
J ( m ) , J ( n ) |
f R- 1 „ fj ( m ) , g j ( n ) ^ j ( m ) - 1 |
Analysis of evolution shows that situation, which changes conditions of forfeit payments, emerges from the winning of one of the participants and lasts till the next switching. If after r switches densities r gi ( m )( t ) and r gi ( n )( t ) compete, then the entire sum of forfeit on the stage is as follows [2]:
∞ r,k2 ,m,n
Cm,n —
{ r g i ( m )( t ) [1 — Gi ( n )( t )] + r g i ( n )( t ) [1 — Gi ( m )( t )] } ci ( m ) i ( n ) dt (21)
Due to (21) the n-tli participant pays to the m-tlr. if i(m) > i(n). and the m-tlr participant pays to the n-th, if i(m) < i(n). For the к2,m,n-th realization of relay-race on formulae, obtained from (5), the probabilities nr,k2mn corresponding to concrete order of switching can be found. So, winner’s sum (the m-th participant) is defined as
M K 2 2 J 2 J \
Nm
= E ЕП nrk 2 mM , n =1 , k 2 ,m,n Г =0 \r =0 /
n=m where K2 is common quality of realization оf pair evolution, which consists of J stages.
Conclusion
Concurrent game was represented as a relay-race, in which participants pass the distance, divided into stages, time of passing of which is known accurate to densities. Usage of the conception of M -parallel semi-Markov process allows to work out a recurrent procedure of relay-race evolution. On the base of common recursive procedure a pair evolution was constructed. For the pair evolution a mathematical expression for evaluation of winner’s sum is obtained. Expression for calculation of winner’s sum is the key to form the optimal strategies of multistage dynamical competitions in the case, when one can control the densities of passing by participants.
Further investigation in this area should be directed to find both formula, which connects quantities of participants and stages with total quantity of trajectories and formula, which permit to generate trajectories of relay-races evolution (now such trajectories are generated algorithmically), that helps to overcome curse of dimensionality. Also a mathematical apparatus, which connects the proposed models with classical game theory [14,15], and permits to build up optimal strategies of relay-race evolution, may be worked out.
Acknowledgements. The reported study was partially supported by RFBR and Tula Region Government, research project No. 16-41-710160 r_a.
Список литературы Simulation of relay-races
- Bellman R.E., Dreyfus S.E. Applied Dynamic Programming. New Jersey, Princeton University Press, 2015.
- Ivutin A.N., Larkin E.V. Simulation of Concurrent Games. Bulletin of the South Ural State University. Series: Mathematical Modelling, Programming and Computer Software, 2015, vol. 8, no. 2, pp. 43-54 DOI: 10.14529/mmp150204
- Krishnendu C., Jurdzinski M., Henzinger T.A. Simple Stochastic Parity Games. Computer Science Logic, Berlin, Heildelberg, Springer, 2003, pp. 100-113 DOI: 10.1007/978-3-540-45220-1_11
- Ivutin A., Larkin E., Kotov V. Established Routine of Swarm Monitoring Systems Functioning. Advances in Swarm and Computational Intelligence. Springer, 2015, pp. 415-422 DOI: 10.1007/978-3-319-20472-7_45
- Ivutin A.N., Larkin E.V., Lutskov Y.I. Simulation of Concurrent Games in Distributed Systems. 2015 5th International Workshop on Computer Science and Engineering: Information Processing and Control Engineering, WCSE 2015-IPCE. Moscow, 2015, pp. 60-65.
- Korolyuk V., Swishchuk A. Semi-Markov Random Evolutions. Semi-Markov Random Evolutions. Springer Netherlands, 1995, pp. 59-91 DOI: 10.1007/978-94-011-1010-5_4
- Ivutin A.N., Larkin E.V., Lutskov Y.I., Novikov A.S. Simulation of Concurrent Process with Petri-Markov Nets. Life Science Journal, 2014, vol. 11, no. 11, pp. 506-511.
- Shiryaev A.N. Probability. N.Y., Springer, 1996 DOI: 10.1007/978-1-4757-2539-1
- Cleaveland R., Smolka S.A. Strategic Directions in Concurrency Research. ACM Computing Surveys, 1996, vol. 28, no. 4, pp. 607-625 DOI: 10.1145/242223.242252
- Heymann M. Concurrency and Discrete Event Control. Institute of Electrical & Electronics Engineers Control System Magazine, 1990, vol. 10, no. 4, pp. 103-112 DOI: 10.1109/37.56284
- Valk R. Concurrency in Communicating Object Petri Nets. Concurrent Object-Oriented Programming and Petri Nets. Berlin, Heildelberg, Springer, 2001, pp. 164-195 DOI: 10.1007/3-540-45397-0_5
- Dijkstra E.W. Cooperating Sequential Processes. The Origin of Concurrent Programming. N.Y., Springer, 1968, pp. 65-138.
- Ivutin A., Larkin E. Estimation of Latency in Embedded Real-Time Systems. 2014 3rd Mediterranean Conference on Embedded Computing, Institute of Electrical & Electronics Engineers, 2014, pp. 236-239 DOI: 10.1109/meco.2014.6862704
- Squillante M.S. Stochastic Analysis and Optimization of Multiserver Systems. Run-Time Models for Self-managing Systems and Applications. Birkhäser Basel, 2010, pp. 1-24 DOI: 10.1007/978-3-0346-0433-8_1
- Iverson M.A., Ozguner F., Follen G.J. Run-Time Statistical Estimation of Task Execution Times for Heterogeneous Distributed Computing. Proceedings of 5th Institute of Electrical & Electronics Engineers International Symposium on High Performance Distributed Computing-96, Institute of Electrical & Electronics Engineers, 1996 DOI: 10.1109/hpdc.1996.546196