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.

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

The Bernoulli Sum

Definition

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

Key point

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.

Worked example

Setting Up a Count

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

  1. 1
    Represent each outcome

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

  2. 2
    Form the random count

    The total number of yes outcomes is Z = X₁ + X₂ + X₃.

  3. 3
    Combine the probabilities

    The quantity denoted by p is p₁ + p₂ + p₃.

Result

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.

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

Transforming a Threshold

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

  1. 1
    Start with the count event

    Consider the event Z > a.

  2. 2
    Choose a positive parameter

    Let t be any positive number.

  3. 3
    Apply the exponential

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

  4. 4
    Prepare for Markov's inequality

    The transformed event is now an exceeding event for the nonnegative exponential quantity exp(tZ).

Result

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.

Z = X₁ + ··· + Xₙexp(tZ)exponential of a sumProduct of exp(tXᵢ)one factor per variableSeparate expectationsindependenceapply exp(t·)rewriteindependence enables
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.

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

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.

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

Common Mistakes

  • Common mistake

    Treating p as the success probability of one particular variable.

    What it looks like

    Writing p as though it referred only to X₁.

    Why it fails

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

    Do this instead

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

  • Common mistake

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

    What it looks like

    Jumping from the event Z > a straight to a Chernoff bound.

    Why it fails

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

    Do this instead

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

  • Common mistake

    Choosing a single t before constructing the general bound.

    What it looks like

    Assuming a special value of t is required from the beginning.

    Why it fails

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

    Do this instead

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

  • Common mistake

    Confusing Markov's inequality with the whole Chernoff method.

    What it looks like

    Describing Markov's inequality and the exponential transformation as unrelated steps.

    Why it fails

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

    Do this instead

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

At a glance

  • 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

Related concepts

More concepts starting with B