Around a few statistics on binary search trees and on accessible deterministic automata

Abstract : This Phd thesis is divided into two independent parts. In the first part, we provide an asymptotic analysis of some statistics on the binary search tree. In the second part, we study the coupon collector problem with a constraint. In the first part, following the model introduced by Aguech, Lasmar and Mahmoud [Probab. Engrg. Inform. Sci. 21 (2007) 133—141], the weighted depth of a node in a labelled rooted tree is the sum of all labels on the path connecting the node to the root. We analyze the following statistics : the weighted depths of nodes with given labels, the last inserted node, nodes ordered as visited by the depth first search procees, the weighted path length, the weighted Wiener index and the weighted depths of nodes with at most one child in a random binary search tree. In the second part, we study the asymptotic shape of the completion curve of the collection conditioned to T_n≤ (1+Λ), Λ>0, where T_n≃n ln⁡n is the time needed to complete accessible automata, we provide a new derivation of a formula due to Korsunov [Kor78, Kor86]
Document type :
Theses
File URL :
http://docnum.univ-lorraine.fr/ulprive/DDOC_T_2018_0301_AMRI.pdf
Complete list of metadatas

https://hal.univ-lorraine.fr/tel-02096118
Contributor : Thèses Ul <>
Submitted on : Thursday, April 11, 2019 - 10:04:03 AM
Last modification on : Friday, April 12, 2019 - 1:24:07 AM

Identifiers

  • HAL Id : tel-02096118, version 1

Collections

Citation

Anis Amri. Around a few statistics on binary search trees and on accessible deterministic automata. Mathematics [math]. Université de Lorraine, 2018. English. ⟨NNT : 2018LORR0301⟩. ⟨tel-02096118⟩

Share

Metrics

Record views

11