13 ms·
The asymptotic means for tails and cycles of random functions are in Theorem 3 of https://link.springer.com/content/pdf/10.1007/3-540-46885-4_34.pdf https://l
by vmilner 8y ago
The asymptotic means for tails and cycles of random functions are in Theorem 3 of
https://link.springer.com/content/pdf/10.1007/3-540-46885-4_34.pdf https://link.springer.com/content/pdf/10.1007/3-540-46885-4_...
- ColinWright 8y agoGreat catch - thank you! Now to find some time to read it properly.
- vmilner 8y agoAntoine Joux's book: https://books.google.co.uk/books?id=buQajqt-_iUC https://books.google.co.uk/books?id=buQajqt-_iUC precis-es this paper in its sections 7.2 and 7.3 and highlights the fact that looking at "Pollard rho style" random functions with in-degree 0 or 2, merely changes the multiplicative constants of the tail and cycle statistics without changing the order.
- ColinWright 8y agoThat's pretty much what I was expecting, and it's great to see that someone's done the work. I never expected my idle musings to be in any way new or insightful, so it's nice to be able to see that at least I'm not completely off-track. I'm now wondering about constructing fast-to-compute functions with in-degree (0,0,3) or (0,0,0,4), which should change the characteristics, but I need to read a bit first. Again, thanks.