Timeline for Counting permutations defined by a simple process
Current License: CC BY-SA 4.0
28 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 15, 2022 at 20:47 | vote | accept | macat | ||
| Mar 15, 2022 at 20:44 | comment | added | macat | @Iosif Pinelis, This question did not turned out as I hoped it would, and my question remains unanswered. Nevertheless, I found the discussion extremely helpful, and I am greatfull for your time. The formula you suggested is indeed simpler than anything I had before (including my conjectured formula)! Should I fail to extend it for the desired problem, I will ask for help in a new question in a few days. Thank you again! | |
| Mar 15, 2022 at 17:36 | comment | added | Iosif Pinelis | Previous comment continued: However, (i) the two-ball setting is not mentioned in your post, (ii) this modified setting, briefly mentioned only in a comment of yours, is open to different interpretations (in my view), and (iii) your conjectured expression does not seem to have a good chance to be proved and then successfully used. Therefore, the present question seems now ripe for a resolution, and the two-ball setting could be explained in detail in a separate post. | |
| Mar 15, 2022 at 17:34 | comment | added | Iosif Pinelis | @macat : The all-positive-terms expression in my answer is substantially simpler than your conjectured alternating-sign expression. Moreover, the all-positive expression is proved (rather than conjectured) and, moreover, used to prove the desired bound and asymptotics. No such prospects for your conjectured expression are in sight and can hardly be expected. It appears that my approach has so far the best prospects to be extended to two balls changing the color. | |
| Mar 15, 2022 at 16:39 | comment | added | macat | I can still not see how to generalize the formula of @Iosif Pinelis without the sums getting very ugly. | |
| Mar 15, 2022 at 16:01 | comment | added | macat | @Max Alekseyev, I am sure this would give the right formula, but how would I prove my upper bound to that variant of the formula? (I can not prove it even for the easier case.) | |
| Mar 15, 2022 at 15:56 | comment | added | Max Alekseyev | @macat: Switching to the variation amounts to replacing the expression $(r_2 + r_3 + 2(r_4+r_5) + \dots)$, which stands for the number of suitable places for the marked ball, with $(r_2 + 2(r_3+r_4) + 3r_5 + 4(r_6+r_7) + 5r_8 + \dots)$ or alike. Otherwise it goes along the same lines. | |
| Mar 15, 2022 at 15:41 | comment | added | macat | @Iosif Pinelis, Thank you. I am trying to generailse your formula for the more complicated case I mentioned in the comments (when two consequtive balls become blue instead of just one). I wonder how complicated it is going to be. | |
| Mar 15, 2022 at 4:38 | comment | added | Iosif Pinelis | @macat : (i) I have further simplified the expression, which is now very easy to analyze. (ii) Now it is also proved that, for $n=2k-1$, indeed $1/3$ is the exact upper bound on the probability of the marked red ball turning blue and this probability goes to $1/3$ as $k\to\infty$. | |
| Mar 15, 2022 at 2:33 | comment | added | macat | @Max Alekseyev, It is not clear how to work with your expression. I do not insist to my formula if I can show the bound mentioned in the previous comment for another one. | |
| Mar 15, 2022 at 2:33 | comment | added | macat | @Iosif Pinelis, In the setting of the original question, I want to prove that the probability of the marked red ball going blue is at most $1/3$ if $n\geq 2(k-1)+1$ (we can assume $n = 2(k-1)+1$). It would be a nice addition to see that the probability for $k$ and $n = 2(k-1)+1$ goes to $1/3$ as $k\rightarrow\infty$. Note that $n = 2(k-1)+1$ is the smallest number of balls where all $k$ red balls may remain red. | |
| Mar 15, 2022 at 0:07 | comment | added | Iosif Pinelis | @macat : (i) It should be pretty straightforward to modify my approach to the case of the two subsequent balls changing the color. (ii) The advantage of my expression is that all terms in it are positive, which should make it significantly easier to upper-bound (and to lower-bound) it. What kind of upper bound are you looking for? | |
| Mar 14, 2022 at 23:18 | comment | added | Max Alekseyev | @macat: My approach well extends to this variation as well. | |
| Mar 14, 2022 at 21:58 | comment | added | macat | Based on computer evaluations, I am quite confident that my formula is correct. I am also interested in the problem when for the $i$-th tick, if the $i$-th ball is red, then it colors both the $(i+1)$-th and the $(i+2)$-th ball blue (now we have only $n-2$ ticks). My formula nicely transfers to this more complicated problem. My aim is to give upper bound on the probability of a red ball turning blue --- this does not look easy with the other formulas posted in this thread even for the simper version of the problem. But maybe I am wrong in this regard. | |
| Mar 14, 2022 at 20:27 | comment | added | Iosif Pinelis | The expression in my answer coincides with your conjectured (?) expression for $n=1,\dots,40$ and $k=1,\dots,n$. I think it could be helpful if you can disclose how you arrived at your expression (and also, perhaps, why it is of interest). | |
| Mar 14, 2022 at 20:03 | history | edited | macat | CC BY-SA 4.0 |
added 151 characters in body
|
| Mar 14, 2022 at 18:10 | answer | added | Max Alekseyev | timeline score: 2 | |
| Mar 14, 2022 at 18:03 | comment | added | Peter Taylor | The straightforward inclusion-exclusion on the length of the run of red balls up to the marked ball gives $$(k-1) \sum_{j=0}^{k-2} (-1)^j \frac{(k-2)!(n-1-j)!}{(k-2-j)!}$$but the term values differ from your sum. It might still be worth rearranging your sum as $$(k-1) \sum_{j=0}^{k-2}(-1)^j\frac{n!2^{k-2-j} \binom{k-2}{j}}{n-j}$$since the $(k-1)$ and $\binom{k-2}j$ have easy combinatorial explanations. | |
| Mar 14, 2022 at 17:43 | answer | added | Iosif Pinelis | timeline score: 2 | |
| Mar 14, 2022 at 16:19 | history | edited | macat | CC BY-SA 4.0 |
added 8 characters in body
|
| Mar 14, 2022 at 16:18 | comment | added | macat | @Max Alekseyev, The balls are labelled, so there are $n!$ permutations. | |
| Mar 14, 2022 at 16:14 | comment | added | macat | @Iosif Pinelis, you are right, it would be clearer to say that there are only $n-1$ ticks. The $i$-th ball is the ball at index $i$ in the permutation. Fixed the questions so that this is clear now. | |
| Mar 14, 2022 at 16:11 | history | edited | macat | CC BY-SA 4.0 |
added 40 characters in body
|
| Mar 14, 2022 at 16:10 | comment | added | Max Alekseyev | Is it a permutation of labeled or unlabeled balls? In other words, are the balls of the same color distinguishable? | |
| Mar 14, 2022 at 16:08 | comment | added | Iosif Pinelis | So, you only do $n-1$ ticks? Also, what is "the $i$-th ball"? | |
| Mar 14, 2022 at 15:50 | comment | added | macat | Yes, and the red ball before the marked should not be preceded by another red ball, unless it is preceded by another red one, etc. | |
| Mar 14, 2022 at 15:46 | comment | added | Max Alekseyev | In other words, the marked red ball should follow another red ball in the permutation, shouldn't it? | |
| Mar 14, 2022 at 15:23 | history | asked | macat | CC BY-SA 4.0 |