Azuma Predictable Bets

Worked Example

Consider a predictable policy called "Reduce below zero" over n=6 steps with a threshold t=2. The policy sets the bet size b_i = 1 if the current wealth S_i ≥ 0, and b_i = 0.5 if S_i < 0. The maximum possible step size remains c_i = 1. The total deterministic squared bound budget is B² = \sum_(i=1)^n c_i² = n = 6.

By generating all 2^6 = 64 equally likely coin paths and evaluating S_6 for each, we find exactly 16 paths where S_6 ≥ 2. Thus, the exact upper tail probability is:

1. Count the paths: 16
2. Total paths: 64
3. Exact probability: 16 / 64 = 0.25

Using Azuma's inequality, the deterministic upper bound is:

P(S_6 >= 2) <= exp(-t^2 / (2 * n)) = exp(-2^2 / (2 * 6)) = exp(-4 / 12) = exp(-1/3) ≈ 0.7165313105737893

The bound of approximately 0.7165 is completely valid and correctly upper bounds the true probability of 0.25.

Experiment

In the Azuma Predictable Bets module, you can explore how different predictable policies affect the tail probabilities.

1. Set Policy to "Unit stakes", Steps to 6, and Threshold to 2.
2. Observe that the terminal variance is 6.0 and the exact upper tail probability is 0.34375.
3. Change the Policy to "Stop at two".
4. Observe that the terminal variance drops to 4.75 and the exact tail probability changes to 0.453125. The deterministic squared bound budget remains 6, keeping the Azuma bound at ≈ 0.7165.

Limitations

Azuma's inequality relies on a worst-case deterministic bound on the step sizes (|c_i| ≤ 1). Even if a policy like "Reduce below zero" lowers the actual observed variance (e.g., to 4.0546875), the deterministic bound must still account for the worst-case possible path. Consequently, the Azuma bound can be quite loose compared to the exact probability.

References

The concepts implemented in this module are based on the following resources.

• CS 574 Randomized Algorithms Notes (UIUC) - Covers martingale difference sequences and Azuma's inequality.