Timeline for Distribution of a maximum
Current License: CC BY-SA 3.0
17 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 1, 2012 at 16:21 | vote | accept | Fan Zhang | ||
| Dec 20, 2011 at 12:20 | comment | added | Johan Wästlund | Fan Zhang: The difference $S_n-S_k$ is distributed like $S_{n-k}$ (a sum of independent $W$'s). By the central limit theorem, such a sum, suitably rescaled, approaches normal distribution, and in particular the probability that it is smaller (greater) than its mean approaches $1/2$. Therefore it is certainly bounded away from 0 and 1. I guess $C=1/e$ will do (the probability of a single exponential being larger than its mean), but I don't see at the moment how to prove that. | |
| Dec 11, 2011 at 16:44 | comment | added | Fan Zhang | @JohanWastlund Hi Johan, I review the problem today, I am not quite clear about how to get the following inequality: $ \Pr (|S_n - n| > t) \geq C\cdot \Pr(|S_k-k| > t \text{for some} k \leq n) $? And how to determine $C$ | |
| Dec 11, 2011 at 12:32 | vote | accept | Fan Zhang | ||
| Dec 11, 2011 at 16:21 | |||||
| Dec 11, 2011 at 12:32 | vote | accept | Fan Zhang | ||
| Dec 11, 2011 at 12:32 | |||||
| Nov 7, 2011 at 11:01 | history | edited | Johan Wästlund | CC BY-SA 3.0 |
added 1154 characters in body; deleted 1 characters in body; added 14 characters in body
|
| Nov 5, 2011 at 4:13 | comment | added | Fan Zhang | @JohanWastlund Hi Johan, what about your new idea? | |
| Oct 30, 2011 at 8:54 | comment | added | Johan Wästlund | Fan Zhang: Sure, I will update my answer! | |
| Oct 28, 2011 at 8:37 | comment | added | Fan Zhang | @JohanWastlund I am not quite clear about your idea. Could you explain it more or put it in the answer? And what is "obvious way" and " standard way"? | |
| Oct 28, 2011 at 7:15 | comment | added | Johan Wästlund | Brendan, was there a typo? I don't see it. | |
| Oct 28, 2011 at 7:14 | comment | added | Johan Wästlund | To return to the discrete problem, we can start by choosing points uniformly in the interval $[0,m-n+1]$, then mapping them to the set $\{1,\dots,m-n+1\}$ in the obvious way (which may lead to repetitions), and finally map to a set of $\{1,\dots,m\}$ without repetitions in the standard way (pushing the $i$th ball $i-1$ bins up). This moves each point another $O(n)$ away from its mean, so we get a high-probability upper bound of $O(m/\sqrt{n} + n)$, where the first term dominates when $m>>n^{3/2}$. On the other hand, if $m$ is only slightly larger than $n$, it must be possible to do better. | |
| Oct 28, 2011 at 3:47 | vote | accept | Fan Zhang | ||
| Oct 28, 2011 at 3:47 | |||||
| Oct 27, 2011 at 15:35 | vote | accept | Fan Zhang | ||
| Oct 28, 2011 at 3:47 | |||||
| Oct 26, 2011 at 5:40 | comment | added | Fan Zhang | @JohanWastlund Do you have any suggestion about the case where it can not be approximated to "selection with replacement". | |
| Oct 25, 2011 at 18:17 | comment | added | Ori Gurel-Gurevich | Very nice. I somehow missed the fact that the $Y_i$'s behave like Brownian motion, so there are strong dependencies and maximum is only $\sqrt{n}$. | |
| Oct 25, 2011 at 15:30 | comment | added | Brendan McKay | Nice approach. You might want to fix the $|X_k-X_k|$. | |
| Oct 25, 2011 at 14:11 | history | answered | Johan Wästlund | CC BY-SA 3.0 |