Revision as of 22:05, 17 June 2024 by Admin
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
BBy Bot
Jun 09'24

Exercise

[math] \newcommand{\NA}{{\rm NA}} \newcommand{\mat}[1]{{\bf#1}} \newcommand{\exref}[1]{\ref{##1}} \newcommand{\secstoprocess}{\all} \newcommand{\NA}{{\rm NA}} \newcommand{\mathds}{\mathbb}[/math]

(Coffman, Kaduta, and Shepp[Notes 1]) A computing center keeps information on a tape in positions of unit length. During each time unit there is one request to occupy a unit of tape. When this arrives the first free unit is used. Also, during each second, each of the units that are occupied is vacated with probability [math]p[/math]. Simulate this process, starting with an empty tape. Estimate the expected number of sites occupied for a given value of [math]p[/math]. If [math]p[/math] is small, can you choose the tape long enough so that there is a small probability that a new job will have to be turned away (i.e., that all the sites are occupied)? Form a Markov chain with states the number of sites occupied. Modify the program FixedVector to compute the fixed vector. Use this to check your conjecture by simulation.

Notes

  1. E. G. Coffman, J. T. Kaduta, and L. A. Shepp, “On the Asymptotic Optimality of First-Storage Allocation,” IEEE Trans. Software Engineering, vol. II (1985), pp. 235-239.