Skip to main content
MathOverflow

Return to Question

added 102 characters in body
Source Link
Martin Zhang
Martin Zhang
  • 183
  • 6

Let $R_1, R_2, \cdots$ be i.i.d. Rademacher random variables (taking values $-1,+1$ w.p. $0.5$). At time $k$, their average is $\frac{1}{k}\sum_{i=1}^k R_i$. One can imagine after $k\geq n$ for some $n$, this average becomes quite close to zero. It is interesting to characterize the maximum deviation of the average after time $n$: $$ Y_n = \sup_{k\geq n} \frac{1}{k}\sum_{i=1}^k R_i.$$ Since $Y_n$ converges to $0$ as $n$ grows, the characterization should be in terms of $n$. The answer can be upper bounds on either $\mathbb{E}[Y_n]$ or $\mathbb{P}(Y_n \geq t)$.

Specifically, is it possible to have a finite sample bound on the term $\mathbb{P}(Y_n \geq t)$?

A few remarks:

  • My guess is that $Y_n = \tilde{O}_p(\frac{1}{\sqrt{n}})$ , where $\tilde{O}_p$ omits some $\log n$ factor. Yet given the simplicity of the problem, it is desirable to get the exact answer.

  • This is related to the question Expected supremum of average? The difference is there the $sup$ is taken over $1 \leq k \leq n$, where a constant bound can be obtained. Here we are interested in how fast $Y_n$ approaches zero as $n$ grows. Hence the bound should depend on $n$.

  • A concrete example is as follows. Consider a sequence of coin tosses $T_1, T_2, \cdots$. The running estimate of the head probability at time $k$ is $\frac{1}{k} \sum_{i=1}^k I_{\{T_i=head\}}$. Then $Y_n = \sup_{k\geq n} \frac{1}{k} \sum_{i=1}^k I_{\{T_i=head\}}$ is the maximum estimation error of head probability after toss $n$.

Let $R_1, R_2, \cdots$ be i.i.d. Rademacher random variables (taking values $-1,+1$ w.p. $0.5$). At time $k$, their average is $\frac{1}{k}\sum_{i=1}^k R_i$. One can imagine after $k\geq n$ for some $n$, this average becomes quite close to zero. It is interesting to characterize the maximum deviation of the average after time $n$: $$ Y_n = \sup_{k\geq n} \frac{1}{k}\sum_{i=1}^k R_i.$$ Since $Y_n$ converges to $0$ as $n$ grows, the characterization should be in terms of $n$. The answer can be upper bounds on either $\mathbb{E}[Y_n]$ or $\mathbb{P}(Y_n \geq t)$.

A few remarks:

  • My guess is that $Y_n = \tilde{O}_p(\frac{1}{\sqrt{n}})$ , where $\tilde{O}_p$ omits some $\log n$ factor. Yet given the simplicity of the problem, it is desirable to get the exact answer.

  • This is related to the question Expected supremum of average? The difference is there the $sup$ is taken over $1 \leq k \leq n$, where a constant bound can be obtained. Here we are interested in how fast $Y_n$ approaches zero as $n$ grows. Hence the bound should depend on $n$.

  • A concrete example is as follows. Consider a sequence of coin tosses $T_1, T_2, \cdots$. The running estimate of the head probability at time $k$ is $\frac{1}{k} \sum_{i=1}^k I_{\{T_i=head\}}$. Then $Y_n = \sup_{k\geq n} \frac{1}{k} \sum_{i=1}^k I_{\{T_i=head\}}$ is the maximum estimation error of head probability after toss $n$.

Let $R_1, R_2, \cdots$ be i.i.d. Rademacher random variables (taking values $-1,+1$ w.p. $0.5$). At time $k$, their average is $\frac{1}{k}\sum_{i=1}^k R_i$. One can imagine after $k\geq n$ for some $n$, this average becomes quite close to zero. It is interesting to characterize the maximum deviation of the average after time $n$: $$ Y_n = \sup_{k\geq n} \frac{1}{k}\sum_{i=1}^k R_i.$$ Since $Y_n$ converges to $0$ as $n$ grows, the characterization should be in terms of $n$. The answer can be upper bounds on either $\mathbb{E}[Y_n]$ or $\mathbb{P}(Y_n \geq t)$.

Specifically, is it possible to have a finite sample bound on the term $\mathbb{P}(Y_n \geq t)$?

A few remarks:

  • My guess is that $Y_n = \tilde{O}_p(\frac{1}{\sqrt{n}})$ , where $\tilde{O}_p$ omits some $\log n$ factor. Yet given the simplicity of the problem, it is desirable to get the exact answer.

  • This is related to the question Expected supremum of average? The difference is there the $sup$ is taken over $1 \leq k \leq n$, where a constant bound can be obtained. Here we are interested in how fast $Y_n$ approaches zero as $n$ grows. Hence the bound should depend on $n$.

  • A concrete example is as follows. Consider a sequence of coin tosses $T_1, T_2, \cdots$. The running estimate of the head probability at time $k$ is $\frac{1}{k} \sum_{i=1}^k I_{\{T_i=head\}}$. Then $Y_n = \sup_{k\geq n} \frac{1}{k} \sum_{i=1}^k I_{\{T_i=head\}}$ is the maximum estimation error of head probability after toss $n$.

Source Link
Martin Zhang
Martin Zhang
  • 183
  • 6

Concentration inequalities on the supremum of average after time $n$

Let $R_1, R_2, \cdots$ be i.i.d. Rademacher random variables (taking values $-1,+1$ w.p. $0.5$). At time $k$, their average is $\frac{1}{k}\sum_{i=1}^k R_i$. One can imagine after $k\geq n$ for some $n$, this average becomes quite close to zero. It is interesting to characterize the maximum deviation of the average after time $n$: $$ Y_n = \sup_{k\geq n} \frac{1}{k}\sum_{i=1}^k R_i.$$ Since $Y_n$ converges to $0$ as $n$ grows, the characterization should be in terms of $n$. The answer can be upper bounds on either $\mathbb{E}[Y_n]$ or $\mathbb{P}(Y_n \geq t)$.

A few remarks:

  • My guess is that $Y_n = \tilde{O}_p(\frac{1}{\sqrt{n}})$ , where $\tilde{O}_p$ omits some $\log n$ factor. Yet given the simplicity of the problem, it is desirable to get the exact answer.

  • This is related to the question Expected supremum of average? The difference is there the $sup$ is taken over $1 \leq k \leq n$, where a constant bound can be obtained. Here we are interested in how fast $Y_n$ approaches zero as $n$ grows. Hence the bound should depend on $n$.

  • A concrete example is as follows. Consider a sequence of coin tosses $T_1, T_2, \cdots$. The running estimate of the head probability at time $k$ is $\frac{1}{k} \sum_{i=1}^k I_{\{T_i=head\}}$. Then $Y_n = \sup_{k\geq n} \frac{1}{k} \sum_{i=1}^k I_{\{T_i=head\}}$ is the maximum estimation error of head probability after toss $n$.