exercise:366d008def: Difference between revisions

From Stochiki
(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
 
(One intermediate revision by the same user not shown)
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 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.
Allocation,” ''IEEE Trans.\ Software Engineering,'' vol. II (1985),
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}}

Latest revision as of 22:05, 17 June 2024

[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.