标题： 一种在m-迪克路径上的新双射及其在随机采样中的应用 显示英文标题

标题： A new bijection on m-Dyck paths with application to random sampling

摘要： 我们提出了一种新的双射，用于不同变体的$m$-Dyck 路径（步长为$\{+1,-m\}$的路径，从高度$0$开始并结束于该高度，并保持在非负高度），这推广了 Dyck 前缀与带标记的{\L }ukasiewicz 路径之间的经典双射。 作为应用，我们提出了一种新的随机采样过程，用于$m$-Dyck 路径，具有线性时间复杂度，并使用准最优数量的随机位。 这优于 Devroye 的算法，该算法使用$\mathcal O(n\log n)$个随机位。 显示英文摘要

摘要： We present a new bijection between variants of $m$-Dyck paths (paths with steps in $\{+1,-m\}$ starting and ending at height $0$ and remaining at non-negative height), which generalizes a classical bijection between Dyck prefixes and pointed {\L}ukasiewicz paths. As an application, we present a new random sampling procedure for $m$-Dyck paths with a linear time complexity and using a quasi-optimal number of random bits. This outperforms Devroye's algorithm, which uses $\mathcal O(n\log n)$ random bits.