Return to Question

If $X_1, \ldots X_n$ are independent real-valued random variables such that $E[X_k] = 0$ and $E[X_k^2]$ is finite for each $k$, Kolmorogov's inequality gives an upper bound on $P[\max_{1\le k \le n}|S_k| < \lambda]$, where $S_k = X_1 + \ldots X_k$. In some work relating to Dvoretzky's stochastic approximation theorem, a colleague and I are looking for a bound where the sums of prefixes $S_k$ are replaced by sums of contiguous subsequences $S_k - S_j$. I.e., under the same assumptions on the $X_k$, we would like a bound, tending to $0$ as $\lambda \to 0$, on $P[\max_{1\le j < k \le n}[|S_k - S_j| < \lambda]$. This seems like a natural thing to ask for, but we haven't been able to find anything in the literature that we can adapt to give such a bound. We would be very grateful for any pointers or hints. Alternatively, we would be very interested in a counter-example showing that $P[\max_{1\le j < k \le n}|S_k - S_j| < \lambda]$ need not tend to $0$ as $\lambda \to 0$.

Edit: apologies, there is a repeated and highly significant typo in the above: "${} < \lambda$" should read "${} > \lambda$" throughout. What we a are looking for is an upper bound, tending to $0$ as $\lambda \to \infty$ on $P[\max_{1\le j < k \le n}[|S_k - S_j| < \lambda]$.

If $X_1, \ldots X_n$ are independent real-valued random variables such that $E[X_k] = 0$ and $E[X_k^2]$ is finite for each $k$, Kolmorogov's inequality gives an upper bound on $P[\max_{1\le k \le n}|S_k| < \lambda]$, where $S_k = X_1 + \ldots X_k$. In some work relating to Dvoretzky's stochastic approximation theorem, a colleague and I are looking for a bound where the sums of prefixes $S_k$ are replaced by sums of contiguous subsequences $S_k - S_j$. I.e., under the same assumptions on the $X_k$, we would like a bound, tending to $0$ as $\lambda \to 0$, on $P[\max_{1\le j < k \le n}[|S_k - S_j| < \lambda]$. This seems like a natural thing to ask for, but we haven't been able to find anything in the literature that we can adapt to give such a bound. We would be very grateful for any pointers or hints. Alternatively, we would be very interested in a counter-example showing that $P[\max_{1\le j < k \le n}|S_k - S_j| < \lambda]$ need not tend to $0$ as $\lambda \to 0$.

Edit: apologies, there is a repeated and highly significant typo in the above: "${} < \lambda$" should read "${} > \lambda$" throughout. What we are looking for is an upper bound, tending to $0$ as $\lambda \to \infty$ on $P[\max_{1\le j < k \le n}[|S_k - S_j| > \lambda]$.

If $X_1, \ldots X_n$ are independent real-valued random variables such that $E[X_k] = 0$ and $E[X_k^2]$ is finite for each $k$, Kolmorogov's inequality gives an upper bound on $P[\max_{1\le k \le n}|S_k| < \lambda]$, where $S_k = X_1 + \ldots X_k$. In some work relating to Dvoretzky's stochastic approximation theorem, a colleague and I are looking for a bound where the sums of prefixes $S_k$ are replaced by sums of contiguous subsequences $S_k - S_j$. I.e., under the same assumptions on the $X_k$, we would like a bound, tending to $0$ as $\lambda \to 0$, on $P[\max_{1\le j < k \le n}[|S_k - S_j| < \lambda]$. This seems like a natural thing to ask for, but we haven't been able to find anything in the literature that we can adapt to give such a bound. We would be very grateful for any pointers or hints. Alternatively, we would be very interested in a counter-example showing that $P[\max_{1\le j < k \le n}|S_k - S_j| < \lambda]$ need not tend to $0$ as $\lambda \to 0$.

Edit: apologies, there is a repeated and highly significant typo in the above: "${} < \lambda$" should read "${} > \lambda$" throughout. What we a are looking for is an upper bound, tending to $0$ as $\lambda \to 0$ on $P[\max_{1\le j < k \le n}[|S_k - S_j| < \lambda]$.

If $X_1, \ldots X_n$ are independent real-valued random variables such that $E[X_k] = 0$ and $E[X_k^2]$ is finite for each $k$, Kolmorogov's inequality gives an upper bound on $P[\max_{1\le k \le n}|S_k| < \lambda]$, where $S_k = X_1 + \ldots X_k$. In some work relating to Dvoretzky's stochastic approximation theorem, a colleague and I are looking for a bound where the sums of prefixes $S_k$ are replaced by sums of contiguous subsequences $S_k - S_j$. I.e., under the same assumptions on the $X_k$, we would like a bound, tending to $0$ as $\lambda \to 0$, on $P[\max_{1\le j < k \le n}[|S_k - S_j| < \lambda]$. This seems like a natural thing to ask for, but we haven't been able to find anything in the literature that we can adapt to give such a bound. We would be very grateful for any pointers or hints. Alternatively, we would be very interested in a counter-example showing that $P[\max_{1\le j < k \le n}|S_k - S_j| < \lambda]$ need not tend to $0$ as $\lambda \to 0$.

Edit: apologies, there is a repeated and highly significant typo in the above: "${} < \lambda$" should read "${} > \lambda$" throughout. What we a are looking for is an upper bound, tending to $0$ as $\lambda \to \infty$ on $P[\max_{1\le j < k \le n}[|S_k - S_j| < \lambda]$.

If $X_1, \ldots X_n$ are independent real-valued random variables such that $E[X_k] = 0$ and $E[X_k^2]$ is finite for each $k$, Kolmorogov's inequality gives an upper bound on $P[\max_{1\le k \le n}|S_k| > \lambda]$, where $S_k = X_1 + \ldots X_k$. In some work relating to Dvoretzky's stochastic approximation theorem, a colleague and I are looking for a bound where the sums of prefixes $S_k$ are replaced by sums of contiguous subsequences $S_k - S_j$. I.e., under the same assumptions on the $X_k$, we would like a bound, tending to $0$ as $\lambda \to 0$, on $P[\max_{1\le j < k \le n}[|S_k - S_j| > \lambda]$. This seems like a natural thing to ask for, but we haven't been able to find anything in the literature that we can adapt to give such a bound. We would be very grateful for any pointers or hints. Alternatively, we would be very interested in a counter-example showing that $P[\max_{1\le j < k \le n}|S_k - S_j| > \lambda]$ need not tend to $0$ as $\lambda \to 0$.

If $X_1, \ldots X_n$ are independent real-valued random variables such that $E[X_k] = 0$ and $E[X_k^2]$ is finite for each $k$, Kolmorogov's inequality gives an upper bound on $P[\max_{1\le k \le n}|S_k| < \lambda]$, where $S_k = X_1 + \ldots X_k$. In some work relating to Dvoretzky's stochastic approximation theorem, a colleague and I are looking for a bound where the sums of prefixes $S_k$ are replaced by sums of contiguous subsequences $S_k - S_j$. I.e., under the same assumptions on the $X_k$, we would like a bound, tending to $0$ as $\lambda \to 0$, on $P[\max_{1\le j < k \le n}[|S_k - S_j| < \lambda]$. This seems like a natural thing to ask for, but we haven't been able to find anything in the literature that we can adapt to give such a bound. We would be very grateful for any pointers or hints. Alternatively, we would be very interested in a counter-example showing that $P[\max_{1\le j < k \le n}|S_k - S_j| < \lambda]$ need not tend to $0$ as $\lambda \to 0$.

Edit: apologies, there is a repeated and highly significant typo in the above: "${} < \lambda$" should read "${} > \lambda$" throughout. What we a are looking for is an upper bound, tending to $0$ as $\lambda \to 0$ on $P[\max_{1\le j < k \le n}[|S_k - S_j| < \lambda]$.