Timeline for Expected number of compositions needed to get constant function
Current License: CC BY-SA 4.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 2, 2021 at 20:14 | comment | added | Sophie M | @SamHopkins Yes, $k=1$ is special because a single map generates a commutative monoid; $k \geq 2$ should be different. An average-case version of my question, closer to yours: Fix $k$ and $\ell$. Let $\{ f_1, \dots, f_k \}$ be a set of $k$ distinct maps $[n] \to [n]$ chosen uniformly at random. Let $i_1, \dots, i_{\ell}$ be chosen from $\{ 1, \dots, k \}$ uniformly and independently (both from each other and the $f_i$'s). What is the probability that $f_{i_{\ell}} \circ \cdots \circ f_{i_1}$ is a constant map? | |
| Dec 2, 2021 at 19:37 | comment | added | Sam Hopkins | @SophieMacDonald: For $k=1$ in your set-up, the worst-case expectation will be less than $2n$: because the only singletons allowed correspond to arboresences, whose longest paths must be $< n$ in length. (Incidentally it is a classical fact that the probability a random map $[n]\to [n]$ is eventually constant under self-composition is $1/n$: this is equivalent to Cayley's formula for the number of labeled trees on $[n]$. There is also a beautiful $q$-analog of this: doi.org/10.1080/00029890.2021.1868384) | |
| Dec 2, 2021 at 19:20 | comment | added | Sophie M | A refinement of the question, since the accepted answer links to a complete solution: suppose you draw your functions instead from the uniform distribution on some subset $\{ f_1, \dots, f_k \}$, where there is some sequence of these $f_i$'s that composes to a constant map. For a given $k$, which sets $\{ f_1, \dots, f_k \}$ will maximize the expected number of compositions required for a constant map? How small does $k/n^n$ have to be before this worst-case expectation is substantially larger than $2n$? | |
| Dec 1, 2021 at 20:19 | history | became hot network question | |||
| Dec 1, 2021 at 19:13 | vote | accept | Sam Hopkins | ||
| Dec 1, 2021 at 19:12 | answer | added | esg | timeline score: 5 | |
| Dec 1, 2021 at 19:07 | comment | added | Sam Hopkins | @esg: that's terrific! Please post it as an answer so I can accept it! | |
| Dec 1, 2021 at 18:59 | comment | added | esg | See this paper of Fill: citeseerx.ist.psu.edu/viewdoc/… | |
| Dec 1, 2021 at 17:33 | answer | added | David E Speyer | timeline score: 4 | |
| Dec 1, 2021 at 16:27 | history | edited | Sam Hopkins | CC BY-SA 4.0 |
added 821 characters in body
|
| Dec 1, 2021 at 16:17 | comment | added | Sam Hopkins | @PeterTaylor: it would be very interesting if the leading term were $2n$... | |
| Dec 1, 2021 at 15:31 | answer | added | Peter Taylor | timeline score: 6 | |
| Dec 1, 2021 at 15:02 | comment | added | Peter Taylor | Empirically, based on calculations up to $n=99$, it seems to be roughly $1.99n - 2.48$. | |
| Dec 1, 2021 at 14:13 | comment | added | Sam Hopkins | We could even consider the distribution of the random partition $(a_1,a_2,\ldots)$ where $a_i$ is the cardinality of the image of $g_i$ minus one. | |
| Dec 1, 2021 at 12:19 | history | asked | Sam Hopkins | CC BY-SA 4.0 |