Concepts / Bernoulli Variables

Bernoulli Variables

A Chernoff-bound problem begins with independent Bernoulli variables and their sum.

  • Programming

From Outcomes to a Count

Suppose a random experiment records many yes-or-no outcomes. Represent each outcome with a variable that equals 1 for a yes outcome and 0 for a no outcome. The total number of yes outcomes is therefore a sum of these variables. A Chernoff-bound problem studies how likely that total is to cross a chosen threshold, rather than necessarily finding its exact distribution.

contributescontributescontributessuccess probability p₁success probability p₂success probability pₙX₁0 or 1Ztotal yes outcomesX₂0 or 1pp₁ + ··· + pₙXₙ0 or 1
How do individual zero-or-one outcomes and their success probabilities combine into the random count Z?

The Bernoulli Sum

Let X₁, X₂, through Xₙ be independent Bernoulli variables. Each variable records one yes-or-no outcome and equals either 0 or 1. Their total is the random count Z = X₁ + ··· + Xₙ. If the individual success probabilities are p₁, p₂, through pₙ, then the notation p refers to their sum: p = p₁ + ··· + pₙ.

Keep the roles of the symbols separate: Z describes the random count observed in an experiment, while p describes the sum of the individual success probabilities.

Setting Up a Count

Three independent yes-or-no outcomes are represented by X₁, X₂, and X₃, with success probabilities p₁, p₂, and p₃.

Represent each outcome: Each Xᵢ is either 0 or 1, depending on whether its corresponding outcome is no or yes.

Form the random count: The total number of yes outcomes is Z = X₁ + X₂ + X₃.

Combine the probabilities: The quantity denoted by p is p₁ + p₂ + p₃.

The Chernoff setup begins with the independent sum Z and the probability sum p.

Changing the Tail Event

The central proof move is to replace an event involving Z with an event involving an exponential expression. Choose any t greater than 0 and apply the function exp(t·) to both the count and the threshold. Because the exponential function is increasing, the event that Z exceeds a threshold becomes an event in which exp(tZ) exceeds the corresponding exponential threshold.

applyincreasing transformationinvokeZ exceeds thresholdZ > aexp(t·)t > 0exp(tZ) exceedsexp(ta)Markov's inequalitybound the event
What happens when a threshold event for Z is transformed by the increasing function exp(t·)?

Transforming a Threshold

Set up the transformation of the event that Z exceeds a threshold a.

Start with the count event: Consider the event Z > a.

Choose a positive parameter: Let t be any positive number.

Apply the exponential: Since exp(t·) is increasing, the event is compared with exp(tZ) > exp(ta).

Prepare for Markov's inequality: The transformed event is now an exceeding event for the nonnegative exponential quantity exp(tZ).

The original tail event has been converted into an exponential exceeding event that can be bounded with Markov's inequality.

Independence and Factorization

The sum structure remains useful after exponentiation. The exponential of the sum is represented as a product of individual exponential terms. The independence assumption is what permits the corresponding expectation to be handled as separate contributions from the individual variables. This is the point at which the many-variable problem connects back to the individual Bernoulli variables.

apply exp(t·)rewriteindependence enablesZ = X₁ + ··· + Xₙexp(tZ)exponential of a sumProduct of exp(tXᵢ)one factor per variableSeparate expectationsindependence
How does the exponential of a Bernoulli sum become a product whose separate terms can be handled using independence?

Applying Markov's Inequality

Markov's inequality supplies the bounding step. After the threshold event has been changed into an event involving exp(tZ), Markov's inequality is applied to that transformed quantity. Thus, the Chernoff method combines two roles: the exponential transformation changes the form of the event, and Markov's inequality bounds the probability of the resulting exceeding event.

choose thresholdtransform with t > 0applyobtainIndependentBernoulli sumZ = X₁ + ··· + XₙThreshold eventZ > aExponential eventexp(tZ) > exp(ta)Markov boundtransformed probabilityChernoff-bound familyone bound for each t > 0
How is the event that Z crosses a threshold converted into a probability bound?

The result is a family of valid bounds indexed by t. The derivation is valid for every t greater than 0; it does not begin by assuming one special value.

Choosing the Parameter

The positive parameter t controls the exponential scale. Changing t changes how strongly different values of Z are separated by the transformation exp(tZ), and it changes the resulting upper bound. The proof strategy is therefore to construct a valid bound for every positive t and then choose a value that makes the bound useful when the intermediate inequality is combined with the earlier equation.

setsproducesselect useful valueAny t > 0valid derivationExponential scaleexp(tZ)Bound indexed by tdifferent upper boundst = log(1 + δ)source's stated choice
How does the choice of t change the exponential transformation and the available probability bound?

Common Mistakes

  • Treating p as the success probability of one particular variable.

    In this setup, p denotes the sum of the individual success probabilities.

    Fix: Keep p₁, p₂, through pₙ attached to the individual variables and use p for their sum.

  • Applying Markov's inequality directly to the original count without describing the exponential transformation.

    The Chernoff proof route first changes the threshold event into one involving exp(tZ).

    Fix: Show the monotone exponential transformation before identifying the quantity to which Markov's inequality is applied.

  • Choosing a single t before constructing the general bound.

    The derivation is valid for every t greater than 0, and the useful value is selected later.

    Fix: Treat t as a positive parameter that indexes a family of valid bounds.

  • Confusing Markov's inequality with the whole Chernoff method.

    Markov supplies the probability bound, while the exponential transformation creates the form used by the Chernoff argument.

    Fix: Explain the two roles together.

Practice Setup

MEDIUM

Let X₁, through Xₙ be independent Bernoulli variables with individual success probabilities p₁, through pₙ. Write the random count Z, identify the quantity p, and outline how you would begin bounding the event that Z exceeds a threshold a.

Hints
  • Start by adding the individual variables.
  • Use p for the sum of the individual success probabilities.
  • Choose t greater than 0, apply the increasing function exp(t·), and then identify where Markov's inequality enters.

What do you think happens?

Before reading the outline, what should happen to the event Z > a when t is positive and the exponential function is applied?

  • It becomes an event comparing exp(tZ) with exp(ta).
  • It becomes an event comparing tZ with a divided by t.
  • It disappears because exponentiation changes probabilities.
Reveal answer

Answer: It becomes an event comparing exp(tZ) with exp(ta).

The exponential function is increasing, so applying exp(t·) preserves the threshold comparison while changing its scale.

Summary

  1. Independent Bernoulli variables each record a zero-or-one outcome, and their sum Z records the total number of yes outcomes.
  2. The symbol p denotes the sum of the individual success probabilities.
  3. For t greater than 0, the increasing exponential function changes a threshold event for Z into an exceeding event for exp(tZ).
  4. Markov's inequality bounds the transformed event, while independence supports separating the contributions from the individual variables.
  5. The parameter t generates a family of valid bounds; the stated choice in the source is t = log(1 + δ).

Key Takeaways

  • A Bernoulli sum counts yes outcomes by adding independent variables that each equal 0 or 1.
  • The sum of individual success probabilities is denoted by p, while Z denotes the random count.
  • Chernoff's method transforms a threshold event for Z into an exponential exceeding event.
  • Markov's inequality bounds the transformed event, and independence enables separate treatment of the individual terms.
  • The positive parameter t controls the transformation and is selected later to produce a useful bound.

Related Topics

  • Markov's Inequality
  • Chernoff Bounds
  • Independent Random Variables