Skip to main content
MathOverflow

Return to Question

formatting, added tag
Source Link
YCor
YCor
  • 63.9k
  • 5
  • 187
  • 286

Probabilistic Methodmethod Alon and Spencer Azuma's Inequalityinequality

Theorem 7.5.2 states:

Let $v_1, \dots, v_n$ be vectors with $||v_i|| \leq 1.$$\|v_i\| \leq 1.$ Let $\epsilon_1, \dots, \epsilon_n \in \{-1, 1\}$ be independent with uniform probability and let $X=||\epsilon_1 v_1 + \dots + \epsilon_n v_n||.$$X=\|\epsilon_1 v_1 + \dots + \epsilon_n v_n\|.$ Then $$\Pr[X - \mathbb{E}[X]] > \lambda \sqrt{n}] < e^{-\lambda^2/2},$$ $$\Pr[X - \mathbb{E}[X]] < \lambda \sqrt{n}] < e^{-\lambda^2/2}.$$

In the solution they state that the corresponding martingale $X_0, \dots, X_n$ obtained by exposing each edge one at a time satisfies $|X_{i+1}-X_i| \leq 2$. Why is this?

Probabilistic Method Alon and Spencer Azuma's Inequality

Theorem 7.5.2 states:

Let $v_1, \dots, v_n$ be vectors with $||v_i|| \leq 1.$ Let $\epsilon_1, \dots, \epsilon_n \in \{-1, 1\}$ be independent with uniform probability and let $X=||\epsilon_1 v_1 + \dots + \epsilon_n v_n||.$ Then $$\Pr[X - \mathbb{E}[X]] > \lambda \sqrt{n}] < e^{-\lambda^2/2},$$ $$\Pr[X - \mathbb{E}[X]] < \lambda \sqrt{n}] < e^{-\lambda^2/2}.$$

In the solution they state that the corresponding martingale $X_0, \dots, X_n$ obtained by exposing each edge one at a time satisfies $|X_{i+1}-X_i| \leq 2$. Why is this?

Probabilistic method Alon and Spencer Azuma's inequality

Theorem 7.5.2 states:

Let $v_1, \dots, v_n$ be vectors with $\|v_i\| \leq 1.$ Let $\epsilon_1, \dots, \epsilon_n \in \{-1, 1\}$ be independent with uniform probability and let $X=\|\epsilon_1 v_1 + \dots + \epsilon_n v_n\|.$ Then $$\Pr[X - \mathbb{E}[X]] > \lambda \sqrt{n}] < e^{-\lambda^2/2},$$ $$\Pr[X - \mathbb{E}[X]] < \lambda \sqrt{n}] < e^{-\lambda^2/2}.$$

In the solution they state that the corresponding martingale $X_0, \dots, X_n$ obtained by exposing each edge one at a time satisfies $|X_{i+1}-X_i| \leq 2$. Why is this?

Source Link
Marina Drygala
Marina Drygala
  • 75
  • 3

Probabilistic Method Alon and Spencer Azuma's Inequality

Theorem 7.5.2 states:

Let $v_1, \dots, v_n$ be vectors with $||v_i|| \leq 1.$ Let $\epsilon_1, \dots, \epsilon_n \in \{-1, 1\}$ be independent with uniform probability and let $X=||\epsilon_1 v_1 + \dots + \epsilon_n v_n||.$ Then $$\Pr[X - \mathbb{E}[X]] > \lambda \sqrt{n}] < e^{-\lambda^2/2},$$ $$\Pr[X - \mathbb{E}[X]] < \lambda \sqrt{n}] < e^{-\lambda^2/2}.$$

In the solution they state that the corresponding martingale $X_0, \dots, X_n$ obtained by exposing each edge one at a time satisfies $|X_{i+1}-X_i| \leq 2$. Why is this?