Martingale de l'excédent

[lyceen95]

"La théorie nous dit que la matrice Proj obtenue est le projecteur spectral pour M associé à la valeur propre 1."

Je suis bien content pour toi : tu cherchais un projecteur spectral, et tu l'as trouvé. J'avais déjà croisé des projecteurs vidéo, mais je ne savais même pas que dans la famille des projecteurs, il y avait des projecteurs spectraux.
La prochaine fois que je croiserai un projecteur vidéo, je lui demanderai s'il a un cousin qui est spectral.

Plus sérieusement, ces notions me dépassent complètement ; déjà , quand j'ai vu le mot PolynomialRing, j'ai bien imaginé que Ring, c'était la traduction de la notion d'anneau qu'on a en algèbre, mais j'ai surtout imaginé que c'était une coïncidence.

[beagle2]

Bon alors hier soir j'ai fait un peu vite et j'ai mangé une branche
on a donc en direct plutôt:
1/2 + (1/2)^3 + 2(1/2)^5 + 5(1/2)^7 + 13(1/2)^9
qui fait déjà 0,752
je pense arriver plus facilement à 0,8

Mais comme je ne fais pas avec ordinateur c'est sur une feuille A4 et vite brouillon.

Sinon , non ce n'est pas l'idée de Lycéen que je fais.

je reteste et vous en reparle.
bon il n' y a rien d'extraordinaire derriere ça non plus
ne soyez donc pas en attente de la chaine du beagle!

ps: pour l'indirect par le complémentaire ça change aussi bien sur:
1 - [(1/2)^4 + 3(1/2)^6 + 8(1/2)^8]
qui donne 0,859

[GaBuZoMeu]

Tu es sûr que ce n'est pas ?

[GaBuZoMeu]

Lycéen95 : un cours où on parle en détail des projecteurs spectraux. Quand on fait de l'algèbre linéaire, un projecteur est un endomorphisme tel que . Par exemple, dans un espace euclidien, l'endomorphisme de projection orthogonale sur un sous-espace est un projecteur. C'est une notion très utile, mais je conçois bien que ce ne soit pas d'un usage courant en informatique.

[beagle2]

Tu es sûr que ce n'est pas ?

13 j'ai trouvé ça bizarre, possible encore un oubli.
De toutes façons j'arrète.

Donc on avait bossé ici et sur le site de Pierre, le fait que:
il y a autant de chemins qui font +5 que de chemins qui font -5 en premier, donc c'est meme proba de passer de 20 à 25 que de 20 à 15
proba 1/2 de 25, proba 1/2 15

et je suis à 15
15 1/2 d'aller à 20 par rapport à baisser à 10 1/2

Puis de 20 à 25 c'est le (1/2)^3
ou 15
10 donne 15 ou 5
c'est ce 5 qui fera le zero du (1/2)^4
and so on, arbre de proba ...

[GaBuZoMeu]

Ah ben voila ! Enfin une explication qui permet de comprendre. Par contre, ce que je ne comprends toujours pas, c'est pourquoi tu as fait autant de cachotteries.

C'est une belle idée, elle revient en gros à dire que tu considère des marches à pas de géant où tu montes ou descend de 5 niveaux d'un coup. On peut alors tout diviser par 5, se dire qu'on est au niveau 4 et qu'on est content si on arrive au niveau 5, mais qu'on risque de tout perdre en arrivant au niveau 0.

Le premier cas où on a cet ennui d'avoir un chemin qui arrive au niveau 5 en étant passé par le niveau 0, c'est pour un chemin de longueur 9 - et il y a alors un seul chemin de cet acabit. Le nombre de bons chemins de longueur 9, ceux qui arrivent pour la première fois au niveau 5 sans être passés par le niveau 0, est donc bien 14 (le nombre de Catalan ) moins 1, ce qui fait bien 13 comme tu trouves.
On peut donner une formule pour les autres coefficients en utilisant la réflexion à deux miroirs comme je l'ai fait plus haut. Pas ce soir, demain si j'ai le temps et le courage.

[lyceen95]

Effectivement, compter uniquement les cas où le compteur change de cinq-aine, c'est très fûté.

[lyceen95]

Quand on fait de l'algèbre linéaire , un projecteur est ...

C'est une projection, une application qui vérifie P^2=P ... Voilà, c'est clair. pour moi simple lycéen, une projection, je maitrise, je comprend. C'est un mot que j'ai entendu des centaines de fois. Et je vois très bien pourquoi la propriété P^2=P nous intéresse ici : cette projection c'est la fonction obtenue quand on multiplie notre matrice de Markov par elle-même une infinité de fois.

Pourquoi appeler cela un projecteur spectral !
Ce n'est pas une question, c'est une exclamation ; je ne veux surtout pas la réponse à cette exclamation.

[GaBuZoMeu]

Pourquoi ne pas l'appeler comme ça puisque c'est un projecteur et que ça relève de la théorie spectrale des endomorphismes linéaires ? Il est interdit d'employer un terme technique consacré que tu ne connais pas ? J'avais donné un lien sur l'autre fil où je définissais ce terme. Je ne comprends pas ta réaction.

PS. Wikipedia.

[beagle]

La difficulté si on raisonne par 'estimation', c'est que les résultats obtenus après 20 , 40, 60 ou même 100 tirages sont biaisés. Après 100 tirages, Charles va gagner dans 70% des cas, il va perdre dans 10% des cas, et la partie ne sera pas terminée dans 20% des cas (je donne des pourcentages très approximatifs, je n'ai pas les chiffres sous les yeux). On peut être tenté de dire que Charles gagne 7 fois plus souvent qu'il ne perd.
Mais en fait, dans les 20% restants, la situation va s'équilibrer, la moitié seulement de ces cas va conduire à une victoire de Charles. Et on va arriver aux 80% de victoire pour 20% de défaite.

Je te mets les chiffres qui permettent de voir si un coté avance plus vite ou non que le milieu.
donc la cinétique devrait dire où on va avec un estimateur.
Dans le cas présent on avance (les gains) dans la même proportion que le complémentaire qui enlève les pertes:
Voici les derniers sondages:

en direct:
1/2 + (1/2)^3 + 2(1/2)^5 + 5(1/2)^7 + 13(1/2)^9 +34 (1/2^)^11 + ...
soit une progression:
0,5 ; 0,62 ; 0,69 ; 0,73 ; 0,75 ; 0,77 (0,7685)


en indirect:
1 - [(1/2)^4 + 3(1/2)^6 + 8(1/2)^8 + 21(1/21)^10 +...]
soit une diminution:
0,93 ; 0,89 ; 0,86 ; 0,84

le 0,75 est à 5 de l'objectif (puissance 9) en direct
lorsque les puissance 8 et 10 qui l'encadrent sont à 6 puis 4 en indirect

plus cinétique d'amortissement non étudié, mais qui pourrait se faire un jour si besoin...

[Sylviel]

J'ai l'impression que cela n'as pas été dis mais, sauf erreur de ma part, la réponse à l'exercice posé par GBZM s'obtient avec 0 calcul et assez peu d'arguments (Martingale bornée + temps d'arrêt presque sûrement fini).
Une fois qu'on a l'espérance et en sachant qu'il n'y a que 2 résultats possibles on obtient les probas respective...

[LB2]

80% de chances de gagner 5 et 20% de chance de perdre 20, non ?
(jeu d'espérance nulle puisque la pièce est équilibrée)

[GaBuZoMeu]

Cela n'a pas été dit, Sylviel, et tu as sans doute l'argument simple que j'attendais. Mais je ne comprends pas ce que tu as écrit. Peux tu détailler ? Je suis curieux de voir ton argument de façon précise.

Sinon, pour la série de beagle qui accélère bien la convergence, j'ai fait des calculs basés sur la réflexion à double miroir que j'ai la flemme pour le moment d'expliciter, mais dont je donne le résultat de manière tout à fait explicite, sous forme de code :

Code: Tout sélectionner

def C(k,l) :
    if l>=0 :
        return (10*l+1)*binomial(2*k,k+5*l)/(k+5*l+1)
    elif l<0 :
        return (10*l+1)*binomial(2*k,k+5*l+1)/(k-5*l)
def Coeff(k) :
    min = (-(k+1)/5).ceil()
    max = (k/5).floor()
    return add(C(k,l) for l in range(min,max+1))

Voici grâce à ça les 20 premiers coefficients de la série (beagle en a donné 6 exacts) :
1,
1,
2,
5,
13,
34,
89,
233,
610,
1597,
4181,
10946,
28657,
75025,
196418,
514229,
1346269,
3524578,
9227465,
24157817
et la somme des 20 premiers termes de la série :
0.799916753539947
On n'est vraiment pas loin de 0.8.

[Sylviel]

Soit $X_n$ le gain au bout de n coups. Il s'agit d'une martingale dont l'incrément est borné. Soit $T$ le temps de sortie de $[-20,5]$, il s'agit d'un temps d'arrêt presque sûrement fini, donc $E[X_T] = E[X_0]=0$ par théorème d'arrêt de Doob.

Après je n'ai pas fait proprement ce genre de choses depuis un moment et il peut me manquer un argument technique...

@LB2 : je dis la même chose que toi, avec le nom du théorème qui permet de justifier que le jeu est d'espérance nulle

[LB2]

Puissant en effet ce théorème de Doob

[GaBuZoMeu]

Merci Sylviel. Je ne connaissais pas ce théorème d'arrêt de Doob (pas de la daube). J'ai jeté un coup d'oeil à sa démonstration sur la page wikipedia en anglais. Ça fait effectivement un argument rapide, mais moyennant un assez gros théorème.

Dans le cas particulier qui nous intéresse, la matrice de transition entre états (le joueur a jetons) pour (où est l'objectif en nombre de jetons que s'est fixé le joueur, il sort quand il l'atteint - de même qu'il sort quand il a 0 jeton) est la matrice de taille :



On voit assez directement que la limite de (le projecteur spectral associé à la valeur propre 1) est



est de rang 2, vérifie et .

Edit : démonstration du fait que est bien égale à la limite de . Vu qu'on a une chaîne de Markov absorbante avec deux états absorbants, est un projecteur de rang 2, donc de même rang que . Les égalités ci-dessus entraînent pour tout et donc par passage à la limite . Avec l'égalité des rangs, il vient que et ont même noyau et même image, et donc ces deux projecteurs sont égaux.

Morale : si le joueur part avec jetons, avec , alors il a chances sur de sortir avec jetons (et donc un gain de ) et chances sur de sortir avec 0 jeton (et donc une perte de . L'espérance de gain est nulle dans tous les cas.

[LB2]

Je n'ai pas fait tous les calculs, mais il me semble qu'on peut également raisonner, de façon élémentaire (sans théorème de Doob), en introduisant les v.a. J_n, nombre de jetons dont dispose le joueur au bout de n tours. On connait la loi conditionnelle de J_{n+1} sachant J_n, en utilisant les fonctions génératrices des moments, on peut en déduire l'espérance de J_n, et en déduire la probabilité de ruine du joueur et de ruine de la banque (et en prime, pour une pièce biaisée également). J'ai trouvé ce problème et sa résolution (avec une légère variation des règles) dans un livre de Jean-Louis Roque, qui le doit à Philippe Robine.

[GaBuZoMeu]

Peux-tu détailler, LB2 ? Pour le moment, ça me semble assez flou ...

[Sylviel]

Il me semblait que c'était un théorème classique, présent dans tous les cours de chaînes de Markov / martingale à temps discret - mais je peux me tromper !

En revanche je réalise que je l'ai appliqué un peu rapidement : le temps d'arrêt doit être borné pour que le théorème fonctionne. La technique consiste à prendre le minimum entre le temps d'arrêt et une constante puis de faire tendre la constante vers l'infini, ce qui ne sera possible que par domination (ici parce que X est borné).

[GaBuZoMeu]

Il me semblait que c'était un théorème classique, présent dans tous les cours de chaînes de Markov / martingale à temps discret - mais je peux me tromper !

Encore faut-il avoir suivi un tel cours, ou avoir eu à l'enseigner, ou avoir eu l'occasion de se frotter à ces choses au cours de son activité de recherche. Ce n'est pas mon cas. Par contre, je n'ai pas de problème avec les aspects matriciels des chaînes de Markov.

Sinon, pour les conditions d'application du théorème de Doob tel qu'il figure dans la page wikipedia en anglais, je vais écrire ce que j'ai compris.

1°) est le nombre de jetons de Charles après tirages (Charles jouant tout le temps pile). On a . La suite est bien une martingale (pour la filtration à laquelle tout le monde pense, les événements de sont ceux relatifs aux premiers tirages) : l'espérance conditionnelle de est bien égale à .
2°) est le premier temps où Charles arrive à 0 ou 25 jetons. C'est bien un temps d'arrêt, toujours pour cette même filtration.

Il y a une constante telle que pour tout entier naturel (on peut prendre ). C'est l'hypothèse c) du théorème dans la page mise en lien, et on peut conclure est une variable aléatoire presque sûrement bien définie et que . (En fait ici est presque sûrement fini ; je pense qu'avec les deux barrières 0 et 25, on a même l'espérance de qui est finie, mais je n'en ai pas la démonstration pour le moment.)

En clair : l'espérance de gain est nulle de chez nul.

Correct ?

On a donc deux méthodes de démonstration : une méthode vraiment probabiliste avec le théorème de Doob, une méthode reposant sur un calcul matriciel.