Concentration Bounds and a High-Probability Guarantee · seed 1 · A4, ink-friendly. The answer key prints on its own page for grown-ups.

From averages to almost-sure promises

Computing · Algorithms & Data Structures · ages 22-23
Name ______________________   Date ____________

  1. Waiting time is nonnegative with mean 6 minutes. Markov caps the chance of waiting 30 minutes or more. Type that cap as a decimal.

    Answer: ______________

  2. A routine averages 10 seconds. What does that alone promise about the next run?

    • Nothing about a single run
    • At most 10 seconds
    • Exactly 10 seconds

  3. Which bound demands independent trials?

    • Markov
    • Chebyshev
    • Chernoff

  4. Trial outcomes share state, so independence fails. Which bound is off the table?

    • Markov
    • Chernoff
    • Neither, all still apply

  5. Scores have mean 50 and standard deviation 4. Chebyshev caps the chance of missing the mean by 8 or more. Type that cap as a decimal.

    Answer: ______________

  6. Expected time is 10 seconds. You fear runs of 50 seconds or more. What does Markov say?

    • At most 1/5 of runs stray that far
    • At most 1/2 of runs stray that far
    • At most 1/50 of runs stray that far

  7. Markov, Chebyshev, and Chernoff all apply to one quantity. Which cap is tightest?

    • Markov, it assumes the least
    • All three always tie
    • Chernoff, bought with the strongest assumption

  8. Mia applies Chernoff to a chain where each step depends on the last. What is wrong?

    • Chernoff needs no assumptions at all
    • Dependent steps void the independence Chernoff requires
    • Chernoff only works below the mean
LightMySky · lightmysky.comW1-mt_WIltjK12oW-s1

Answer key

For grown-ups. Fold this page away before handing over the rest.

From averages to almost-sure promises W1-mt_WIltjK12oW-s1

  1. 0.2 · 30 is 5 times the mean, so the cap is 1/5.
  2. Nothing about a single run · Averages range over runs; one run may stray.
  3. Chernoff · Independence buys the exponential tail.
  4. Chernoff · Without independence, Chernoff does not apply.
  5. 0.25 · 8 is 2 standard deviations, so the cap is 1/4.
  6. At most 1/5 of runs stray that far · 50 is 5 times the mean, giving 1/5.
  7. Chernoff, bought with the strongest assumption · Stronger assumptions pay for sharper statements.
  8. Dependent steps void the independence Chernoff requires · Dependence removes the only license for Chernoff.
Worksheet · LightMySky