EIBougnador
2019-07-01 15:30:43
Le 30 juin 2019 à 22:15:51 Pirvence a écrit :
Je vais passer en L2 et j'ai jamais compris comment fonctionne la réccurence
La récurrence, c'est une des idées les plus fondamentales en mathématiques. Ce qui est beau, c'est qu'elle est accessible très très tôt dans la formation mathématique, mais qu'à haut niveau, de nombreuses notions utiles ont fait vraiment le même principe de base au fond, qui est "propager de proche en proche"(des notions utiles aux noms barbares comme connexité, Cauchy-Lipschitz, ordinaux(qui comprennent que pour faire des récurrences au-delà de l'infini, c'est le principe de récurrence forte qui est pertinent ), structure engendrée par une sous-partie, etc.).
Ce que dit le principe de récurrence, c'est que si tu as une propriété qui dépend d'un nombre entier N (par exemple "N est un nombre pair"), eh bien dès lors qu'on a les deux conditions suivantes :
- la propriété est vraie pour N=0 ;
- si la propriété est vraie pour un entier N, alors elle l'est automatiquement pour l'entier N+1 (formellement : pour tout entier N, si tu as P(N), alors tu as P(N+1))
alors on a automatiquement :
- pour tout entier N, la propriété P(N) est vraie.
La première des deux hypothèses s'appelle l'initialisation, la seconde l'hérédité.
Et c'est assez intuitif : imagine une chaîne de dominos. Imagine qu'en faire tomber un fait forcément tomber le suivant (hérédité). Bah si tu fais tomber le premier (initialisation), alors ils tomberont tous !
Si on veut se convaincre avec les mains de ce principe, c'est pas très dur. Tu as P(0), par initialisation. En utilisant l'hérédité, comme tu as P(0), tu en déduis P(1). Puis en utilisant l'hérédité, comme tu as P(1), tu en déduis P(2). Puis comme tu as P(2), tu en déduis P(3). Et coetera.
C'est une preuve "avec les mains", à cause du "et coetera". "Et coetera" qui revient un peu à appliquer un principe de récurrence en fait.
Je pense que le mieux, c'est d'accepter ce principe comme postulat de départ, après avoir compris en quoi il était très naturel. Ne pas forcément chercher à le démontrer. Car pour le démontrer, tu devras forcément partir d'un autre postulat de départ("on ne démontre rien à partir de rien", problème type "premier mot du dictionnaire"), et il y a des chances que ce point de départ ne soit pas forcément beaucoup plus intuitif que ce principe lui-même.
Mais par exemple, si tu acceptes que tout ensemble formé d'entiers naturels(les entiers qui sont positifs ou nuls)est soit vide, soit admet un plus petit élément, alors tu peux démontrer le principe de récurrence. Prends une propriété P qui vérifie les deux hypothèses (initialisation, hérédité), et regarde l'ensemble E des entiers qui ne vérifient pas ta propriété. Si cet ensemble est non-vide, alors il a un plus petit élément, qu'on va noter M. Forcément, M n'est pas 0, à cause de l'hypothèse d'initialisation. Donc M-1 est bien un entier naturel. Comme M est le plus petit élément de E, M-1 n'est pas élément de E. Par définition de E, cela signifie que M-1 vérifie la propriété P(il ne vérifie pas "ne pas vérifier la propriété P"). Par hérédité appliquée pour N=M-1, l'entier M devrait vérifier P ; donc il ne devrait pas être dans E. Or par définition, il est dans E.
On a donc une contradiction : ça veut dire que notre hypothèse de travail selon laquelle E est non-vide était erronée. Cela signifie donc que E est vide. Ce qui signifie que la propriété P est vérifiée par tous les nombres entiers
C'est super le principe de récurrence, car cela permet, avec un nombre fini d'arguments et un peu d'abstraction, de démontrer quelque chose pour une infinité de nombres (en fait tous les nombres).
Un exemple ? Imagine que tu veuilles démontrer que pour tout N, si on additionnes tous les nombres entiers naturels inférieurs ou égaux à N, le nombre obtenu est N(N+1)/2.
Bah pour N=0, on a juste le nombre 0 qui est inférieur ou égal à 0, ce qui correspond bien à 0 fois (0+1) divisé par 2. OK pour l'initialisation donc(au pire, si additionner un seul nombre te paraît source de confusion, initialise en N=1 plutôt qu'en N=0, tu en déduiras la conclusion pour tous les entiers strictement positifs ). Maintenant, donne-toi un entier N et supposes que la formule est juste pour ce N. Il s'agit de la démontrer pour N+1.
Et bah Somme_des_trucs(N+1)=Somme_des_trucs(N)+N+1.
Or Somme_des_trucs(N) = N(N+1)/2, par hypothèse de récurrence.
Donc Somme_des_trucs(N+1)= N(N+1)/2+N+1=N²/2+3N/2+1.
Or (N+1)((N+1)+1)/2=(N+1)(N+2)/2=N²/2 + 3N/2 + 1.
Donc Somme_des_trucs(N+1) = (N+1)((N+1)+1)/2.
La propriété recherchée est donc vraie pour N+1. On donc établie que la propriété étudiée vérifiait l'hérédité. Puisqu'elle vérifie à la fois initialisation et hérédité, par le principe de récurrence, elle est vraie pour tout entier N
Attention, par contre, il est essentiel d'initialiser ta récurrence hein. (C'est naturel dans la métaphore dominos, il faut une pichenette au début pour s'assurer que tout tombe.)
En effet, sinon, tu peux démontrer n'importe quoi. Par exemple, la propriété "N>N" est héréditaire : si N>N, alors N+1 > N+1 (ajouter 1 de chaque côté d'une inégalité stricte laisse l'inégalité stricte valable). Seulement, la propriété N>N n'a pas lieu pour tout entier N, mais pour aucun entier N ! Cela ne viole pas le principe de récurrence, puisqu'on n'avait pas l'initialisation.Il faut aussi bien veiller à l'initialiser à un certain nombre (dans notre explication, 0), puis démontrer que dès qu'on prend N supérieur ou égal à ce nombre, si la propriété a lieu, alors elle a lieu pour le nombre suivant. On en déduit alors la propriété pour tout N supérieur ou égal à ce nombre. Si on sort de cadre, à nouveau, on peut faire n'importe quoi. (Toujours très naturelle sur la métaphore dominoesque).
On va démontrer que si on se donne un nombre fini de points dans le plan, ils sont forcément alignés (ce qui est faux, donc y aura une faille dans la preuve). La propriété P(N), c'est "si on se donne N points distincts dans le plan, alors ils sont alignés".
Initialisation : c'est vrai pour N=2 ; deux points sont toujours alignés
Hérédité. Suppose que c'est vrai pour N. Montrons-le pour N+1. J'ai des points que j'appelle P(1), ..., P(N+1). Par hypothèse de récurrence, les points P(1), ..., P(N) sont alignés. Par hypothèse de récurrence, les points P(2), ... P(N+1), également au nombre de N, sont eux aussi alignés. On en déduit que les points P(1), ... , P(N+1) sont alignés. D'où l'hérédité.
Par récurrence, si on se donne un nombre fini de points dans le plan, ils sont alignés.
A-t-on fait bugger le principe de récurrence ?
Non. En fait, pourquoi avoir les N premiers points et les N derniers points alignés impliquerait que les N+1 points dans leur totalité sont alignés ? On a une droite qui contient les N premiers, une qui contient les N autres, mais pourquoi ce serait la même droite ? Ah-ah ! Aucune raison ! L'honneur est sauf. Sauf ? Sauf que... Bah y a N-1 points qui sont communs à la fois à {P(1),...,P(N)} et {P(2),...,P(N+1)} : les points numérotés de 2 à N. Si chacune des deux droites qu'on considère doit passer par ces N-1 points, ces deux droites doivent être identiques : notre argument n'était pas détaillé, mais il était correct. On a fait planter les mathématiques.
Saut que attends : si N-1 = 1, ça marche pas du tout cet argument ! Par un point, on peut faire passer plein de droites !
Eh oui, l'hérédité, on la montre, en effet, mais sous l'hypothèse que N-1 > 1, à savoir N>2, alors qu'on devrait le faire pour N supérieur ou égal à 2. Elle est là, notre arnaque fondamentale. Eeet... voilà
EIBougnador
2019-07-01 15:43:09
Le 01 juillet 2019 à 15:35:55 HamiltonJacobi a écrit :
Pourquoi est-ce qu'on augmente la filtration quand on fait du calcul stochastique ?
La filtration, c'est une collection croissante de tribus car la tribu collecte l'information visible dans le passé, et que le passé augmente avec le temps (la suite ]-infini, t] croît au sens de l'inclusion avec t). Mais je pense que ce n'est pas ta question, et que tu parles d'augmentation en mode "compléter les tribus pour ajouter les négligeables". J'imagine que c'est juste parce qu'il y a un certain nombre d'événements qui sont naturels à considérer, qui ne sont pas mesurables, mais qui "ont quand même proba zéro" puisqu'ils sont clairement inclus dans des événements très concrets et de proba nulle.
En mode prototype, si tu prends R^{[0,infini[} avec la tribu produit de tribus boréliennes, les singletons ne sont pas mesurables, alors qu'on a clairement envie de dire "nan mais ça, va, demander que le brownien soit égal à une trajectoire prescrite, ça a proba nulle quand même". Et carrément, ouais : prescrire la valeur à l'instant 1, ça donne déjà une proba nulle, alors la prescrire en tout point.
Oui, mais agneugneu, c'est pas mesurable. Compléter la tribu en rendant les "parties de négligeables mesurables, et de proba nulle", ça permet de parler de ces événements sans se prendre la tête.