Timeline for Expected number of forward jumps to reach a given quantile of a rv [closed]
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 28, 2016 at 19:53 | comment | added | Douglas Zare | It's a little simpler if you just count the times that there is a greatest-so-far draw below the threshold. You know there will be precisely one draw above the threshold with probability $1$. You can recognize the power series, so there is actually no computation needed. | |
| Feb 28, 2016 at 19:13 | comment | added | usul | @DouglasZare, OK I see it now. The expected number of switches is the sum, over the die rolls, of the probability that it is a switch. The probability the $k$th die roll is a switch is the probability that no previous roll exceeded quantile $1-\rho$, times $q_k$, the chance this roll is the highest given that fact. Then $q_k = \rho + (1-\rho)/k$, as with probability $\rho$ this roll is in the highest quanitle, and otherwise it has a $1/k$ chance of being largest thus far. This gives $\sum_k (1-\rho)^{k-1}(\rho + (1-\rho)/k)$. I get this to be exactly $\log(1/\rho)$ not counting the first roll. | |
| Feb 28, 2016 at 16:08 | comment | added | Douglas Zare | There are no integrals required. The conditional probability that the $17$th number drawn from a continuous distribution is the largest is $1/17$ by symmetry. | |
| Feb 28, 2016 at 15:04 | comment | added | usul | @DouglasZare, I still don't see how to find a closed form for the probability of occurrence of, say, the 7th or 17th change, let alone a closed form for the infinite sum. I just get a bunch of increasingly nasty integrals. Apologies if I am being dense. | |
| Feb 28, 2016 at 7:49 | review | Reopen votes | |||
| Feb 28, 2016 at 8:43 | |||||
| Feb 28, 2016 at 7:33 | history | edited | aroyc | CC BY-SA 3.0 |
explanation added to make clear it's connection with my research
|
| Feb 28, 2016 at 7:02 | history | closed |
Douglas Zare Wolfgang Stefan Kohl♦ Ryan Budney Myshkin |
Not suitable for this site | |
| Feb 28, 2016 at 3:34 | comment | added | Douglas Zare | The expected number is a sum of probabilities, each of which is easy to compute if the distribution is continuous. | |
| Feb 27, 2016 at 22:08 | comment | added | usul | @DouglasZare, good point about the assumption! But I don't understand your hint. | |
| Feb 27, 2016 at 15:13 | review | Close votes | |||
| Feb 28, 2016 at 7:02 | |||||
| Feb 27, 2016 at 14:59 | comment | added | Douglas Zare | @usul: You are assuming that the distribution is continuous. If so, this problem is an easy exercise if you add up the probabilities of changes on each step. | |
| Feb 27, 2016 at 14:50 | comment | added | usul | (1) The distribution might as well be Unif[0,1] since you only care about quantiles. (2) Each time we switch, the new "current max" is distributed independently conditioned on exceeding the old current max. (3) In expectation, each switch cuts the interval in half (first number averages $0.5$, etc), so $\log_2(1/\rho)$ should be the right ballpark. | |
| Feb 27, 2016 at 14:43 | comment | added | Douglas Zare | Whether this was assigned to you or not doesn't matter. | |
| Feb 27, 2016 at 13:02 | history | asked | aroyc | CC BY-SA 3.0 |