Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-23T17:05:45.919Z Has data issue: false hasContentIssue false
  • English
  • Français

Stochastic convexity of sums of i.i.d. non-negative random variables with applications

Part of: Computer system organization Distribution theory - Probability Special processes

Published online by Cambridge University Press:  14 July 2016

Armand M. Makowski  and
Thomas K. Philips
Armand M. Makowski*
Affiliation:
University of Maryland, College Park
Thomas K. Philips*
Affiliation:
IBM Thomas J. Watson Research Center
*
∗ Postal address: Electrical Engineering Department and Systems Research Center, University of Maryland, College Park, MD 20742.
∗∗ Postal address: IBM Thomas J. Watson Research Center, Yorktown Heights, NY 10598, USA.
Get access Rights & Permissions [Opens in a new window]

Abstract

We present some monotonicity and convexity properties for the sequence of partial sums associated with a sequence of non-negative independent identically distributed random variables. These results are applied to a system of parallel queues with Bernoulli routing, and are useful in establishing a performance comparison between two scheduling strategies in multiprocessor systems.

Keywords

FORWARD RECURRENCE TIMESMULTIPROCESSOR SYSTEMSFORK-JOINRANDOM ROUTING

MSC classification

Primary: 60E05: Distributions
Secondary: 60K05: Renewal theory 68M20: Performance evaluation; queueing; scheduling 60K25: Queueing theory
Type
Research Papers
Information
Journal of Applied Probability , Volume 29 , Issue 1 , March 1992 , pp. 156 - 167
Copyright
Copyright © Applied Probability Trust 1992 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

The work of this author was performed while he was a summer visitor at the IBM Thomas J. Watson Research Center.

References

[1]Baccelli, F. and Makowski, A. M. (1989) Queueing models for systems with synchronization constraints. Proc. IEEE 77, 138–161.Google Scholar
[2]Chang, C.-S., Chao, X.-L. and Pinedo, M. (1989) Some inequalities for bulk queues with Poisson arrivals. Unpublished paper, ORSA/TIMS meeting, Vancouver, Canada, May 1989.Google Scholar
[3]Kleinrock, L. (1976) Queueing Systems I: Theory. Wiley, New York.Google Scholar
[4]Makowski, A. M. and Philips, T. K. (1990) Stochastic convexity of sums of i.i.d. non-negative random variables with applications. IBM Research Report RC-16313.Google Scholar
[5]Makowski, A. M., Philips, T. K. and Varma, S. (1991) Comparing two scheduling strategies in multi-processor systems. Technical Report SRC 91-1, Systems Research Center, University of Maryland, College Park.Google Scholar
[6]Marshall, A. W. and Olkin, I. (1979) Inequalities: Theory of Majorization and its Applications. Academic Press, New York.Google Scholar
[7]Ross, S. (1984) Stochastic Processes. Wiley, New York.Google Scholar
[8]Shaked, M. and Shanthikumar, J. G. (1988) Stochastic convexity and its applications. Adv. Appl. Prob. 20, 427–446.Google Scholar
[9]Shaked, M. and Shanthikumar, J. G. (1990) Convexity of a set of stochastically ordered random variables. Adv. Appl. Prob. 22, 160–177.Google Scholar
[10]Shaked, M. and Shanthikumar, J. G. (1990) Parametric stochastic convexity and concavity of stochastic processes. Ann. Inst. Statist. Math. 42, 509–531.Google Scholar
[11]Stoyan, D. (1984) Comparison Methods for Queues and Other Stochastic Models. English translation, ed. Daley, D. J. Wiley, New York.Google Scholar