2010/09/16 by Nicolas Curien, Curien, Nicolas, Adrien Joseph +1
Computer Science · Mathematics · #Bayesian Methods and Mixture Models #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Stochastic processes and statistical mechanics #math.PR
paper · pdf · doi:10.48550/arxiv.1009.3113
arxiv created 2010/09/16 · openalex publication_date 2010/09/16 · arxiv updated 2010/09/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We analyze the mean cost of the partial match queries in random two-dimensional quadtrees. The method is based on fragmentation theory. The convergence is guaranteed by a coupling argument of Markov chains, whereas the value of the limit is computed as the fixed point of an integral equation.