Timeline for Bound on queries to a tree with unusual probabilities
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 6, 2017 at 2:07 | comment | added | fedja | @MichaelJarret 1) Yes, updating $k_w$ is exactly what makes this example work. 2) My usual response is "Just credit MO in some decent way" but, at any rate, let us solve the problem first (so, yes, by all means post the new version) | |
| Sep 6, 2017 at 1:02 | vote | accept | Michael Jarret | ||
| Sep 6, 2017 at 1:02 | comment | added | Michael Jarret | For just a bit more clarification, the idea in your example is to update $k_w$ as we go so that I'm always likely to move along the path, but not likely to jump to a leaf. Then, I'm always unlikely to simply jump to a bush, so I just end up progressing down a limited path and end up just chasing the next-deepest leaves. This seems to be correct for the problem as stated, which means that the other conditions (which I may post as a follow up problem if you're interested) are actually relevant. This will be part of a paper, how would you like to be credited? Is your mathoverflow handle okay? | |
| Sep 5, 2017 at 13:58 | comment | added | Michael Jarret | I think i get this now. The probabilities from the bush itself cause me to approach the bush, but I'm more likely to just jump past it than actually sample a leaf. We then repeat this process a bunch. If I'm right, this is proof that I need more constraints. Thanks, I will potentially be asking a new version of this problem with additional constraints that make the scenario you describe impossible. (These constraints exist in the original problem, but I previously deemed them unnecessary for this argument.) | |
| Sep 5, 2017 at 13:50 | comment | added | fedja | Indeed, if you arrive at a bush, then you end up in the leaf with high probability. The whole point is that it is very unlikely to do so because at each step you have at least $m$ vertices on the path to choose from out of which only $2$ are bush roots and the probability to go directly to a leaf of the second bush is negligible. Since you seem to be a visual person like myself, I added the picture of $k_w$ as well. The double translation (picture -> text -> picture) can, indeed, be too much :-) | |
| Sep 5, 2017 at 13:47 | history | edited | fedja | CC BY-SA 3.0 |
added 160 characters in body
|
| Sep 5, 2017 at 3:00 | comment | added | Michael Jarret | thanks for the graphic, that was very helpful in clarifying your example. I still don't understand why this example would require more than $\sim log(m)$ steps, however. It seems that when one arrives at any bush, one samples a leaf with very high probability. I assume there's something about your adjustment of the probability function, but I didn't quite follow that part. | |
| Sep 5, 2017 at 1:20 | history | edited | fedja | CC BY-SA 3.0 |
added 17 characters in body
|
| Sep 5, 2017 at 1:11 | comment | added | fedja | @MichaelJarret I added a graph example to avoid any notation misunderstanding. What else is unclear? | |
| Sep 5, 2017 at 1:10 | history | edited | fedja | CC BY-SA 3.0 |
added 86 characters in body
|
| Sep 4, 2017 at 23:30 | comment | added | Michael Jarret | I can no longer edit my own comment, but there might be a notational issue above. Did you mean m leaves at every m-th vertex or m leaves at ever n-th vertex? If the latter, I should have said that it seems like the result scales like log(n), not log(m). Regardless, I may just not be understanding your argument. Thanks for the help. | |
| Sep 4, 2017 at 23:16 | comment | added | Michael Jarret | I don't think that I fully follow this. We're only looking for the probability that we find some leaf, not a particular leaf. Does this still hold in that case? It seems like, in the example you're describing (if I'm actually understanding it) we would find some leaf in expected number of steps log(m) since this is approximately the same problem as the path. It is a few examples like this that motivated the conjecture. | |
| Sep 4, 2017 at 23:07 | history | answered | fedja | CC BY-SA 3.0 |