G. LOUCHARD

Teaching activities: I am now retired so I can devote (almost) all my time to research

Research activities: during the last decade, we have used probabilistic techniques such as Brownian motion, random walks, diffusion processes in the analysis of algorithms. We have investigated distribution of costs which constitute an improvement over the classical average case or worst case analysis. Many applications have already been covered. Our next research concerns hashing algorithms, analytic combinatorics and other computer science random structures.

Recent cooperations:

Publications and technical reports :

  1. Etude stochastique de la r�partition des neutrons dans un mod�rateur - I; Bull. Acad. R. Belg. Cl. Sc. 4, 233-249, 1960.
  2. Etude stochastique de la r�partition des neutrons dans un mod�rateur - II; Bull. Acad. R. Belg. Cl. Sc. 5, 363-384, 1960.
  3. Tests d'ajustement et m�thodes de Monte-Carlo - I; Bull. Acad. R. Belg. Cl. Sc. 8, 769-784, 1963.
  4. Tests d'ajustement et m�thodes de Monte-Carlo - II; Bull. Acad. R. Belg. Cl. Sc. 3, 245-274, 1964.
  5. Analyse statistique des signaux �mis par les radio-sources de faible intensit�; M�moire publi� par l'Acad. R. Bel. Cl. Sc., 1965.
  6. Hitting probabilities for Brownian motion in three dimensions; J. of Math. and Phys. 44, 2, 177-181, 1965.
  7. Th�orie du potentiel et mouvement Brownien sur la sph�re; Cahiers du Centre d'Etudes de Recherche Op�rationnelle 7, 3/4, 248-257, 1965.
  8. Recurrence times and capacities for finite ergodic chains, Duke Math. J. 33, 1, 13-22, 1966.
  9. Mouvement Brownien et valeurs propres du Laplacien; Ann. Inst. Henri Poincar�, IV, 4, 331-342, 1968.
  10. Moments de temps al�atoires dans des cha�nes de Markov d�nombrables et transientes; Rev. Roum. Math Pures et Appl. XIII, 1367-1383, 1968.
  11. Ensembles infinis d'�quilibre dans des cha�nes de Markov d�nombrables et transientes; Comptes rendus du IVe Congr�s des Math�maticiens d'Expression Latine, 1970.
  12. Realization of Petri Nets without conditional statements; Inf. Proc. Letters 2, 4, 105-107, 1973 (with R. Devillers)
  13. Approximation of eigencharacteristics in nearly-completely decomposable stochastic systems; Stocha\-stic Processes and their Applications 4, 1976 (coauteur P.J. Courtois)
  14. Improvement of parallelism in a finite buffer sharing policy; The computer Journal 19, 3, 1976 (coauteur R. Devillers)
  15. Editing co-occurrences in pyramidal pattern using list structures; Cirpho 2/2, 1974 (coauteur Cl. Machgeels)
  16. Using auxiliary variables in parallel programs verification; Proceedings ICS 77 (coauteur R.Devillers)
  17. Return times in nearly completely decomposable stochastic processes, J.A.P. 15, 1978 (coauteur G. Latouche)
  18. Hashing techniques. A global approach; B.I.T 19, 3, 302-311, 1979 (coauteur R. Devillers)
  19. Random times in nearly-completely decomposable, transient Markov chains; Cahiers du Centre d'Etudes de Recherche Op�rationelle 24, 2-4, 1982 (coauteur G. Latouche)
  20. Nearly-completely decomposable stochastic processes; Proceedings of the International Congress on Applied Systems Research and Cybernetics; Acapulco, D�c. 12-15, 1980.
  21. The Brownian Motion : a neglected tool for the complexity analysis of sorted tables manipulation; RAIRO-Informatique Th�orique 17, 4, 365-385, 1983.
  22. Kac's formula, Levy's local time and Brownian excursion; J.A.P, 21, 479-499, 1984.
  23. The Brownian excursion area : a numerical analysis; International Journal of Computers and Mathematics with Applications 10, 6, 413-417, 1984. Corr. 12A, 3, 375, 1986.
  24. Brownian motion and algorithms complexity; B.I.T. 26, 1, 17-34, 1986.
  25. Random walks, Gaussian processes and list structures; Proc. CAAP'86, Nice. Full version: Theor. Comp. Sc. 53, 99-124, 1987.
  26. Exact and asymptotic distributions in digital and binary search trees; RAIRO-Theor. Inf. Appl. 21, 4, 479-496, 1987.
  27. Large finite population queueing systems - Part I : the infinite server model; Stoch. Models and Comm. Statistics, 4, 3, 473-506, 1988.
  28. Geometric bounds on iterative approximations for nearly completely decomposable Markov chains; J. Appl. Prob. 27, 521-529, 1990 (coauteur G. Latouche)
  29. Dynamic algorithms in D.E. Knuth's model : a probabilistic analysis, with B. Randrianarimanana and R. Schott; Proc. ICALP'89, Stresa, L.N.C.S 372, 521-533. Full version: TCS 93, 201-225, 1992.
  30. Probabilistic analysis of some distributed algorithms, with R. Schott; Proc. CAAP'90, Copenhagen, L.N.C.S. 431, 239-253. Full version: Random Structures and Algorithms 2, 2, 151-186, 1991.
  31. Robust variations of interpolation search : an asymptotic analysis; Computing 46, 193-222, 1991.
  32. Random walks, heat equation and distributed algorithms, with R. Schott, M. Tolley and F. Zimmerman, J. Comp. Appl. Math. 53, 243-274, 1994.
  33. L'analyse d'algorithmes. Nouvelles de la Science et des Technologies. 9, 4,27-35, 1993.
  34. Trie size in a dynamic list structure. Proc. CAAP'93 Orsay, L.N.C.S 688, 717-731.\\ Full version: Rand. Struct. Alg. 5, 665-695, 1994.
  35. A probabilistic analysis of a string edit problem, with W. Szpankowski. Proc. 4th Int. Symp. Combin. Patt. Match '93, Padova, LNCS 684, 152-163; Full version: Comb. Prob. Comp. 4, 143-166, 1995. LS36.ps
  36. Large finite population queueing systems: the finite server model. Stoch. Proc. Appl. 55, 117-145, 1994.
  37. Probabilistic analysis of some (un)directed animals. Proceedings Gascom'94; Full version: T.C.S. 159, 1, 65-79, 1996.
  38. Generalized Lempel-Ziv parsing scheme and its preliminary analysis of the average profile, with W. Szpankowski. Proc. DCC'95, 262-271, 1995.
  39. Average profile and limiting distribution of a phrase size in the Lempel-Ziv parsing algorithm, with W. Szpankowski. IEEE Trans. Inf. Theor. 41, 2, 478-488, 1995. LS40.ps
  40. Dynamic analysis of some relational databases parameters, with D. Gardy. Proc. STACS'95, Munich, LNCS 900, 433-444, 1995; Full version: TCS 144, 125-160, 1995 (Special volume on Mathematical analysis of algorithms).
  41. Finding the maximum with linear error probabilities: a sequential approach. Proc. STACS'95, Munich, LNCS 900, 14-25, 1995.
  42. Some distributed algorithms revisited. Stoch. Models 11 (4), 563-586, 1995.
  43. Digital search trees revisited. Cahiers du CERO 36, 259-278, 1995.
  44. On the average redundancy rate of the Lempel-Ziv code, with W. Szpankowski. Proc. DCC'96. Full version: IEEE Trans. Inf. Theor. 43, 1, 2-8, 1997. LS45.ps
  45. Probabilistic analysis of adaptative sampling. RSA 10, 157-168, 1997. (Special issue on Average-case Analysis of Algorithms)
  46. Probabilistic analysis of column convex and directed diagonally convex animals. RSA 11, 151-178, 1997.
  47. Average profile of the generalized digital search trees and the generalized Lempel-Ziv Algorithm, with W. Szpankowski and J. Tang. Siam J. Comp. 28, 3, 935-954, 1999. LS48.ps
  48. Data structures maxima, with C. Kenyon and R. Schott. Proc. 8th Inter. Conf. Fund. Comp. Theor. '91, Berlin, LNCS 529, 339-349. Full version: Siam J. Comp. 26, 4, 1006-1042, 1997.
  49. The Brownian Excursion multi-dimensional local time density, with B.Gittenberger. JAP 36, 2, 350-373, 1999. BEL9.ps
  50. Asymptotic properties of some underdiagonal walk generation algorithms. GASCOM'97, Caen. Full version: T.C.S., 218, 935-954, 1999. uwg4.ps
  51. The complete solution of the competitive rank selection problem, with T.Bruss and M.Drmota. 4th Int.Symp. on Average-case analysis of Algorithms, Princeton , 1998. Full version: Algorithmica, 22, 4, 413-447, 1998 (Special issue on Average-case Analysis of Algorithms). BDL12.ps
  52. Sharp bounds for winning probabilities in the competitive rank selection problem, with T.Bruss. JAP, 35 ,1007-1011, 1998
  53. Probabilistic analysis of column-convex and directed diagonally-convex animals II. ALEA'98, Asnelles, FEB.1998. Full version: RSA, 15, 1-23, 1999. ANI2.ps
  54. On the local time density of the reflecting Brownian Bridge, with B.Gittenberger. J.Appl.Math.Stoch.An., 13, 2, 125-136, 2000. BB6.ps
  55. Generalized covariances of multi-dimensional Brownian excursion local times, with J.Turner LATIN 2000, Punta del Este, Montevideo, LNCS, 176, 463-472, 2000. Full version: TCS, 21, 317-336, 2003 . Cov.ps
  56. L'analyse d'algorithmes. TSI, 19, 1,2,3, 359-372, 2000.
  57. Probabilistic analysis of Carlitz compositions, with H.Prodinger . 2000, DMTCS, 5, 1, 71-96, 2002. carl51.ps
  58. Analytic variations on the Airy distribution , with P.Flajolet . 2000, Algorithmica , 31 ,3, 361-377, 2001 airy9.ps
  59. Probabilistic analysis of a Schroder walk generation algorithm , with O.Roques . Proc.Mathinfo 2000:Mathematics and Computer science,Birkhauser. schr2.ps
  60. Phase transition for parking blocks, Brownian excursion and coalescence, with P.Chassaing . 2000, RSA, 21 ,1, 76-119, 2002 . parkp.ps
  61. Runs of geometrically distributed random variables: a probabilistic analysis . 2000, JCAM, 142, 1, 137-143, 2002 . run.ps
  62. Distinctness of compositions of an integer: a probabilistic analysis , with P.Hitczenko . 2000, RSA, 19, 3-4, 407-437, 2001. hlanall2.ps
  63. Reflected Brownian bridge area conditioned on its local time at the origin , with P.Chassaing . 2001, J.Algor., 44 ,29-51,2002 BBcond1.ps
  64. Ascending runs of geometrically distributed random variables , with H.Prodinger,2001. TCS, 304, 59-86, 2003. runas5.ps
  65. Random 0-1 rectangular matrices: a probabilistic analysis, with H.Prodinger.2001. Periodica Mathematica Hungarica. 47,1-2, 169-193, 2003. carm21ps
  66. Random sampling from Boltzmann principles. with P.Duchon, Ph.Flajolet, G.Shaeffer. ICALP '2002. Full version: Comb. Prob. Comp. 13, 577-626, 2004. dfls.ps
  67. Optimal stopping on patterns in strings generated by independent random variables, with T.Bruss. 2002. JAP, 40, 49-72, 2003. bruss1.ps
  68. Reflected Brownian Bridge Local Time conditioned on its Local Time at the Origin, with B.Gittenberger. 2002. Stat. Prob. Letters. Stat. Prob. letters. 68, 1, 51-60. glnote14.ps
  69. On the N-Tower-Problem and Related Problems, with T.Bruss and J.Turner. Adv.Appl.Prob., 35, 1, 278-294, 2003 brlt.ps
  70. Additive Decompositions, Random Allocations, and Threshold Phenomena, with O.Dubois and J.Mandler. Comb. Prob. Comp. 13, 537-576, 2004. dec8.ps
  71. The number of inversions in permutations: A saddle point approach, with H.Prodinger. J. Integer Sequences, 6, 03.2.8, 2003 inv14.ps
  72. The number of distinct part sizes of some multiplicity in compositions of an Integer. A probabilistic Analysis. DRW'03, Paris, full version: DMTCS, AC, 155-170, 2003 multi.ps
  73. The Guessing Secrets problem: a probabilistic analysis, with A.Del Lungo, C.Marini and F.Montagna. 2003. J. Algorithms., 142-176, 2005. quest.ps
  74. Monotone runs of uniformly distributed integer random variables: a probabilistic analysis .TCS, 346, 2-3, 358-387, 2005. lungo.ps
  75. Analysis of a Recurrence Related to Critical Nonhomogeneous Branching Processes, with M.Drmota and N.M.Yanev. 2003. Stoch. An. Appl. 24, 1, 37-59, 2006. analrecu6.ps
  76. Common intervals in Permutations, with S.Corteel and R.Pemantle. 2004. Proc. Third Colloquium on Mathematics and Computer Science. DMTCS, 1, 189-214, 2006. cort83.ps .Full version: comnew.ps
  77. A distributed algorithm to find Hamiltonian cycles in G(n,p) random graphs (short version), with E.Levy and J.Petit. Proc. Workshop on Combinatorial and Algorithmic aspects of networking. LNCS. 2004. ham.ps
  78. Asymptotics of the Moments of Extreme-value related distribution functions, with H.Prodinger. 2004. Algorithmica, 46, 3, 431-462, 2006. . Long version: moml.ps
  79. Asymptotic Analysis of a Leader Election Algorithm, with C.Lavault. 2004. TCS, 359, 1-3, 239-254, 2006. elecs.ps
  80. The number of distinct values of some multiplicity in sequences of geometrically distributed random variables, with H.Prodinger and M.D.Ward. Proc. AoFA'2005, DMTCS. AD, 231-256, 2005. lpw.pdf
  81. On gaps and unoccupied urns in sequences of geometrically distributed random variables (long version), with H.Prodinger . Discrete Mathematics. 308, 9, 1538-1562, 2008. gaps18.ps
  82. The number of elements close to near-records in geometric samples, with H.Prodinger . Quaestiones Mathematicae, 29, 4, 447-470, 2006. balalp6.ps
  83. A variant of the Guessing Secrets Game, with C.Marini, F.Montagna and G.Simi . Pure Mathematics and Applications, 16, 3, 295-305, 2005. guy3.ps
  84. Generalized Approximate Counting Revisited, with H.Prodinger . 2006. Theoretical Computer Science. 391, 109-125, 2008. gac2.ps
  85. The Asymmetric Leader Election Algorithm, with H.Prodinger . 2006. Annals of Combinatorics. 12, 449-478, 2009 elecas7.ps
  86. Advancing in the Presence of a Demon, with H.Prodinger . Mathematica Slovaca. 58, 3, 263-276, 2008. demon5.ps
  87. Analysis of a new skip list variant, with H.Prodinger . DMTCS, proc AG, 365-374, 2006, Fourth Coll. Math. Comp. Sc. Trees, Comb. and Prob. dmag.pdf
  88. A combinatorial and probabilistic study of initial and end heights in samples of geometrically distributed random variables and in permutations , with H.Prodinger . DMTCS, 9, 1,137-170, 2005. descents4.ps
  89. Random Optimization: a Probabilistic Analysis , with J. Cardinal and S. Langerman . 2007. Proc. AoFA'2007, DMTCS, AH, 57-78. optth3.ps
  90. Injecting unique minima into random sets and applications to "Inverse Auctions", with F.T. Bruss and M. D. Ward. TALG, 6, 1,21, 1-19, 2009 aucn8.ps
  91. Joint distributions for Movements of elements in Sattolo's algorithm, with H. Prodinger and S. Wagner. 2007. Questiones mathematicae, 31, 307-344, 2008 moves4.ps
  92. Tail estimates for the Brownian excursion area and other Brownian areas, with S. Janson. Elec. Journ. Prob. 12, 58, 1600-1632, 2007. tails2.pdf
  93. FIFO Queuing of Constant Length Fully Synchtonous Jobs, with V. Berten and R. Devillers. 2007. Proc. GSEM'2007 fullsync.pdf
  94. The Catalan distribution: A saddle point approach, with H. Prodinger. 2008. Annals of Combinatorics, 15, 2, 313-329, 2011 catal5.ps
  95. Representations of numbers as :A saddle point approach , with H. Prodinger. LNCS. 5489, 87-96, 2010 rep1.ps
  96. Convergence of some leader election algorithms , with S. Janson and C. Lavault. DMTCS, 10, 3, 171-196, 2008 fr6.ps
  97. The Register Function for Lattice Paths, with H. Prodinger. Fifth Coll. Math. Comp. Sc. Trees, Comb. and Prob. DMTCS, proc. AG, 139-152, 2008 register.pdf
  98. The Odds-algorithm based on sequential updating and its performance, with F.T. Bruss. 2008. AAP, 41, 131-153, 2009 genodds.ps
  99. Matrix Compositions: a Probabilistic analysis. Proc. GASCOM'08. Pure Mathematics and Applications, 19, 2-3, 127-146, 2008. Long version: compmat.ps
  100. Asymptotic results for silent elimination, with H. Prodinger. DMTCS, 18, 2, 185-196, 2010 fla6.pdf
  101. Number of Survivors in the Presence of a Demon with H. Prodinger and M. D. Ward. Publ. Math. Hung. 64,1, 101-117, 2012 lpw10.pdf
  102. The maximum of Brownian motion with parabolic drift, with S. Janson and A. Martin-L\"of. Electronic Journal of Probability. 15, 1893-1929, 2010 sj243.pdf
  103. Asymptotics of the Stirling numbers of the first kind revisited: A saddle point approach. DMTCS, 12, 2, 167-184, 2010 stirp.pdf
  104. Recent studies on the Dice Race Problem and its connections. Mathematica Applicanda, 44, 1, 63-86, 2016 Louchard-revised2.pdf
  105. The Swedish leader election protocol: Analysis and variations, with C. Martinez and H. Prodinger. Proc. ANALCO 2011, 127-134, 2011 leadel.pdf
  106. The largest missing value in a composition of an integer and some Allouche-Shallit-like identities, with H. Prodinger. J.Integer sequences, 16, 2, Article 13.2.2, 2013 ALSH7.pdf
  107. The Asymmetric Leader Election Algorithm with swedish stopping: A probabilistic analysis, with H. Prodinger. DMTCS, 14, 2, 91-128, 2012 elecas11.pdf
  108. Asymptotics of the Stirling numbers of the second kind revisited: A saddle point approach. Applicable Analysis and Discrete Mathematics, 7, 2, 193-210, 2013 Stirling2.pdf
  109. Approximate counting with m counters: a probabilistic analysis, with H. Prodinger. Journal of Algebra, Discrete Structures and Applications, 2, 3, 191-209, 2015 mcount6.pdf
  110. Sum of positions of records in random permutations: An asymptotic analysis in central and non-central regions. Online journal of Analytic Combinatorics, 9, 2014 srecn3.pdf
  111. The Asymmetric leader election algorithm: number of survivors near the end of the game. Quaestiones Mathematicae, 1-19, 2015 surviv.pdf
  112. Resolution of T.~Ward's Question and the Israel--Finch Conjecture. Precise Analysis of an Integer Sequence Arising in Dynamics, with J. Gaither, S. Wagner, M. D. Ward. Cambridge University press, Combinatorics, Probability and Computing, 24-1, 2015, http://journals.cambridge.org/abstract_S0963548314000455 GaitherLouchardWagnerWard.pdf
  113. Asymptotics of the Eulerian numbers revisited: a large deviation analysis. Online Journal of Analytic Combinatorics, 10, 1-11, 2015 eulerian.pdf
  114. The Truncated Geometric Election Algorithm : Duration of the Election, with M. D. Ward. Statistics and Probability letters, 101, 40-48, 2015. Long version: leadgeom.pdf
  115. Multivariate asymptotic analysis of set partitions: focus on blocks of fixed size. Journal of Algebra Combinatorics Discrete Structures and Applications, 4, 1, 75-91, 2017 partiREV2.pdf
  116. Philippe Flajolet and the Airy Function, with C. Banderier. banderier-louchard.pdf
  117. Sequential selection of the $\K$ best out of $n$ rankable objects, with T. Bruss. DMTCS, 18, 3, 1-12, 2016 kbest9.pdf
  118. Asymptotic Analysis of the Sums of Powers of Multinomial Coefficents: A Saddle Point Approach, with M. D. Ward. Integers, 17, paper A47, 2017 an2.pdf
  119. Number of Singletons in Involutions of large size: a central range and a large deviation analysis. Online Journal of Analytic Combinatorics, 12, 1-16, 2017 sing.pdf
  120. The Adaptive sampling revisited, with Y. Swan asnew5.pdf, new version: The Adaptive sampling revisited, with Matthew Drescher and Y. Swan DMTCS, 21, 3,# 13, 1-12, 2019 asnew12.pdf
  121. A refined and asymptotic analysis of optimal stopping problems of Bruss and Weber. Mathematica Applicanda, 45, 2, 95-118, 2017 weber.pdf
  122. The perimeter of uniform and geometric words: a probabilistic analysis. Quaestiones Mathematicae (online) 2018 perim.pdf
  123. Two applications of polylog functions and Euler sums. ArXiv:1709.08686, 2017 polyeuler.pdf
  124. An Asymptotic Series for an Integral, with Michael E. Hoffman, Markus Kuba, Moti Levy. ArXiv: 1802.09214, 2017, The Ramanujan Journal, 53(1), 1-25, 2020 jlv6.pdf
  125. Some large polyominoes' perimeter: a stochastic analysis. ArXiv: http://arxiv.org/abs/1808.00912 V.3, 2019, Online Journal of Analytic Combinatorics, 15, 2020 perinewP3.pdf
  126. Conjectures about Traffic Light Queues, with S.Finch. ArXiv: http://arxiv.org/abs/1810.03906v2, 2018 conj.pdf
  127. Traffic Light Queues and the Poisson Clumping Heuristic, with S.Finch. ArXiv: http://arxiv.org/abs/1810.12058v3, 2019 heu1.pdf
  128. Traffic lights, clumping and QBDs, with S.Finch, G.Latouche and B.Meini. ArXiv: http://arxiv.org/abs/1911.01134, 2019, Stochastic Models Online, 1-25
  129. The number of distinct adjacent pairs in geometrically distributed words: a probabilistic and combinatorial analysis, with Werner Schachinger and Mark Daniel Ward ArXiv: https://arxiv.org/abs/2203.14773, DMTCS vol 25:2#3,2023,1-46 louchard-schachinger-ward-V4.pdf