Timeline for The frog problem with negative steps
Current License: CC BY-SA 4.0
52 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 26, 2020 at 12:43 | history | rollback | Sextus Empiricus |
Rollback to Revision 15
|
|
| S Oct 29, 2019 at 15:02 | history | bounty ended | CommunityBot | ||
| S Oct 29, 2019 at 15:02 | history | notice removed | CommunityBot | ||
| Oct 24, 2019 at 19:48 | vote | accept | Sextus Empiricus | ||
| Oct 24, 2019 at 19:46 | history | edited | Sextus Empiricus | CC BY-SA 4.0 |
I can't change my username into my desired pseudonym so I place it in the post
|
| S Oct 21, 2019 at 13:29 | history | bounty started | Sextus Empiricus | ||
| S Oct 21, 2019 at 13:29 | history | notice added | Sextus Empiricus | Improve details | |
| S Oct 12, 2019 at 13:02 | history | bounty ended | CommunityBot | ||
| S Oct 12, 2019 at 13:02 | history | notice removed | CommunityBot | ||
| Oct 10, 2019 at 12:12 | comment | added | EngrStudent | This feels like a discretized random walk. | |
| Oct 10, 2019 at 10:24 | comment | added | Sextus Empiricus | @quester with a fixed number of tiles behind the frog it is not so easy either. | |
| Oct 10, 2019 at 10:21 | history | edited | Sextus Empiricus |
edited tags
|
|
| Oct 10, 2019 at 10:20 | comment | added | quester | try to solve it with $n$ possible tiles and then compute $\lim_{n -> \infty} J_1$ and so on | |
| Oct 10, 2019 at 9:06 | comment | added | Sextus Empiricus | @Hans I have moved the discussion to the Partial results answer | |
| Oct 10, 2019 at 6:23 | comment | added | Sextus Empiricus | @Sebastian absorbing random walk can be solved with a differential equation. But this works different it is not like a diffusion process. The frogs from position $x$ move to all places. I guess that this approach is difficult (but it would be nice if it works). | |
| Oct 10, 2019 at 6:13 | comment | added | Haitao Du | 500 reputation... | |
| Oct 10, 2019 at 6:11 | comment | added | Sebastian | This is also somewhat reminiscent of the absorbing random walk. So maybe the derivation of the winning probability for the absorbing random walk can be adjusted to this scenario. | |
| Oct 10, 2019 at 3:11 | answer | added | Sextus Empiricus | timeline score: 5 | |
| Oct 9, 2019 at 22:20 | comment | added | quester | $$J_1 = \frac{1}{2} J_2 + \frac{3}{2}$$ | |
| Oct 9, 2019 at 11:31 | comment | added | Hans | Still, how does the exponential decay of $1-F$ force the finiteness of $J_n$? | |
| Oct 8, 2019 at 20:33 | comment | added | Sextus Empiricus | If $\mu$ can become as small as you like then the fraction of frogs with a position $x>0$ must get as close to zero as you like. | |
| Oct 4, 2019 at 18:30 | comment | added | Aksakal | the recurrence relation is sort of not so useful. The number of paths in J(1) is still infinite, and it also includes in itself J(2), J(3) etc. in that it only looks like it's compressing while you move to smaller N, but it's not. That's what makes the problem much more difficult compared to only moving forward. | |
| Oct 4, 2019 at 16:42 | comment | added | Sextus Empiricus | I filled in the expression J_n = H_n + c and this constant disappeared but maybe I should use a function c (n) | |
| Oct 4, 2019 at 16:28 | comment | added | Sextus Empiricus | That looks very close. My relationship is for f instead of s. | |
| Oct 4, 2019 at 16:10 | comment | added | whuber♦ | BTW, I cannot obtain your recurrence. Letting $f_n$ be the expected number of steps to reach pad $0$ from pad $n,$ the rules imply $$f_n = 1 + \frac{1}{n+1}\left(f_{n+1}+f_n+f_{n-1} + \cdots + f_1\right),$$ leading to a recurrence for $s_n=f_1+f_2+\cdots+f_n$ of the form $$s_{n+1}=(n+1)(s_n-s_{n-1}-1).$$ | |
| Oct 4, 2019 at 15:58 | comment | added | Sextus Empiricus | Yes it will almost certainly terminate, but at first I thought that this might still lead to an infinite expectation value (but the growth is not fast enough). | |
| Oct 4, 2019 at 15:45 | comment | added | whuber♦ | No; it's easy to prove it's almost certain the game on infinitely many leaves will terminate. | |
| Oct 4, 2019 at 14:47 | history | edited | Sextus Empiricus | CC BY-SA 4.0 |
deleted 162 characters in body
|
| Oct 4, 2019 at 14:35 | history | edited | Sextus Empiricus | CC BY-SA 4.0 |
deleted 2 characters in body
|
| Oct 4, 2019 at 14:29 | history | edited | Sextus Empiricus | CC BY-SA 4.0 |
added 424 characters in body
|
| Oct 4, 2019 at 14:18 | answer | added | Aksakal | timeline score: 1 | |
| Oct 4, 2019 at 14:12 | history | edited | Sextus Empiricus | CC BY-SA 4.0 |
added 51 characters in body
|
| Oct 4, 2019 at 14:04 | history | edited | Sextus Empiricus | CC BY-SA 4.0 |
added 51 characters in body
|
| Oct 4, 2019 at 13:57 | history | edited | Sextus Empiricus | CC BY-SA 4.0 |
added 51 characters in body
|
| Oct 4, 2019 at 13:51 | comment | added | Sextus Empiricus | Yes, the game only ends when the frog has no leaves in front of him. If he happens to go very far backwards than 'magically' new leaves will appear behind him (without limit) and the frog will not die or otherwise stop before the game ends. (do you imagine that the expectation value for the number of steps is infinite?) | |
| Oct 4, 2019 at 13:49 | comment | added | whuber♦ | Are you assuming there are infinitely many leaves? (That wasn't part of the original problem.) | |
| Oct 4, 2019 at 13:47 | comment | added | Sextus Empiricus | @whuber a frog that has $n$ leaves in front of him will: - jump to either one of those leaves - jump to the leaf it is currently sitting on - or jump one leaf backwards. Those are $n+2$ options and each of the options has the same $\frac{1}{n+2}$ probability. | |
| Oct 4, 2019 at 13:44 | history | edited | Sextus Empiricus | CC BY-SA 4.0 |
added 74 characters in body
|
| Oct 4, 2019 at 13:20 | comment | added | whuber♦ | I don't understand the question because it's incomplete: although it expands the set of possible transitions, it doesn't specify their probabilities. What are they? And what are the probabilities when the frog is as far from the end as possible, where there is no possibility of jumping backwards? | |
| Oct 4, 2019 at 12:00 | history | tweeted | twitter.com/StackStats/status/1180090326251429889 | ||
| S Oct 4, 2019 at 11:41 | history | bounty started | Sextus Empiricus | ||
| S Oct 4, 2019 at 11:41 | history | notice added | Sextus Empiricus | Draw attention | |
| Sep 16, 2019 at 11:16 | history | edited | Sextus Empiricus | CC BY-SA 4.0 |
added 1210 characters in body
|
| Sep 16, 2019 at 11:08 | history | edited | Sextus Empiricus | CC BY-SA 4.0 |
added 1210 characters in body
|
| Sep 16, 2019 at 10:52 | history | edited | Sextus Empiricus | CC BY-SA 4.0 |
added 1210 characters in body
|
| Sep 16, 2019 at 8:29 | history | edited | Sextus Empiricus | CC BY-SA 4.0 |
deleted 17 characters in body
|
| Sep 16, 2019 at 7:56 | answer | added | polettix | timeline score: 4 | |
| Sep 14, 2019 at 12:58 | history | edited | Sextus Empiricus |
edited tags
|
|
| Sep 14, 2019 at 12:58 | comment | added | Sextus Empiricus | It is indeed much as you describe. Iterative steps where the frog will jump to a leaf in front of him with equal probability untill he reaches the end. That is the problem in the link. In this case the frog can also jump to the same place or one leaf backwards. In the other question I already commented on an alternative solution strategy that should work here as well. | |
| Sep 14, 2019 at 11:55 | comment | added | Stephan Kolassa | What do you mean by "with equal probability"? And are there $n$ leaves? Do you mean that there are $n$ leaves, the frog starts on the 1st one, and he next jumps onto one of the ones ahead of him, with equal probability to jump to each one? And the entire process ends when he arrives at the last leaf? | |
| Sep 14, 2019 at 11:53 | history | edited | Stephan Kolassa | CC BY-SA 4.0 |
deleted 5 characters in body
|
| Sep 14, 2019 at 7:55 | history | asked | Sextus Empiricus | CC BY-SA 4.0 |