Calendar

Mar
3
Tue
Student Seminar: Jason Matterer @ Whitehead 304
Mar 3 @ 3:00 pm – 4:00 pm
Convergence in Law of QuickVal Residual to a Scale Mixture of Gaussians

QuickVal is a theoretical construct that has been used as an intermediate step to analyzing the comparison cost of the rank-finding algorithm Quickselect. For a wide variety of comparison cost-functions, it is well-known that provided some technical assumptions, QuickVal converges in a strong sense (almost surely and L^p) to a limit random variable S. We consider what we call the QuickVal residual, which is the difference between the cost of QuickVal and S, and show that after a suitable scaling and under some technical assumptions, the QuickVal residual converges in law to a scale mixture of Gaussians.

 

Back to top