Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
145 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

QDV 19: le printemps est revenu!

Envoyé par Norbert Verdier 
Re: QDV 19: le printemps est revenu!
il y a six années
avatar
Je ne sais pas où bs a trouvé l'énoncé, mais l'ami google semble montrer que

Il y a eu une discussion sur mathoverflow:

[mathoverflow.net]

qui a inspiré M. Erickson qui l'a mis dans son bouquin

[books.google.fr]

La solution du bouquin n'est pas plus rigoureuse que les arguments heuristiques développés ici (c'est essentiellement la même).
Un intervenant sur mathoverflow donne une référence vers une méthode possible de preuve.

Personnellement, je serais très intéressé de lire une preuve rigoureuse.
Re: QDV 19: le printemps est revenu!
il y a six années
La méthode de l'EDO "moyenne" est un outil usuel dans l'analyse des algorithmes d'approximation stochastique (cf ici). Je ne crois pas que les outils développés là-bas s'appliquent tels quels ici, mais il faut voir.
JLT
Re: QDV 19: le printemps est revenu!
il y a six années
avatar
En attendant une preuve élémentaire complète, si elle existe, je vulgarise déjà la première partie facile du commentaire en bas de la page de Mathoverflow.

On peut supposer que les pilules sont rangées dans des boîtes numérotées de $1$ à $n$. L'étudiant ouvre tous les jours une boîte au hasard, s'il trouve une pilule entière il en mange une moitié, s'il trouve une moitié il la mange et s'il trouve une boîte vide il ne fait rien.

Une expérience équivalente est la suivante. On a $n$ urnes vides, et à tout instant $t\in\N^*$ on place une boule dans l'une des urnes. On cherche l'espérance du nombre maximum d'urnes contenant exactement une boule.

Soit $X_k$ le nombre d'urnes contenant exactement une boule à l'instant $k$. Soit $X=\max\{X_k\mid k\in\N^*\}$.
On cherche donc à montrer que $\mathbb{E}[X]=\dfrac{n}{e}+o(n)$.

Comme $X\geqslant X_k$, on a déjà la minoration $\mathbb{E}[X]\geqslant \mathbb{E}[X_k]$ pour tout $k$.

Or, $X_k=\sum_{j=1}^n X_{k,j}$ où $X_{k,j}=1$ si l'urne $j$ contient exactement une boule, et $X_{k,j}=0$ sinon. Donc $\mathbb{E}[X_k]=n\mathbb{E}[X_{k,1}]=n\mathbb{P}[X_{k,1}=1]$.

Or, $\mathbb{P}[X_{k,1}=1]$ est égal à $k$ fois la probabilité que la première boule soit tombée dans la première urne et que les autres boules soient tombées dans les autres urnes :

$$\mathbb{P}[X_{k,1}=1]=k.\frac{1}{n}\Big(1-\frac{1}{n}\Big)^{k-1}.$$
On en déduit que $\mathbb{E}[X]\geqslant \mathbb{E}[X_{k}]=n\frac{k}{n}\Big(1-\frac{1}{n}\Big)^{k-1}$.

En prenant $k=n$, on obtient que $\mathbb{E}[X]\geqslant n\Big(1-\frac{1}{n}\Big)^{n-1}\geqslant \dfrac{n}{e}$.
JLT
Re: QDV 19: le printemps est revenu!
il y a six années
avatar
Continuons. Comme $X\leqslant n$, il suffit de montrer les deux assertions suivantes :

(1) Pour tout $\epsilon>0$, $\mathbb{P}[\max\{X_1,\ldots,X_{3n}\}\geqslant n\big(\frac{1}{e}+\epsilon\big)]$ tend vers 0 ;

(2) Pour tout $\epsilon>0$, $\mathbb{P}[\sup\{X_k\mid k\geqslant 3n \}\geqslant n\big(\frac{1}{e}+\epsilon\big)]$ tend vers 0.

Pour $j\ne\ell$, on a
$$\mathbb{E}[X_{k,j}X_{k,\ell}]=\mathbb{P}[X_{k,j}=1,\;X_{k,\ell}=1]=\frac{k(k-1)}{n^2}\Big(1-\frac{2}{n}\Big)^{k-2}.$$

On en déduit que
$$\mathbb{V}(X_k)=n\frac{k}{n}\Big( 1-\frac{1}{n}\Big)^{k-1}+n(n-1)\frac{k(k-1)}{n^2}\Big(1-\frac{2}{n}\Big)^{k-2}-n^2\frac{k^2}{n^2}\Big(1-\frac{1}{n}\Big)^{2k-2}.$$

Il n'est pas difficile de montrer que le membre de droite est un $o(n^2)$. Ici, les $o$ sont "uniformes", c'est-à-dire que $o(f(n))$ est majoré en valeur absolue par $\epsilon(n)f(n)$ pour une fonction "universelle" $\epsilon(n)$, ne dépendant pas de $k$, tendant vers 0 à l'infini. En l'occurrence on pourrait montrer que $\mathbb{V}(X_k)\leqslant 100 n$ pour tout $n\geqslant 2$.

L'inégalité du bien-aimé Tchebycheff, ainsi que le fait que $\mathbb{E}[X_k]\leqslant \dfrac{n}{e}+o(n)$, entraîne alors que pour tout $k$ et pour tout $\epsilon>0$, l'expression $\mathbb{P}[X_k \geqslant n\Big(\frac{1}{e}+\epsilon\Big)]$ tend vers 0.

Fixons $\epsilon>0$. Choisissons un entier $r\geqslant \frac{6}{\epsilon}$. Pour tout $n$, il existe des entiers $k_1\leqslant k_2\leqslant\cdots\leqslant k_r$ tels que pour tout entier $k\in [ 1, 3n]$, $\exists j$, $|k-k_j|\leqslant \dfrac{6n}{r}\leqslant \epsilon n$. Comme $|X_k-X_{k_j}|\leqslant \epsilon n$, on a
\begin{eqnarray*}
\mathbb{P}[\max\{X_1,\ldots,X_{3n}\} \geqslant n\Big(\frac{1}{e}+2\epsilon\Big)]
&\leqslant& \mathbb{P}[\max\{X_{k_1},\ldots,X_{k_r}\} \geqslant n\Big(\frac{1}{e}+\epsilon\Big)]\\
&\leqslant&\sum_{j=1}^r \mathbb{P}[X_{k_j} \geqslant n\Big(\frac{1}{e}+\epsilon\Big)]
\end{eqnarray*}

tend vers 0. Ceci montre l'assertion (1).

La preuve de l'assertion (2) doit être du même acabit mais j'ai eu la flemme de faire tous les calculs. On montre que quand $n$ tend vers l'infini, la probabilité qu'au temps $k=3n$ il y ait au plus $\dfrac{n}{e}$ urnes contenant au plus une boule est proche de 1. Or, à tout instant $\ell\geqslant k$, il y a moins d'urnes contenant exactement une boule que d'urnes contenant au plus une boule à l'instant $k$, ce qui montre que la probabilité que $\sup\{X_k\mid k\geqslant 3n\}\geqslant n\Big(\dfrac{1}{e}+\epsilon\Big)$ tend vers 0.
JLT
Re: QDV 19: le printemps est revenu!
il y a six années
avatar
Question 2bis :

Quels sont les cinq plus grands nombres entiers qui s'écrivent en un seul mot dans la langue française, le plus grand étant gogolplex, comme l'a rappelé Alain un peu plus haut ?

----------------------

Je ne suis pas sûr de ce qui fait partie de la langue française ou non, mais on peut lire sur cette page

[fr.wikipedia.org]\%C3\%89chelles_longue_et_courte

$10^{603}$ : un centilliard
$10^{600}$ : un centillion
J'imagine qu'il y a aussi le noninonagintilliard ($10^{597}$) et le noninonagintillion ($10^{594}$).
Par contre, il n'est pas clair sur le tableau de wiki si on peut aller plus loin en parlant de uncentillion, uncentilliard, duocentillion, duocentilliard,... nonicentilliard ($10^{657}$) etc.
JLT
Re: QDV 19: le printemps est revenu!
il y a six années
avatar
Sinon, cette page

[en.wikipedia.org]

mentionne le quingentilliard ($10^{3003}$).
Re: QDV 19: le printemps est revenu!
il y a six années
avatar
Avec le calcul d'espérance, JLT a fait le plus rude.

Avec le principe de Maurey, on a


$P(|X_k-E[X_k]|\ge \epsilon n)\le 2\exp(-\frac{\epsilon^2 n^2}k)$, de sorte que pour $k\le n^{3/2}$, on a
$P(|X_k-E[X_k]|\ge \epsilon n)\le 2\exp(-\epsilon^2 \sqrt{n})$.

Mais $P(\exists k>n^{3/2}, X_k\ne 0)\le n P(Z_1+Z_2>n^{3/2})$ où $Z_1$ et $Z_2$ sont géométriques indépendantes de paramètre $1/n$.
$P(Z_1+Z_2>n^{3/2})\le 2P(Z_1>n^{3/2}/2)=2(1-\frac1{n})^{n^{3/2}/2}$.

Or $\lim_{n\to +\infty} n2(1-\frac1{n})^{n^{3/2}/2}=0$ et c'est fini.
Re: QDV 19: le printemps est revenu!
il y a six années
avatar
Principe de Maurey:

[fr.wikipedia.org]

(si je mettais dans le même message, ça buggait)
Re: QDV 19: le printemps est revenu!
il y a six années
avatar
Ah oui, juste une remarque: formellement, JLT et moi avons démontré la convergence en probabilité. Mais pour une suite de variables aléatoires bornées (*), cela entraîne la convergence des espérances (bon exercice de L3).

(*) c'est la remarque $X\le n$ de JLT.
JLT
Re: QDV 19: le printemps est revenu!
il y a six années
avatar
Merci aléa, j'ai bien fait de ne pas terminer tous mes calculs vu la concision de ta démonstration. Quelques éclaircissements pour les lecteurs qui, comme moi, ne manipulent pas fréquemment les probabilités :

1. $Z_1$ est le premier temps où une boule tombe dans l'urne no. 1, $Z_1+Z_2$ est le deuxième temps où une boule tombe dans l'urne no. 1. Donc $P(Z_1+Z_2>n^{3/2})$ est la probabilité qu'à l'instant $n^{3/2}$ il y a au plus une boule dans l'urne no. 1. Et donc $nP(Z_1+Z_2>n^{3/2})$ majore la probabilité qu'à l'instant $n^{3/2}$ il existe une urne contenant au plus une boule.

2. Le principe de Maurey est appliqué à $A=\{1,\ldots,n\}$, $B=\{1,\ldots,k\}$, $B_t=\{1,\ldots,t\}$, $\lambda=\epsilon n$ et à la variable aléatoire $X_k$. L'espace de probabilité $\Omega$ est l'ensemble des lancers de $k$ boules dans $n$ urnes. Le fait que $X_k$ est $\mathcal{B}$-Lipschitzienne signifie que si on modifie juste un des lancers à un instant $t$, le nombre final d'urnes contenant exactement une boule varie d'au plus une unité.
Re: QDV 19: le printemps est revenu!
il y a six années
avatar
Petite variation de l'exercice de bs: le taupin désargenté

Un taupin dispose d'une boite de pilules pour améliorer ses chances d'intégrer une grande école lors des concours. Il doit en prendre une chaque matin afin d'améliorer ses performances intellectuelles.
Comme les pilules sont chères, il adopte l'algorithme suivant: chaque jour, il prend une pilule au hasard dans sa boite. Il la coupe en deux avant d'en avaler une moitié et de remettre l'autre dans la boite.
Si la boite contient initialement $n$ pilules de taille normale, montrer que l'espérance du nombre maximal de demi-pilules présentes dans la boite est équivalent à $Kn$ quand $ n$ tend vers l'infini, $K$ étant à déterminer.

Même question pour les quarts de pilules, huitièmes de pilules, etc...

(Dans ce modèle, le taupin est immortel et le concours est éternellement repoussé...)
JLT
Re: QDV 19: le printemps est revenu!
il y a six années
avatar
Edit: ce qui suit est FAUX.

Pour des pilules de taille $2^{-m}$, c'est $K=e^{-m}$.

Ici on regarde l'espérance du nombre d'urnes contenant exactement $m$ boules, qui vaut
$$n\times\frac{k(k-1)\cdots (k-m+1)}{n^m}\Big(1-\frac{m}{n}\Big)^{k-m}$$
qui vaut environ $n(xe^{-x})^m$ où $x=\dfrac{k}{n}$. Ceci est maximum lorsque $x=1$, et l'espérance vaut alors $ne^{-m}$.
Re: QDV 19: le printemps est revenu!
il y a six années
avatar
N'est-ce pas plutôt

$\displaystyle n\times\frac{k(k-1)\cdots (k-m+1)}{m! n^m}\Big(1-\frac{1}{n}\Big)^{k-m}$ ?


(Le deuxième terme du produit est la probabilité $\mathcal{B}_{k,\frac1{n}}(\{m\})$ )
JLT
Re: QDV 19: le printemps est revenu!
il y a six années
avatar
Oups, oui j'avais oublié de diviser par $m!$ (qui vient du fait que l'on peut permuter les boules dans une urne qui en contient $m$) et en plus j'avais confondu urne et boule en écrivant le dernier terme...

Bref, $K=\dfrac{m^me^{-m}}{m!}$.

Je devrais arrêter d'économiser sur les pilules...
JLT
Re: QDV 19: le printemps est revenu!
il y a six années
avatar
De toute façon l'exercice n'est pas réaliste, au bout de quelques années la plupart de ses pilules sont réduites à l'état d'atomes.
bs
Re: QDV 19: le printemps est revenu!
il y a six années
avatar
Bonjour les thumbs down superchampions thumbs down ,

Question 4 :

Oui aléa, c'est dans le Beautiful Mathematics de Martin Erickson que j'ai trouvé l'énoncé : j'ai juste modifié un peu la fin pour adapter l'exercice au niveau des intervenants ;)

J'ai traduit avec ton aide, merci infiniment,

" ... show than the expected maximum number oh half pills in the bottle tends to $\dfrac{n}{e}$ as $n$ tends to infinity."
par

"...montrer que l'espérance du nombre maximal de demi-pilules présentes dans la boîte est équivalent à $Kn$ quand $n$ tend vers l'infini, $K$ étant à déterminer."

Amicalement.
Re: QDV 19: le printemps est revenu!
il y a six années
avatar
Eh bien, c'était dur...

JLT est trop modeste car il a fait bien plus que traduire la remarque de Johan Wästlund: il a montré que le modèle équivalent était exploitable dans le domaine discret, alors que Johan Wästlund l'abandonnait aussitôt pour étudier un analogue continu.
bs
Re: QDV 19: le printemps est revenu!
il y a six années
avatar
Bonjour,

Question 1bis : recherche d'une équation paramétrique du cercle passant par les points $(1,0,0), (0,1,0),(0,0,1)$.

egoroffski, je suppose que ta réponse proposée ici est exacte, voilà la courbe obtenue avec le "spacecurve" de Maple. Lorsque je tente de calculer pour quelles valeurs du paramètre $t$ la courbe passe par les trois points mentionnés, les calculs sont délicats, même avec Maple.

Qu'as-tu choisi pour $v, w$ ? Merci.

[attachment 27805 cercle50.JPG]

Amicalement.
JLT
Re: QDV 19: le printemps est revenu!
il y a six années
avatar
C'était plutôt

\begin{align*}
f(t) &= \frac{1}{3} + \frac{\sqrt{3}}{3} \cos t + \frac{1}{3} \sin t \\
g(t) &= \frac{1}{3} - \frac{\sqrt{3}}{3} \cos t + \frac{1}{3} \sin t \\
h(t) &= \frac{1}{3} - \frac{2}{3} \sin t
\end{align*}
Re: QDV 19: le printemps est revenu!
il y a six années
Bon décidément je ne sais plus calculer... sad smileysad smileysad smiley

Je n'ai plus mon brouillon, mais de mémoire j'ai pris $v=a(1,-1,0)$ et $w=b(1,1,-2)$ pour $a,b$ bien choisis (du moins je le pensais).

PS : Ah tiens, en l'écrivant, j'ai trouvé mon erreur : j'ai semble-t-il conclu un peu rapidement que $1^2+1^2+(-2)^2=5$ thumbs up du coup en multipliant tous les sinus par $\sqrt{5/6}$ dans ma réponse erronée, on retombe sur celle de JLT.
bs
Re: QDV 19: le printemps est revenu!
il y a six années
avatar
Bonjour,

Question 1bis : thumbs down

Équation paramétrique du cercle passant par $(1,0,0),(0,1,0),(0,0,1)$

Vos équations paramétriques peuvent se réécrire :

\begin{align*}
f(t) &= \frac{1}{3} + \frac{2}}{3} \sin (t+\frac{\pi}{3}) \\
g(t) &= \frac{1}{3} + \frac{2}}{3} \sin (t-\frac{\pi}{3}) \\
h(t) &= \frac{1}{3} + \frac{2}{3} \sin (t+\pi)
\end{align*}
Le cercle passe par $(1,0,0),(0,1,0),(0,0,1)$ respectivement pour $t=\dfrac{\pi}{6}$, $t=\dfrac{5\pi}{6}$ et $t=\dfrac{3\pi}{2}.$

Question 2bis :

Merci JLT pour tes liens; ainsi, les cinq plus grands nombres entiers s'écrivant en un seul mot en français seraient :

gogolplex= $10^{gogol}$ > quingentilliard $=10^{3003}$ > quinquagintaquadringentilliard $=10^{2703}$ > Quadringentilliard $=10^{2403}$ > Quinquagintatrecentilliard $=10^{2103}$ >

....(et sur une autre page Wikiki) ...

> centilliard $= 10^{603}$ > centillion $= 10^{600}$ > nonagintilliard $= 10^{543}$ > nonagintillion $= 10^{540} >....$

Le gogolplex proposé par Alain est de loin le plus grand.

Ces mots se trouvent sur la toile, sur Gogol, sur Wikiki, mais figurent-ils sur les dictionnaires ou encyclopédies (Larousse, Littré, Académie Française) de langue française ?

Merci à tous, amicalement.
bs
Re: QDV 19: le printemps est revenu!
il y a six années
avatar
Bonjour,

Question 4 : "... montrer que l'espérance du nombre maximal de demi-pilules présentes dans la boîte est équivalent à $\dfrac{n}{e}$ quand $n$ tend vers l'infini".

Par ailleurs, si $S_n$ est l'ensemble des permutations de l'ensemble $[1,n]$, alors le nombre $d_n$ de dérangements [permutations sans point fixe] tend vers $\dfrac{n!}{e}$ quand $n$ tend vers l'infini.

Connaissez-vous d'autres exercices de ce genre dans lequel apparaît également le nombre $e$ ?

Référence : Toutes les questions proposées ici proviennent d'un joli cadeau de mon ami Aleg :) : le Beautiful Mathematics de Martin Erickson.

Ce Beautiful Mathematics avait déjà été source d'inspiration pour l'exercice Comtet 32 lors de la QDV 12 & H 63 (2): Combinatoriennes, ...

Joyeuses Pâques.

Amicalement.
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 138 314, Messages: 1 342 660, Utilisateurs: 24 796.
Notre dernier utilisateur inscrit DidierBourbon.


Ce forum
Discussions: 884, Messages: 11 411.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page