exercise:366d008def: Difference between revisions
(Created page with "<div class="d-none"><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></div> (Coffman, Kaduta, and Shepp<ref group="Notes" >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.</ref>) A computing...") |
No edit summary |
||
| Line 6: | Line 6: | ||
\newcommand{\NA}{{\rm NA}} | \newcommand{\NA}{{\rm NA}} | ||
\newcommand{\mathds}{\mathbb}</math></div> (Coffman, Kaduta, and Shepp<ref group="Notes" >E. G. Coffman, | \newcommand{\mathds}{\mathbb}</math></div> (Coffman, Kaduta, and Shepp<ref group="Notes" >E. G. Coffman, | ||
J. T. Kaduta, and L. A. Shepp, “On the Asymptotic Optimality of | J. T. Kaduta, and L. A. Shepp, “On the Asymptotic Optimality of First-Storage Allocation,” ''IEEE Trans. Software Engineering,'' vol. II (1985), | ||
First-Storage | pp. 235-239.</ref>) 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 | ||
Allocation,” ''IEEE Trans. | 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. | ||
pp. 235-239.</ref>) 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''' | '''Notes''' | ||
{{Reflist|group=Notes}} | {{Reflist|group=Notes}} | ||
Revision as of 22:05, 17 June 2024
(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