• Login
    View Item 
    •   JScholarship Home
    • Theses and Dissertations, Electronic (ETDs)
    • ETD -- Doctoral Dissertations
    • View Item
    •   JScholarship Home
    • Theses and Dissertations, Electronic (ETDs)
    • ETD -- Doctoral Dissertations
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    QuickSelect Process and QuickVal Residual Convergence

    Thumbnail
    View/Open
    MATTERER-DISSERTATION-2015.pdf (637.9Kb)
    references.bib (18.44Kb)
    thesis.cls (45.95Kb)
    jhu12.clo (18.25Kb)
    set-up.and.prelim.tex (28.01Kb)
    residual.quickval.moments.tex (9.254Kb)
    residual.quickmin.moments.tex (53.97Kb)
    quickval.residual.clt.tex (27.50Kb)
    quickselect.process.convergence.tex (29.33Kb)
    preamble.tex (6.279Kb)
    Matterer_Dissertation.tex (9.541Kb)
    matterer.cv.tex (5.296Kb)
    introduction.tex (17.72Kb)
    exact.L2.residual.quickmin.tex (13.80Kb)
    Date
    2015-09-22
    Author
    Matterer, Jason
    Metadata
    Show full item record
    Abstract
    We define a sequence of tree-indexed processes closely related to the operation of the QuickSelect search algorithm (also known as Find) for all the various values of n (the number of input keys) and m (the rank of the desired order statistic among the keys). As a "master theorem" we establish convergence of these processes in a certain Banach space, from which known distributional convergence results as n tends to infinity about (1) the number of key comparisons required are easily recovered (a) when m/n tends to alpha in [0, 1], and (b) in the worst case over the choice of m. From the master theorem it is also easy, for distributional convergence of (2) the number of symbol comparisons required, both to recover the known result in the case (a) of fixed quantile alpha and to establish our main new result in the case (b) of worst-case Find. Our techniques allow us to unify the treatment of cases (1) and (2) and indeed to consider many other cost functions as well. Further, all our results provide a stronger mode of convergence (namely, convergence in L^p or almost surely) than convergence in distribution. Extensions to MultipleQuickSelect are discussed briefly. Under mild assumptions on a general class of cost functions, Fill and Nakama (2013) proved that the scaled cost of QuickVal converges in L^p and almost surely to a limit random variable S. For a general cost function, we consider what we term the QuickVal residual. The residual is of natural interest (especially in light of the previous analogous work on QuickSort). In the case of QuickMin with key-comparisons cost, we are able to calculate---a la Bindjeme and Fill for QuickSort ---the exact (and asymptotic) L^2-norm of the residual. We take the result as motivation for the scaling factor of root n for the QuickVal residual for general population quantiles and for general cost. We then show in general that the scaled QuickVal residual converges in law to a scale-mixture of centered Gaussians. In the motivating case of QuickMin with key-comparisons cost, we also prove convergence of moments. Following Fuchs for QuickSort, this was part of our original attempt at proving convergence in distribution for the scaled QuickVal residual: using the method of moments. However, this approach encountered two roadblocks: first, because the approach is inherently recursive, we don't know how to extend beyond the motivating case; second, in the case of QuickMin with key-comparisons cost, we can show via Krein's condition that the moments of the limiting distribution do not uniquely define a distribution . In the case of QuickVal with general cost functions, it is still an open question whether the limiting residual distribution is uniquely defined by its moments for any value of alpha.
    URI
    http://jhir.library.jhu.edu/handle/1774.2/39602
    Collections
    • ETD -- Doctoral Dissertations

    Related items

    Showing items related by title, author, creator and subject.

    • Three Favorite Marches. (1) Recruiting March; (2) Duke of Yorks March; (3) Quick March in the Battle of Prague [three missing pages; only Primo part of Duke of York March, and Quick March in the Battle of Prague]. 

      Unknown author (J. Carr, [n.d.])
    • (1) The Rail Road Quick Step; (2) The Carrollton Quick Step. 

      W. Broadbent (composer) (Geo. Willig, Jr., 1828)
    • Military Recreations. A Collection of Marches, Quick Steps, and Waltzes. (1) The United States Infantry Parade March. (2) The York Rifle Corps Quick Step. 

      Ch. Zeuner (arranger); Walch (composer) (John F. Nunns, 184 Chesnut St., 1847)

    DSpace software copyright © 2002-2016  DuraSpace
    Policies | Contact Us | Send Feedback
    Theme by 
    Atmire NV
     

     

    Browse

    All of JScholarshipCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister

    DSpace software copyright © 2002-2016  DuraSpace
    Policies | Contact Us | Send Feedback
    Theme by 
    Atmire NV