Skip to main content
Theorem
Path
Curriculum
Paths
Labs
Diagnostic
Case Study
Blog
Search
Sign in
Quiz Hub
/
Stochastic Processes for ML
Stochastic Processes for ML
5 selected
Difficulty 7-8
5 unseen
View topic
Advanced
New
0 answered
5 advanced
Adapts to your performance
Question 1 of 5
120s
advanced (7/10)
state theorem
Azuma-Hoeffding gives
P
(
∣
S
n
∣
≥
t
)
≤
2
exp
(
−
t
2
/
(
2
∑
i
b
i
2
))
for a martingale difference sequence with
∣
D
i
∣
≤
b
i
. What is the *minimum* assumption on the
D
i
that this requires, beyond boundedness?
Hide and think first
A.
Pairwise uncorrelatedness
E
[
D
i
D
j
]
=
0
for all
i
=
j
; the MDS structure then follows mechanically from variance computations and the tower property.
B.
Mutual independence of the
D
i
; Azuma is just Hoeffding for bounded independent variables restated under the alternative martingale-difference-sequence notation.
C.
E
[
D
i
∣
F
i
−
1
]
=
0
(the MDS property); full independence is *not* required, and Azuma applies broadly to dependent sequences.
D.
Sub-Gaussianity of each
D
i
marginally; the bounded-increment assumption is the special case of sub-Gaussian with parameter
σ
i
=
b
i
for the increment range.
Show Hint
Submit Answer
I don't know