Distributional asymptotics in the analysis of algorithms: Periodicities and discretization
| Autor: | Rudolf Grübel |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2007 |
| Předmět: |
von neumann addition
sukhatme-rényi representation renewal processes markov chains loser election counting processes digital search trees geometric distribution [info.info-ds] computer science [cs]/data structures and algorithms [cs.ds] [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] [math.math-co] mathematics [math]/combinatorics [math.co] [info.info-cg] computer science [cs]/computational geometry [cs.cg] Mathematics QA1-939 |
| Zdroj: | Discrete Mathematics & Theoretical Computer Science, Vol DMTCS Proceedings vol. AH,..., Iss Proceedings (2007) |
| Druh dokumentu: | article |
| ISSN: | 1365-8050 |
| DOI: | 10.46298/dmtcs.3528 |
| Popis: | It is well known that many distributions that arise in the analysis of algorithms have an asymptotically fluctuating behaviour in the sense that we do not have 'full' convergence, but only convergence along suitable subsequences as the size of the input to the algorithm tends to infinity. We are interested in constructions that display such behaviour via an ordinarily convergent background process in the sense that the periodicities arise from this process by deterministic transformations, typically involving discretization as a decisive step. This leads to structural representations of the resulting family of limit distributions along subsequences, which in turn may give access to their properties, such as the tail behaviour (unsuccessful search in digital search trees) or the dependence on parameters of the algorithm (success probability in a selection algorithm). |
| Databáze: | Directory of Open Access Journals |
| Externí odkaz: |
|