exercise:366d008def: Difference between revisions
No edit summary |
No edit summary |
||
| Line 7: | Line 7: | ||
\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 First-Storage Allocation,” ''IEEE Trans. Software Engineering,'' vol. II (1985), | 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 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 | 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. | ||
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
(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