The discrete-day ski-rental note obtains a different deterministic ratio. This note uses continuous time and a different tie convention; compare the models before comparing their bounds.
An online algorithm must act before knowing how long a task will continue. Renting a resource is inexpensive for a short use, while buying avoids repeated charges during a long use. The difficulty is that the decision to buy must be made before the remaining duration is revealed.
The ski-rental model isolates this problem with only two prices. It lets us prove a complete comparison: the best deterministic multiplicative competitive ratio is 2, while a carefully chosen randomized policy achieves . We will derive that distribution and a matching lower bound, keeping the timing convention and the adversary's access to randomness explicit.
Specify what the algorithm knows and when it pays
Definition 7.2.1
(Continuous-time ski rental and pure competitive ratio)
Normalize the rental rate to one cost unit per time unit. Buying costs , after which further use is free. The season has unknown duration . Until it ends, the algorithm observes only that use is still needed; it receives no other predictive information. Costs have no resale value, refund or discount.
If the algorithm plans to buy at time , its cost is
At a tie , the end notification is processed first, so no purchase is made. Choosing means never buying. The offline optimum, knowing the duration in advance, is
A randomized policy has pure multiplicative competitive ratio at most when
The expectation is over the policy's private random choices. No additive constant is allowed in this definition. The adversary fixes independently of those choices; this is the oblivious-input model used below.
The no-additive-constant convention matters for this single-season problem. Allowing an arbitrary additive amount comparable to could hide the entire buying cost. We are comparing the displayed multiplicative guarantees directly.
Every deterministic policy here has a fixed first purchase time: imagine running it on a season that never ends. Before that time, every continuing season supplies the same observations. The same argument with a private random seed fixed in advance represents a randomized policy by a random purchase time , possibly infinite. On a fixed finite season, its behavior is the corresponding prefix until the season ends.
Balance the two ways a deterministic policy can lose
Buying immediately can waste on an arbitrarily short season. Never buying can spend an arbitrarily large amount on a long season. A finite positive threshold trades these risks against one another.
Theorem 7.2.2
(The optimal deterministic competitive ratio is 2)
Rent until time , then buy if use is still needed. This policy is 2-competitive. No deterministic policy in the stated model has a smaller pure multiplicative competitive ratio.
Proof
(Analyze both duration ranges and every possible threshold)
With , a season costs . A season costs .
For any , take durations just above and still below . Their ratio approaches . If , choose : the ratio is . Threshold attains 2. Threshold zero is unbounded as , and an infinite threshold is unbounded as .
Equivalently, the worst-case supremum for a finite positive threshold is when , and when . The first may be a limiting value rather than a maximum because of the end-before-purchase convention.
Worked example 7.2.3
(The event at the threshold has a distinct cost)
Let and use the threshold .
| Duration T | Policy cost | Offline cost | Ratio |
|---|---|---|---|
| 6 | 6 | 6 | 1 |
| 10 | 10 | 10 | 1 |
| 20 | 10 | 2 | |
| 30 | 20 | 10 | 2 |
At duration exactly 10, the season ends before a purchase. Slightly after 10, the policy has both rented and bought. This is why a proof must use the chosen event-order convention rather than assume continuity of every deterministic cost function. The competitive bound remains 2.
Derive a randomized distribution instead of guessing one
Seek a policy whose purchase time has a continuous density supported on , with cumulative distribution . For a fixed , either the policy has bought before , paying , or it has continued renting. Hence
Differentiating gives . To seek an equal ratio throughout this short-season range, require . Since , the resulting differential equation is .
With , its solution is . Requiring all probability to lie in , namely , determines the candidate
This derivation constructs a promising policy in the chosen density family. The next two proofs verify its guarantee and then show that no randomized policy in the model can do better.
One way to sample it is to draw uniformly in and set . This uses inverse-CDF sampling. The density is increasing, so choosing a time uniformly on would be a different policy.
Theorem 7.2.4
(The proposed threshold distribution achieves e/(e−1))
For every fixed duration , independently of the sampled threshold,
Thus this ideal continuous-time policy has competitive ratio exactly , approximately .
Proof
(Marginal cost on short seasons and expected cost on long ones)
For , substitute the candidate into to obtain . Since , integration gives .
For , the policy has bought with probability one; the single endpoint has zero probability. Its expected rental time is
because the integral is 1. Therefore its total expected cost is . The formulas agree at , proving the result for every positive duration.
Proof X-ray
Why the ratio is constant on short seasons
The distribution was built so that one equation holds: for all . The proof splits at because the two regimes behave differently. For only the marginal cost of one more unit of renting matters: it is , the chance that the policy has not yet bought, plus , the density of buying at that moment, and with the chosen these add to the constant . For the policy has bought with probability one, so the cost is plus the expected rental time , and the integral turns this into as well. Agreement at shows that the two formulas describe one function, and the zero probability of means the tie convention plays no role here.
The next two examples check the theorem by direct computation.
Worked example 7.2.5
(The expected cost computed directly at half a season)
Take and . Under the density on the expected cost is
Since , the integral equals . With , the second term is . The sum is , which equals , as the theorem states.
Worked example 7.2.6
(A season of exactly one break-even time and a very short season)
Keep . For the threshold is almost surely below , since has probability zero, so the policy always buys and pays against the offline cost . The tie convention is irrelevant. For a very short season, , the policy buys before the end with probability , so it almost always only rents. Its expected cost is against , again the ratio : the small chance of paying the full price is exactly what keeps the expectation on the line .
The proof so far does not show that randomization by itself is what helps, as the next example shows.
Counterexample mode
Uniform randomization still has worst-case ratio 2
If is uniform on , then for ,
Its ratio to the offline cost is , approaching 2 as . For , expected cost is . Thus uniform randomization does not improve the worst-case ratio 2. The useful ingredient was the distribution's balance across all fixed durations, not just the presence of a random choice.
Prove optimality by averaging independent input durations
Theorem 7.2.7
(No randomized policy beats e/(e−1))
Let a randomized policy in this model, possibly one that sometimes never buys, satisfy for every fixed , with private randomness independent of . Then .
Suppose any policy promised a factor for every fixed duration, using private randomness independent of that duration. For a lower-bound analysis, introduce an independent random input duration with density on . Its survival probability is .
Proof
(Averaging over an exponential season)
For a fixed finite threshold , write . Averaging this nonnegative identity gives
The expected purchase cost is . The two contributions sum to , for every fixed finite . A threshold of infinity also costs on average, because then the policy rents for the exponential duration whose mean is .
Conditioning on an independently randomized threshold therefore gives average online cost for every mixture of thresholds. Nonnegative costs justify exchanging the averaging order. Meanwhile the offline expectation is
If the policy's -competitive inequality held for every fixed duration, averaging that inequality over this independent duration law would give
This proves the lower bound for every randomized policy in the model, including policies that sometimes never buy. Together with the constructed upper bound, it establishes the optimal ratio.
Proof X-ray
Why one duration law defeats every threshold
The lower bound rests on a single identity: under the exponential law of mean , every fixed threshold has the same expected cost . The rental term increases in while the purchase term decreases at exactly the compensating rate, so no threshold can exploit the law. This is why mixtures of thresholds do not help and why the policy's private coins may be treated as independent of the season. The benchmark side is a separate computation, , which uses . The hypothesis doing the work is that the guarantee holds for every fixed season; averaging a guarantee that held only for some seasons would give nothing. Nonnegativity of costs justifies exchanging the order of averaging.
Common mistake
(Treating the exponential law as a model of real seasons)
The exponential duration law was introduced as a proof device. The actual competitive guarantee still concerns every fixed duration; it does not assume real seasons follow that law. Averaging a putative better guarantee over any independent duration distribution must preserve the inequality, which is exactly what the lower bound exploits.
An adversary that sees the random choice changes the question
The policy's guarantee fixes before averaging over private coins. It cannot be applied unchanged when is chosen from the policy's realized purchase time.
Counterexample mode
Ending shortly after the observed purchase breaks the independence condition
Suppose an observer waits for the randomized policy to buy at , then ends the season at . The online cost is always , so its expectation is . The offline expected cost satisfies
Consequently the online expected cost is strictly larger than in this correlated experiment. The duration depends on the private random threshold through the observed purchase. This violates the oblivious-input hypothesis; it does not contradict the fixed-duration theorem.
State the model before transferring the policy
Common mistake
(Confusing a price with a duration)
With rental rate and buying price , the break-even time is in time units. Dividing monetary costs by reduces the model to rental rate one and purchase cost . Confusing a price with a duration produces the wrong threshold when the rental rate is not one.
Discrete rental periods, discounts, resale value, predictions about duration and other observations change the available policies or their costs. The exact constants proved here belong to the specified continuous-time, no-refund model. Computational work and sampling precision are also distinct from competitive cost; the ideal continuous random variable is part of the mathematical algorithm.
Exercises with solutions
Quick check
(Renting costs 2 units per time unit and buying costs 10 units. Find the deterministic break-even buying time. Compute the policy and offline costs for durations 4, 5 and 6 under the stated tie convention.)
Solution · Answer
The time threshold is . At durations 4 and 5, the policy only rents, costing 8 and 10; these are also the offline costs. At duration 6 it has rented for 5 units of time and then bought, costing , while the offline cost is 10. The resulting ratios are 1, 1 and 2. Using time threshold 10 would confuse price units with time units.
Quick check
(For the optimal randomized policy, compute . Derive the inverse-CDF expression and the median purchase time. Is choosing a uniform time the same distribution?)
Solution · Answer
The probability is , less than . Solving gives . Setting gives median , greater than since . A uniform purchase time has midpoint probability and a different worst-case ratio, as the counterexample shows.
Quick check
(Against the policy with density , an observer sets after seeing the purchase. Find the expected online cost and explain why comparing it with the offline expectation can exceed the fixed-duration competitive factor.)
Solution · Answer
The expected online cost is . Meanwhile , so the ratio of expectations is greater than . This comparison uses a duration correlated with the policy's coins. The proved theorem keeps duration fixed while averaging over those coins; conditioning its duration on the observed purchase changes that probability experiment.
Quick check
(For the lower-bound proof, take an exponential duration of mean and a fixed buying time . Compute expected rental and buying costs, the offline expected cost, and explain what happens for a random mixture of buying times.)
Solution · Answer
The expected rental cost is and expected buying cost is , summing to . The offline expectation is , so their ratio is .
Every fixed threshold, including never buying, has expected online cost under this independently chosen duration law. A random mixture independent of the duration therefore still has expectation . If a policy promised a smaller factor for every fixed input duration, averaging that promise would contradict this calculation. The lower-bound law does not give the algorithm advance knowledge of the realized duration.