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. The Dice Race : results and open problems, with F.T. Bruss. rounds.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. 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. Stirling2.pdf
  109. Approximate counting with m counters: a probabilistic analysis, with H. Prodinger. mcount2.pdf
  110. Sum of positions of records in random permutations: A precise analysis. srec.pdf