Un problème ouvert "élémentaire"

Lucas
Lucas
dans Analyse
Bonjour à tous,

Comme échauffement avant de vous attaquer en 2015 à Fermat ou Riemann, je vous propose le problème suivant, qui est proposé comme "open problem" page 22 dans l'article très récent :

Ross Pinsky. A One-Dimensional Probabilistic Packing Problem. In Problems from the Discrete to the Continuous, Springer (2014).

Il s'agit de montrer que $$
k\exp\left( -2\sum_{j=1}^{k-1} 1/j \right) \int_0^1 \exp\left( 2 \sum_{j=1}^{k-1} s^j/j\right) ds \quad
\xrightarrow[k\to +\infty]{}\quad \int_0^{+\infty} \exp\left( -2\int_0^x \frac{1-e^{-y}}{y}dy\right) dx.
$$ Il y a une motivation derrière tout ça bien sûr, le terme de gauche est la densité de voitures obtenue lorsque des voitures de taille $k$ essaient de se garer dans un parking infini "discret" comme dans la figure ci-dessous (ici $k=2$):
Film.gif

Et la constante de droite est la "constant du parking de Rényi", c'est la densité de voitures dans l'analogue continu de ce problème. Je vous renvoie à l'article pour le modèle précis, le parking discret est connu sous le nom de "parking de Page", le parking continu est le "parking de Rényi".

À vos stylos !

[edit : corrigé, merci Barnabé]

Réponses

  • Barnabé5
    Barnabé5
    Es tu bien sûr de la formule? Les deux moins aux deux exponentielles de gauche m'embarrassent.
  • Siméon
    Siméon
    Sauf erreur, on a
    $$
    \int_0^1 \exp\left(2\sum_{j=1}^k \frac{s^j-1}{j}\right)\,ds = \frac{1}{k}\int_0^\infty \exp\left(-2 \int_0^x \frac{1-(1-\frac{y}{k})^k}{y}dy\right) 1_{x \leq k} \,dx
    $$
    d'où on déduit le résultat par convergence dominée puisque $(1-\frac{y}{k})^k \leq e^{-y}$ pour $y \in [0,k]$ et
    $$
    \int_0^\infty \exp\left(-2 \int_0^x \frac{1-e^{-y}}{y}\,dy\right) dx = \int_0^\infty \exp\left(-2 \log (1+x) + O(1)\right)\,dx < \infty.
    $$
    Pour la convergence simple, on peut utiliser le fait que $|(1-\frac{y}{k})^k - e^{-y}| \leq k |1-\frac{y}{k} - e^{-\frac{y}{k}}| \leq \frac{y^2}{2k}e^{x}$ pour $y \in [0,x]$.
  • Siméon
    Siméon
    En attendant une réaction de Lucas, je précise que ma première formule s'obtient par changement de variable après avoir remarqué que
    $$
    \sum_{j=1}^k \frac{s^j-1}{j} = \sum_{j=1}^{k} \int_1^s t^{j-1}\,dt = \int_1^s \frac{1-t^k}{1-t}\,dt = - \int_0^{1-s} \frac{1-(1-u)^k}{u}du.
    $$
  • Lucas
    Lucas
    Salut,

    Je viens de prendre connaissance de ton message, bien joué! (moi j'étais parti un peu de travers et je m'étais finalement emmêlé dans les indices.)

    Tu as donc montré la convergence du parking de Page vers le parking de Rényi (à l'occasion si tu lis l'article et que tu trouves comme moi que le problème est sympa tu peux écrire à Ross Pinsky).
  • Lucas
    Lucas
    Du coup pour les curieux je précise l'origine du problème :

    1) Le parking de Page est un parking de $n$ places. A chaque instant une voiture de taille $k$ tire au sort uniformément un emplacement $(i,i+1,\dots, i+k-1)$ parmi les emplacement restants (voir la simulation plus haut pour $k=2$) et se gare. On continue jusqu'à ce que le parking soit saturé (il n'y a plus $k$ places successives libres). On note $M_n$ le nombre de places occupées, alors
    $$
    \frac{\mathbb{E}[M_n]}{n}\to p_k
    $$
    où $p_k$ est un nombre explicite entre $0$ et $1$ (le terme de gauche dans mon premier message).

    2) Le parking de Rényi est un parking de longueur réelle $x$. A chaque instant une voiture de taille $1$ tire au sort uniformément un intervalle $[y,y+1]$ parmi les intervalles possibles (l'ensemble de tous les $y$ possibles est un sous-ensemble mesurable de $[0,x-1]$, il a une mesure de Lebesgue).

    On continue jusqu'à ce que le parking soit saturé, on note $M_x$ le nombre de places occupées, alors quand $x\to\infty$
    $$
    \frac{\mathbb{E}[M_x]}{x} \to p_\infty,
    $$
    où $p_\infty$ est le terme de droite dans mon premier message.
    Bonus : Dans l'article que j'ai cité, il est demandé en plus si $p_k$ est décroissant en $k$ (ce qui paraît clair vu le modèle).
  • dedekind93
    dedekind93
    Bonjour à tous. Je remonte ce fil pour savoir s'il existe un moyen élémentaire (sans espérance conditionnelle notamment) pour expliciter le $p_k$ (ne serait-ce que $p_2$) qu'évoque Lucas ? Peut-être est-ce contenu dans l'article de Ross Pinsky (A One-Dimensional Probabilistic Packing Problem. In Problems from the Discrete to the Continuous, Springer (2014)), mais je n'y ai pas accès (quelqu'un pourrait-il gracieusement me le prêter ?).
    Pour l'instant, j'ai essayé de conditionner par rapport à la position occupée par le premier véhicule, mais la probabilité conditionnelle qui apparaît me pose souci pour former une relation de récurrence exploitable.
    Merci pour votre aide !
  • Chaurien
    Chaurien
    Voici le chapitre en question.
  • dedekind93
    dedekind93
    Merci Chaurien. Je vais m'y atteler...ce n'est pas encore gagné pour le mettre sous forme "élémentaire" !
  • Lucas
    Lucas
    @dedekind93 : Effectivement tu peux regarder le chapitre envoyé par Chaurien (merci à lui au passage), la méthode est volontairement générale car il s'en sert également pour évaluer la variance. Et c'est bien la stratégie que tu as en tête de conditionner par rapport à la première voiture, ensuite on passe aux séries génératrices.

    Deux autres alternatives :
    * L'article historique de P.J.Flory (un chimiste, prix Nobel en 1974) qui a introduit le modèle, il avait déjà calculé $p_2$ en 1939! Je joins l'article. C'est assez malin et ça se fait en quelques lignes.
    * Une preuve probabiliste que tu peux trouver ici : Lien (Parking discret).
  • dedekind93
    dedekind93
    Merci Lucas pour ces documents, je vais regarder ça de plus près !
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion