Press "Enter" to skip to content

Month: October 2014

Recueil de modèles stochastiques

Recueil de modèles stochastiquesJ’ai l’immense joie ce soir de terminer la mise au point de la version préliminaire du livre intitulé « Recueil de modèles stochastiques », écrit en collaboration avec mon vieil ami Florent Malrieu (sauriez-vous nous identifier sur la photo de Saint-Flour 1999 ?). Extrait de l’avant-propos:

Ce recueil de modèles stochastiques puise sa source dans les cours de Master de ma- thématiques et de préparation à l’agrégation de mathématiques, que nous avons dispensés, pendant plusieurs années, aux étudiants des universités de Toulouse, Rennes, Marne-la-Vallée, Paris-Dauphine, et Tours. Le parti pris est de polariser la rédaction par les modèles plutôt que par les outils, et de consacrer chaque séance ou chapitre à un modèle. Bien que parfois reliés, les chapitres sont essentiellement autonomes. Ils ne contiennent pas de rappels de cours sur les outils fondamentaux comme les théorèmes limites, les martingales, et les chaînes de Markov, pour lesquels d’excellentes références sont disponibles. Chaque chapitre commence par une liste de mots-clés et se termine par quelques notes et commentaires. La liste des thèmes abordés n’a rien de canonique ni d’exhaustif, mais constitue un panorama varié, que nous espérons enrichissant.

Le livre compte environ 280 pages, et comporte 26 chapitres, une bibliographie, et un index :

  1. Pile, face, coupons
  2. Marches aléatoires
  3. Modèle d’Ehrenfest
  4. Modèle de Fisher-Wright
  5. Branchement
  6. Percolation
  7. Renforcement
  8. Simulation de lois discrètes
  9. Restaurants chinois
  10. Généalogies et coalescence
  11. Agrégation limitée par diffusion interne
  12. Chaînes de Markov cachées
  13. Algorithme EM et mélanges
  14. Records, extrêmes, et recrutements !
  15. Polymères dirigés en environnement aléatoire
  16. Matrices aléatoires
  17. Problème du voyageur de commerce
  18. File d’attente M/M/Infini
  19. Ruine d’une compagnie d’assurance
  20. Naissances et assassinats
  21. Croissance et fragmentation
  22. Modèle du télégraphe
  23. Problème de Dirichlet
  24. Processus d’Ornstein-Uhlenbeck
  25. Modèles de diffusion
  26. Des chaînes de Markov aux processus de diffusion

C’est l’occasion de rappeler que le nombre $26$, utilisé en France pour la section Mathématiques appliquées et applications des mathématiques du Conseil national des universités, est l’unique nombre coincé entre un carré ($25=5^2$) et un cube ($27=3^3$), cf. [GB].

Pour ceux qui cherchent les graphes aléatoires, il y en a dans les chapitres 5, 6, 7, 8.

Leave a Comment

Linux kernel 3.17 getrandom()

Linux Tux from Wikimedia
Linux Tux

Linus Torvalds has just released the Linux kernel version 3.17. Among other things, it comes with a new system call for random numbers named getrandom() introduced by Theodore Ts’o for the needs of applications such as LibreSSL. This new system call can be used to emulate the getentropy() of OpenBSD. Such random numbers are not algorithmic, and their unpredictability is useful for cryptographic and security applications. More information is available on Linux Weekly News.

Excerpt from the commit in the Git repository of the Linux kernel source:

The getrandom(2) system call was requested by the LibreSSL Portable
developers. It is analoguous to the getentropy(2) system call in
OpenBSD.

The rationale of this system call is to provide resiliance against
file descriptor exhaustion attacks, where the attacker consumes all
available file descriptors, forcing the use of the fallback code where
/dev/[u]random is not available. Since the fallback code is often not
well-tested, it is better to eliminate this potential failure mode
entirely.

The other feature provided by this new system call is the ability to
request randomness from the /dev/urandom entropy pool, but to block
until at least 128 bits of entropy has been accumulated in the
/dev/urandom entropy pool. Historically, the emphasis in the
/dev/urandom development has been to ensure that urandom pool is
initialized as quickly as possible after system boot, and preferably
before the init scripts start execution.

This is because changing /dev/urandom reads to block represents an
interface change that could potentially break userspace which is not
acceptable. In practice, on most x86 desktop and server systems, in
general the entropy pool can be initialized before it is needed (and
in modern kernels, we will printk a warning message if not). However,
on an embedded system, this may not be the case. And so with this new
interface, we can provide the functionality of blocking until the
urandom pool has been initialized. Any userspace program which uses
this new functionality must take care to assure that if it is used
during the boot process, that it will not cause the init scripts or
other portions of the system startup to hang indefinitely.

Notes. LibreSSL is a free version of the Secure Sockets Layer (SSL) and Transport Layer Security (TLS) protocols, forked from OpenSSL cryptographic software library in April 2014 by OpenBSD developers after the Heartbleed security vulnerability in OpenSSL.

Leave a Comment