Cybernetics and Systems Analysis, Vol. 40, No. 5, 2004
BRIEF COMMUNICATIONS ERGODIC DISTRIBUTION OF A SYSTEM RESOURCE T. A. Aliyevaa and T. I. Nasirovab
UDC 519.21
The Laplace transform of the ergodic distribution of a semi-Markov random-walk process with a delay screen at zero is found. Keywords: semi-Markov process, ergodic distribution, system resource, delay screen.
In practice, the solution of many problems on the basis of inventory theory, queueing theory, reliability theory, etc. is stipulated by investigations of processes of semi-Markov walks with a delay screen at zero. Many works are devoted to the study of processes of semi-Markov walks with various screens at zero [1–6] but, in these works, the process of semi-Markov walks with a positive drift, negative jumps, and a delay screen at zero is not considered. It is precisely the sought-for semi-Markov walk process (with a positive drift, negative jumps, and a delay screen at zero) whose ergodic distribution is found in this article. Description of the model proposed. Let, at the initial moment of time, some system have a resource z ( z ³ 0). After a random time interval x 1 > 0 , its resource becomes equal to z + x 1 and, at the moment x 1 , the resource is instantly reduces to a level max( 0, z + x 1 - z 1 ) . Then the resource becomes equal to max( 0, z + x 1 - z 1 ) + x 2 after a time x 2 , instantly reduces to the level max( 0, max( 0, z + x 1 - z 1 ) + x 2 - z 2 ), and so on. The objective of this article is to find the ergodic distribution of the system resource. Mathematical statement of the problem. We assume that, on a probability space (W , J , P ) , a sequence of identically distributed positive independent random quantities { x k , z k }k ³ 1 is given and that, in this case, x k and z k are independent of each other. Based on these random quantities, we construct the following process: X 1 (t ) = z + t -
k -1
å zi,
i =1
k -1
if
å xi
i =1
£t <
k
0
i =1
1
å xi , å
= 0.
By the Borovkov method, this process is delayed by a screen at zero [2] and we have X ( t ) = X 1 ( t ) - inf
0 £s£t
( 0, X 1 ( s )) .
It is required to find the Laplace transform of the ergodic distribution of the process X ( t ) . Laplace transform of the ergodic distribution of the process X ( t ). By the formula of composite probability, we have I {X ( t , w ) < x | X ( 0) = z} = I {X ( t ) < x, x 1 > t | X ( 0) = z}
a
Azerbaijan State Economic University, Baku, Azerbaijan Republic,
[email protected]. bBaku State University, Baku, Azerbaijan Republic,
[email protected]. Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 183-187, September-October 2004. Original article submitted October 4, 2002. 784
1060-0396/04/4005-0784
©
2004 Springer Science+Business Media, Inc.
¥
t
ò ò
+
I { x 1 Î ds; max ( 0, z + x 1 - z 1 ) Î dy}I {X ( t - s ) < x| X (0) = y}.
(1)
s= 0 y= 0
We denote R ( t , x | z ) = I {X ( t ) < x | X ( 0) = z}. Then Eq. (1) assumes the form t
R ( t , x | z ) = I {z + t < x}I {x 1 > t} +
ò
¥
ò
I {x 1 Î ds;
s= 0 y= 0
z + s - z 1 > 0; z + s - z 1 Î dy}R ( t - s, x | y ) ¥
t
+
ò
ò
I { x 1 Î ds; z + s - z 1 < 0, 0Î dy}R ( t - s, x | y},
s= 0 y= 0
where I ( × ) is the indicator of the corresponding event. After some transformations, we obtain R ( t , x | z ) = I { t < max( 0, x - z )}I {x 1 > t} -
¥
t
ò
ò
I { x 1 Î ds}d y I { z 1 < z + s - y}R ( t - s, x | y )
y= 0 s= 0 t
ò
+
I { x 1 Î ds} I { z 1 > z + s }R ( t - s, x | 0) .
(2)
s= 0
We denote
¥
~ R (q, x | z ) =
ò
e - qt R ( t , x | z )dt , q > 0 .
t=0
Then from Eq. (2) we have
~ R (q, x | z ) =
max ( 0 , x - z )
ò
e - qt I { x 1 > t}dt
t=0
-
¥
ò
~ R (q, x | y )
y= 0
¥
e - qs I { x 1 Î ds}d y I {z 1 < z + s - y}
ò
s = max ( 0 , y - z ) ¥
+
ò
~ e - qs I { x 1 Î ds} I { z 1 > z + s}R ( q , x |0) .
(3)
s= 0
Taking into account the notations ¥ ~ ~ ~ R ( q , a | z ) = ò e - ax d x R ( q , x | z ), a > 0 ,
(4)
0
we obtain the following equation from equation (3):
785
¥
~ ~ R ( q , a | z ) = e qz
ò
e - ( a + q ) x I {x 1 > x - z}dx -
x= z
+
¥
ò
¥
¥
y= 0
s= max( 0 , y- z )
~ ~ R ò (q, a | y )
e - qs I {x 1 Î ds}d y I {z 1 < z + s - y}
ò
~ ~ e - qs I {x 1 Î ds} I {z 1 > z + s} R ( q , a |0) .
(5)
s= 0
We solve this equation for the case where the distribution of the random quantities x 1 and z 1 is two-dimensional Erlang with parameters m and l, respectively. Then Eq. (5) is of the form ~ ~ 2 l2 m 2 a + 2m + q - az R (q, a | z ) = e e+ 2 3 (a + m + q ) (l + m + q) l2 m 2
+
+
+
(l + m + q)
l2 m 2 ( l + m + q )2 2 l2 m 2 ( l + m + q )3
3
e ( m+ q ) z
ze -
lz
z
ò
~ ~ e ly R ( q , a | y )dy -
0
¥
ò
~ ~ ye - ( m+ q ) y R ( q , a | y )dy -
z
e ( m+ q ) z
¥
ò
z
lz
ò
~ ~ e ly R ( q , a | y )dy
0
l2 m 2 (l + m + q)
z
2
e-
l2 m 2 ( l + m + q )2
lz
z
ò
~ ~ ye ly R ( q , a | y )dy
0
ze ( m+ q ) z
¥
ò
~ ~ e - ( m+ q ) y R ( q , a | y )dy
(6)
z
~ ~ m2 é 2l ù e - ( m+ q ) y R ( q , a | y )dy + ê1+ lz + eú 2 l + m + q û (l + m + q) ë
lz
~ ~ R ( q , a | 0).
From the integral equation (6), we obtain the following differential equation in z: ~ ~ R
(4 )
~ ~ ( q , a | z ) + 2[ l - m - q ]R
(3 )
(q, a | z )
~ ~ - [ l2 + ( m + q )( m + 4 l - q )( 4 l - m - q )]( R ~ ~ - 2l ( m + q )( l - m - q )R
(1)
(2 )
(q, a | z )
~ ~ ( q , a | z ) + l2 q ( q + 2m )R ( q , a | z )
= ( l - a ) 2 ( a + 2m + q )e -0 z
(7)
whose solution is as follows: ~ ~ R ( q , a | z ) = C1 ( q , a ) e + C 3 (q, a ) e
K 3 (q ) z
K 1 (q ) z
+ C 2 (q, a ) e
+ C 4 (q, a ) e
K 4 (q ) z
K 2 (q ) z
+ C (q, a ) e
+ -0 z
,
(8)
where C (q, a ) =
( l - a ) 2 ( a + 2m + q ) a 4 - 2a 3 [ l - m - q ] + a 2 [ l2 - ( m + q )( 4 l - m - q )] - 2al ( m + q )( m + q - l ) + l2 q ( 2m + q )
and K i ( q ), i = 1, 4, are the roots of the characteristic equation of the differential equation (7). The coefficients C i ( q , a ), i = 1, 4, are found on the basis of the following boundary conditions obtained from integral equation (6):
786
¥ ì~ ~ ~ ~ a + 2m + q l2 m 2 + ye - ( m+ q ) y R ( q , a | y )dy ï R ( q, a | 0) = 2 2 ò (a + m + q ) (l + m + q) 0 ï ï ~ ~ ï ¥ ~ 2 l2 m 2 é 2l ù m 2 R ( q , a|0) - ( m+ q ) y ~ ï ; ( , | ) e R y dy + + 1 + q a ê l + m + qú ò ï ( l + m + q )3 0 û ( l + m + q )2 ë ï ï~ ~ ï R~¢ ( q , a |0) - ( m + q )R~( q , a |0) = - a + 2m + q í a+ m+ q ï ~ ~ ¥ ï ~ l2 m 2 ù m 2 R ( q , a|0) é l - ( m+ q ) y ~ 1 e ( , | ) R q a y dy + ï ê l + m + qú l + m + q ; ò ï ( l + m + q )2 0 û ë ï ~ ~ ~ ~ ï~ ~ 2 ~ 2~ ï R¢ ¢ ( q , a |0) - 2( m + q )R¢ ( q , a |0) + ( m + q ) R ( q , a |0) = a + 2m + q + m R ( q , a |0); ï ~ ~ ~ ~ ï R~ 2 ~ î ¢ ¢ ¢ ( q , a |0) - 2( m + q )R¢ ¢ ( q , a |0) + ( m + q ) R¢ ( q , a |0) = - a( a + 2m + q ).
(9)
Since the random quantity X ( 0, w ) is distributed as the random quantity x 1 , we have ¥ ~ ~ ~ ~ R ( q , a ) = ò R ( q , a | z )dI {x 1 < z}. 0
From the constraints of conditions (9), we find C1 ( q , a ) =
a + 2m + q - {a 2 + 2a( m + q ) + q ( 2m + q )}C ( q , a ) k12 ( q ) - 2( m + q )k1 ( q ) + q ( 2m + q )
,
C i ( q , a ) = 0, i = 2, 4. Then we have
~ é C1 ( q , a ) ~ C (q, a ) ù R (q, a ) = m 2 ê + ú. 2 ( a + m ) 2 úû êë[ m - k1 ( q )]
It is easy to prove that, when l < m, the process X ( t ) is ergodic. Then, by the Tauber theorem, we can find the Laplace transform of the ergodic distribution of the process X ( t ) in the form ~ ~ ~ Ee - aX ( w ) = R ( a ) = lim qR ( q , a ) q ®0
=-
( a + 2m )( a - 2l ) l-m , 2 a( a - l + m ) 2 - 2lm ( a - l + m )
(10)
where X ( w ) is the limiting value of the ergodic process X ( t ) . In particular, from (10), we find EX ( w ) = -
l2 + m 2 1 . , DX ( w ) = l-m 2lm ( l - m ) 2
787
REFERENCES 1. 2. 3. 4. 5. 6.
788
A. A. Borovkov, Probabilistic Processes in Queueing Theory [in Russian], Nauka, Moscow (1972). A. A. Borovkov, “Walk in a zone with delay boundaries,” Math. Notes, No. 4, 649–657 (1975). T. A. Khaniev, “Distribution of a semi-Markov walk with two delay screens,” in: Some Questions of the Theory of Stochastic Processes, Collect. Sci. Works, Kiev (1984), pp. 106–113. T. I. Nasirova, Semi-Markov Processes [in Russian], Elm, Baku (1984). T. I. Nasirova, Semi-Markov Processes [in Russian], Elm, Baku (1988). M. A. EI-Shehawey, “Limit distribution of first hitting time dealing random walk,” J. Indian Soc. Oper. Res., 13, No. 1, 63–72 (1992).