Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 11-05-2017 15:26:44

Varzmir
Habitué de Prise2Tete
Enigmes résolues : 22
Messages : 17

Une suite aélatoire

Bonjour à tous, c'est ma première énigme sur le forum. J'espère que vous l'apprécierez.
Soit (Un) une suite définie par la relation de récurrence suivante :
U0 = 1
U(n+1) = U(n) * (r(n)+w)
avec w un réel fixé et r(n) une suite de réels aléatoires équiprobables entre 0 et 1.
La question est la suivante : Quelle est la valeur que l'on doit donner à w pour que la suite Un ne tende asymptotiquement ni vers 0, ni vers l'infini ?
Bien sur w ne vaut pas 1/2, ce serait trop beau smile
La case réponse est validée par un nombre de la forme 0.abcdef


 
Réponse :
  • |
  • Répondre

#0 Pub

 #2 - 11-05-2017 17:22:13

Ebichu
Expert de Prise2Tete
Enigmes résolues : 49
Messages : 888

ine suite aléatoire

Spoiler : [Afficher le message] Je dirais la solution de l'équation (x+1).ln(x+1)-x.ln(x)-1=0 soit environ 0,542211.

PS : tu devrais cacher les réponses des joueurs pendant quelques temps pour laisser à tout le monde le temps de chercher.

 #3 - 11-05-2017 18:12:05

Varzmir
Habitué de Prise2Tete
Enigmes résolues : 22
Messages : 17

une suote aléatoire

Effectivement Ebichu c'est bien ça !
Oui bonne idée, je vais cacher les réponses pour 24h

 #4 - 12-05-2017 18:54:08

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 398

Une suite aléatoiire

Ca m'a l'air bien compliqué...
Pour l'instant, j'ai pour fonction de densité de
- U1 :
0 si x < w ou si x > w+1
1 si w < x < w+1

-U2 :
0 si x < w^2 ou si x > (w+1)^2
ln(x) - 2ln(w) + 1 + 1/w si w^2 < x < w(w+1)
2ln(w+1) - ln(x) - 1 - 1/(w+1) si w(w+1) < x < (w+1)^2

Après, ça se complique pas mal...

 #5 - 12-05-2017 23:29:27

Varzmir
Habitué de Prise2Tete
Enigmes résolues : 22
Messages : 17

une suite aléatoite

Je ne comprends pas bien ce que vaut x dans ton explication... C'est la valeur du paramètre ou c'est le nom de la variable aléatoire ( r(n) dans [0,1] )?
Un petit conseil :
Spoiler : [Afficher le message] Une astuce serait de transformer le produit en somme avec un logarithme puis de regarder en moyenne la valeur de ln(U(n+1)) - ln(Un) 

 #6 - 13-05-2017 00:32:26

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 398

Une suie aléatoire

x est la variable de ma fonction de densité.
Ca veut dire que P(U2<x) = int f(t) dt ou f est la fonction de densité décrite ci dessus.

Je suppose que ce que tu veux faire est
ln(produit) = somme( ln(r + w))
et ln(r+w) vaut en moyenne (1+w)ln(1+w) - 1 - w ln(w)
on cherche (1+w)ln(1+w) - 1 - w ln(w) = 0 ce qui donne w = 0.542211

J'avais pensé à faire le passage par les logarithmes mais je ne pensais pas aboutir.

reste à voir si tout ça est rigoureux... Je pense que le résultat est juste, mais c'est toujours difficile d'être rigoureux en probas.
Il faut déjà savoir qu'il y a 4 définitions non équivalentes de la convergence de suite de variables aléatoires, il faudrait déja savoir pour quelles définitions la convergence marche...
Je regarderais ça demain...

 #7 - 13-05-2017 15:59:29

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 398

une suite améatoire

Après une bonne prise de tête, je pense avoir enfin une solution à peu près satisfaisante sur ce problème.
Notons W la solution trouvée, qui est l'unique solution de [latex](w+1)ln(w+1) - wln(w) = 1[/latex]

D'abord, une petit résumé de ma réflexion sur ce problème:
Outre chercher la loi pour n quelconque comme j'ai commencé à faire, ce qui n'est vraiment pas simple, la première interprétation du problème serait de trouver w tel que la limite de [latex]\mathbb{E}(U_n)[/latex] ne tendait ni vers 0 ni vers +oo.

En passant par logarithme, on démontre que [latex]\mathbb{E}(log(U_n))[/latex] est nulle si et seulement si [latex]w = W[/latex].
On en conclut de manière erronée que [latex]\mathbb{E}(U_n) = e^0 = 1[/latex] avec [latex]w = W[/latex]
Or [latex] \mathbb{E}(U_n) = \prod \mathbb{E}(r_n+w) = \mathbb{E}(r + w)^n [/latex]car les [latex] r_n + w[/latex] sont indépendants.
La moyenne convergera donc vers une valeur autre que 0 et [latex]+\infty[/latex] si et seulement si [latex]\mathbb{E}(r + w) = 1[/latex], soit [latex]w  = 1/2[/latex]...

Mazette, la première intuition aurait elle été la bonne?

Par simulation informatique, on se rend compte que Un semble bien converger vers 0 quand [latex]w = 1/2[/latex], et avoir un comportement incertain quand [latex]w = W[/latex]. Où se trouve l'erreur?
En creusant un peu, pour [latex]w = 1/2[/latex], on se rend compte que plus le nombre de termes dans le produit devient élevé, plus il y a de valeur inférieures à 1, et de plus en plus proches de 0, mais également de plus en plus rares valeurs très grandes devant 1.
La moyenne reste donc égale à 1, car compensée par les très grande valeurs, mais notre suite semble quand même tendre vers 0.

A l'inverse, pour [latex]w = W[/latex], la moyenne est infinie, mais il y a en moyenne autant de valeur inférieures à 1 que supérieures à 1.

On remarque donc que raisonner sur la convergence de l'espérance ne résout pas du tout le problème.

Solution:
On va prendre comme convergence la convergence en probabilités, qui sera pratique à utiliser dans notre cas, et qui est plus forte que la convergence en loi.
[TeX]\forall \epsilon >0[/TeX]
[TeX]\mathbb{P}(|U_n| < \epsilon) = \mathbb{P}(V_n < ln(\epsilon))[/TeX]
avec [latex]V_n = \sum ln(r+w)[/latex]
[TeX]\mathbb{P}( \dfrac{V_n - nE}{v\sqrt{n}} < \dfrac{ln(\epsilon) - nE}{v\sqrt{n}})[/TeX]
ou E est l'espérance de [latex]ln(r+w)[/latex] et v son écart type.

On a [latex]\dfrac{V_n - nE}{v\sqrt{n}} \to Z [/latex] où Z suit la loi normale N(0,1) (théorème centrale limite)

Comme [latex]F(x) = \mathbb{P}(x < y) [/latex] est une fonction continue:
[TeX]\mathbb{P}(\dfrac{V_n - nE}{v\sqrt{n}} < \dfrac{ln(\epsilon) - nE}{v\sqrt{n}}) \to P( Z < \dfrac{ln(\epsilon) - nE}{v\sqrt{n}} )[/TeX]
Cette probabilité tend vers 1 presque surement si et seulement si [latex]\dfrac{ln(\epsilon) - nE}{v\sqrt{n}}[/latex] tend vers [latex]+\infty[/latex], ce qui est équivalent à [latex]E<0[/latex]

or [latex]E<0[/latex] si et seulement si [latex]w < W[/latex]

Donc pour tout w < W, notre variable tend vers 0.
Par le même raisonnement, si w > W, on peut montrer que quel que soit N > 0, P(Un > N) tend vers 1 presque surement, ce qui justifie que Un tend vers +oo.
Enfin, si w = W, il n'y a pas de convergence car P(Un < 1) = 1/2 pour tout n, ce qui confirme le résultat énoncé.


Je me réserve le droit à l'erreur, mais je pense que c'est suffisamment rigoureux...

Merci pour cette belle énigme, qui montre qu'il ne faut pas trop faire confiance à l'instinct en math!

 #8 - 13-05-2017 22:18:35

Varzmir
Habitué de Prise2Tete
Enigmes résolues : 22
Messages : 17

Une suite aléatooire

Wow, impressionant ! Je ne m'attendais pas à une réflexion aussi poussée smile
Je dois t'avouer que je ne me rendais pas compte de ce que pouvait réserver cette question au niveau de la subtilité des définitions (la limite de l'espérance qui ne vaut pas la limite de la moyenne des termes... je trouve ça assez déroutant).
Maintenant ca me met plein de doutes... Effectivement, si P(Un+1 - Un >0) = P(Un+1 - Un < 0) = 1/2 , alors w vaut effectivement 1/2. Mais si l'on cherche w tel que 0< lim Un < +oo, alors w vaut W.
Merci à toi aussi pour avoir aussi bien développé cette question !

EDIT : après simulation je trouve que la limite de la moyenne des termes vaut 0 pour w=1/2 et n'a pas de limite apparente pour w=W : ca me donne alternativement 0.97, 3*10E8, 1410, 0.03...

 #9 - 14-05-2017 18:04:22

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 398

Une suiite aléatoire

Il faut faire très attention dans la simulation, car l'estimateur classique de la moyenne, la moyenne empirique, est ici un très mauvais estimateur...
Comme je l'ai montré, si on prend U300 avec w = 1/2, qui est le produit de 300 loi uniformes, il y aura de très nombreuses valeurs inférieures à 1, et très proches de 0, et de très très rares très grandes devant 1. Si on fait la moyenne empirique sur 100, 200 termes, il y a une forte probabilité que tout les termes soient très proches de 0, et qu'on trouve un résultat nul. Mais si tu poursuis tes simulation, tu devrais trouver parfois des valeurs de la moyenne très différente, et parfois très grandes devant 1.
Le problème ici est que cet estimateur n'est pas assez efficace pour converger suffisamment au bout de 100 ou 200 itérations, car il converge extrêmement lentement.
J'ai fait la simulation du produit de n =  300 loi uniformes avec w = 1/2  10 000 000 de fois, et j'ai obtenu le résultat:
moyenne : 0.8241122006919434
nombre de valeurs supérieures à 1: 51268

On a donc seulement 0,5% des valeurs qui sont supérieures à 1, mais une moyenne très différente de 0. Effectivement, la moyenne n'est pas 1, mais c'est car l'estimateur n'a toujours pas convergé (et il y a peut être aussi des phénomènes d'arrondis qui rapprochent la moyenne de 0?), mais en tout cas, soit certain que du point de vue théorique, la moyenne est bien 1.  (Mais sinon, reprend le calcul de l'espérance, ma démonstration est exacte, ou alors fait la simulation avec un n plus petit, tu verras que la moyenne est toujours 1.

La question d'estimateur efficace est très intéressante en statistiques et amène à de nombreux paradoxes...

Ici, l'estimateur de la moyenne empirique n'est certainement pas le meilleur pour inférer sur la moyenne, il doit en exister un qui donne de meilleurs résultats, et c'est tout l'objet de la théorie de la statistique inférentielle:
On sait que nos valeurs suivent une certaine loi (par exemple la loi normale d'espérance 0), mais on ignore quelle est la valeur d'un paramètre. (par exemple la variance de la loi normale.) On peut se dire que le meilleur moyen est ici de calculer la variance empirique, c'est à dire [latex]\dfrac{1}{n}\sum x_i^2[/latex]. évidemment, si on a un grand nombre de valeurs [latex]x_i[/latex], cet estimateur va donner un bonne approximation de la variance. En revanche, le calcul [latex]\dfrac{1}{n-1}\sum x_i^2[/latex] va donner en moyenne une valeur plus précise de la variance, même si à première vue, ce n'est pas intuitif...

Pareil pour w = W, si tu obtient des moyennes différentes à chaque simulation, c'est bien la preuve que ton estimateur n'a pas convergé, et qu'il faut faire le calcul sur un nombre beaucoup plus grand de valeurs. Ici encore, si tu reprend ma démo, tu verras bien que l'espérance tends vers +oo quand n augmente

 #10 - 14-05-2017 18:34:24

Varzmir
Habitué de Prise2Tete
Enigmes résolues : 22
Messages : 17

unr suite aléatoire

En fait je m'étais dit que si la limite d'une suite existe, alors la moyenne des termes converge vers cette valeur obligatoirement. Les valeurs dont je parlais précédemment étaient bien une estimation de la moyenne des termes lim n->+oo (U0+U1+...Un)/n et pas de l'espérance. Et ça confirme bien ce que nous disions : la limite de la suite pour w=1/2 est bien 0 (et pour w=W celle-ci est extremement difficile à déterminer puisqu'elle ne tend ni vers 0 ni vers l'infini).
En revanche, au niveau des espérances en effet, lim E(Un) quand n->+oo est bien aux alentours de 1 pour 1/2 et tend vers l'infini pour w=W dans les simulations.
D'où l'importance des définitions en mathématiques big_smile

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Pim, Pam et ?

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete