View Item 
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        JavaScript is disabled for your browser. Some features of this site may not work without it.

        Browse

        All of UU Student Theses RepositoryBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

        Efficient Generation of Discrete Random Variates

        Thumbnail
        View/Open
        thesis.pdf (726.1Kb)
        Publication date
        2019
        Author
        Klundert, B. van de
        Metadata
        Show full item record
        Summary
        In this paper we look at some of the fastest algorithms to generate discrete random variates. All of these algorithms support updating the rate of an event after the data structure has been build. As part of this study we propose extensions for the Table method and for the Alias method which allow these algorithms to perform updates on events. We show that using these extensions the Table method can be updates in $O(\Delta r)$ time. We also show that the Alias method can do updates bounded by $C \cdot r_{ave}$ in $O(1)$ amortized time, where $r_{ave}$ is the average rate of events in the data structure. To back up these theoretical results an experimental evaluation of the algorithms was executed. In this evaluation we scale the number of events, average rate of events and variance of the rate of events to see how each of the algorithms react to these changes.
        URI
        https://studenttheses.uu.nl/handle/20.500.12932/34915
        Collections
        • Theses
        Utrecht university logo