Markov (majorations difficiles)

[Lostounet]

Bonjour,

C'est encore moi sur les probas. J'ai quelques questions d'un devoir que je n'arrive pas du tout à faire.
Toute aide ou piste est la bienvenue.

Soit une chaîne de Markov sur E (fini) telle que sa matrice de transition P vérifie,:
Il existe r>=1, pour tout x et y dans E,

Soit .
1) (réussie) Montrer qu'il existe a dans ]0;1] telle que avec P^Y la matrice de transition de Y

Soit (o désigne un état de E)

2) Soit
Prouver que

3) En déduire que pour tout x, pour tout n,
Puis qu'il existe deux constantes C et c, telles que pour tout x et tout n,

La notation c'est pour signifier que vaut x

[Matt_01]

Comme ca j'écrirais que B(n+1) c'est le sup sur E des sommes de type sur les différents de o.
Maintenant le sup de ces telles sommes, c'est inférieur au sup sur E des sommes de type sur les différents de o, fois le sup sur des (a et b viennent de et ).
D'un côté t'as , et l'autre côté tu peux facilement le majorer par 1-a (et même 1-3a si je suis pas fou).

[Lostounet]

Comme ca j'écrirais que B(n+1) c'est le sup sur E des sommes de type sur les différents de o.
Maintenant le sup de ces telles sommes, c'est inférieur au sup sur E des sommes de type sur les différents de o, fois le sup sur des (a et b viennent de et ).
D'un côté t'as , et l'autre côté tu peux facilement le majorer par 1-a (et même 1-3a si je suis pas fou).

Salut Matt,
Merci de me sauver la vie par cette piste J'y ai passé au moins 4 jours (sur ce DM)

Malheureusement j'avoue que c'est pas encore "super évident" pour moi. Pourrais-tu détailler un petit peu plus (les mêmes arguments peut-être).

Je voudrais te demander par ailleurs: est-ce vrai que l'on a

Et si oui, pourquoi?

[Matt_01]

Je dis peut-être n'importe quoi, mais la proba qu'en partant de x et en faisant un chemin de longueurs n+1 on ne croise pas o c'est :

De là tu dis (pourquoi ?) et donc c'est inférieur à
Quand tu passes au sup t'obtiens ton inégalité.

Ben = inf (i | Y_i = o) donc en fait ce qui veut dire que .
Mais =inf( i | X_i = o) et donc ... ?

[Lostounet]

De là tu dis (pourquoi ?)

Cela est vrai car si a est plus petit que tous les coefficients de la matrice, aucun coefficient ne peut excéder 1-a (car si c'est le cas sur la même ligne il y aurait un coefficient plus petit que a...)

et donc ... ?

Ah, peut-être qu'alors par définition même de T_o^X, on a automatiquement (par propriété de l'inf !) non?

Si j'ai bien compris, du coup je vais continuer de creuser pour le reste (mais cela fait plusieurs jours que je suis dessus)... Si tu as des pistes ce serait super (pour ces constantes absolues c et C)...Il me semble que C doit dépendre de 1/r intuitivement (ou quelque chose comme ça)

[Ben314]

De là tu dis (pourquoi ?) et donc c'est inférieur à

Non, ça déconne :
Si tu as une majoration du tyle
Ce que tu en déduit, c'est que la première somme est inférieure à

en recopiant bien sûr le dans les indices de somme.

Sauf que, si on était dans un cas fini, on aurait

où est le nombre de choix possibles pour donc déjà ça marcherais pas.
Et qu'en plus, ici, rien ne dit que E est fini donc on ne peut rien écrire.

Sinon, rien que la question 1), je comprend pas comment on obtient le résultat : quand on a une série d'inégalités de la forme ???>0, pour en déduire un minorant global (non nul), il faut de sacrés hypothèses du style continuité + compacité ou des trucs du même style. C'est quoi qui fait marcher le bidule ici ?

[Lostounet]

J'ai pas trop compris pourquoi il faut recopier le x_n+1 dans les indices de somme? (après majoration brutale)

Donc ce que tu dis, c'est qu'il faut majorer en deux temps d'abord par (1 - a) mais aussi par K qui est le nombre de choix possibles pour l'état x_n+1 ? Et ça fait appel à la taille de la matrice...?

[Ben314]

J'ai pas trop compris pourquoi il faut recopier le x_n+1 dans les indices de somme?

Ca vaut combien ?
Et

[Lostounet]

il faut de sacrés hypothèses du style continuité + compacité ou des trucs du même style. C'est quoi qui fait marcher le bidule ici ?

Désolé ... mais j'ai oublié de dire que E est un espace d'états fini... (ne m'en veux pas car il y avait tellement d'objets à introduire...)

Et pour tes sommes... la deuxième vaut 3*4/2 et la première ... 3*(3*4/2) ?

Edit: tu as édité tes sommes
Pour la version edit: S1 = 5*6/2
S2 = on somme 15 ... 5 fois?

[Ben314]

Oui c'est ça.
J'ai édité je sais pas combien de fois, mais on s'en fout, le but c'était juste que tu comprenne qu'on ne "vire" pas "gratuitement" des trucs qui sont en indice d'une somme, même si les trucs n'apparaissent pas dans l'expression que l'on somme.

[Lostounet]

J'ai compris, merci...

Les majorations de Matt ne sont pas rectifiables ? C'est vraiment pas évident...

[Ben314]

Le "principe" consistant à dire qu'il faut arriver à passer de ça

à ça

c'est effectivement correct et je pense que ça doit permettre d'aboutir (*)
Mais par contre la façon dont il s'y prend en ne faisant que majorer par une constante, je ne pense pas que ça puisse marcher.

(*) A mon avis, je pense que le 1-a, il provient plutôt d'un truc plus ou moins du style
(où x' et x'' sont fixés)

[Lostounet]

Pas évident des sommer sur des coefficients etc... je note le (1 - a).

Mais si majorer simplement par des constantes ne peut pas marcher ... je ne vois pas comment faire.
Tous mes collègues ont déjà abandonné...

[Matt_01]

Ouais autant pour moi j'ai été un peu vite en besogne.
Maintenant on peut modifier un peu pour que ca marche en disant que la proba de faire une chemin de longueur n sans passer par o, c'est la proba de faire un chemin de longueur (n+1) en arrivant n'importe où, sans passer par o sur les n premiers états.
Ca veut dire que

Et en disant que chacun des P^Y(x_n,o)>a et en passant au sup sur x on obtient :

[Lostounet]

Merci Matt.

Que penses-tu pour la question 2 de la majoration
Par (1-a)^(n/r) ?

[Matt_01]

Ouep je pense que c'est bon. Mais sauf erreur il faut faire attention de ne pas écrire des trucs du style car n/r n'est pas forcément entier. Via manipulation de quelques parties entières on retombe sur ce qu'on veut de toute facon.

[Lostounet]

Oui j'ai utilisé la partie entière en premier temps puis je l'ai majorée.

Mais le problème c'est que je trouve C = 1 alors que ça peut pas être ça (sinon il l'aurait pas mis). Que faire?

[Doraki]

Moi j'aurais plutôt dit ça

P(ne pas arriver sur o en (n+1) coups | Y0 = x)
= somme pour y <> o des P(Y1 = y puis ne pas arriver sur o en n coups suivants | Y0 = x)
= somme pour y <> o des P(Y1 = y | Y0 = x) * P(ne pas arriver sur o en n coups | Y0 = y) (!!!)
<= somme pour y <> o des P(Y1=y | Y0 = x) * Bn
= Bn * P(Y1 <> o | Y0 = x)
= Bn * (1 - P(Y=o | Y0 = x))
<= Bn * (1-a)

Donc en prenant le sup, B(n+1) <= Bn * (1-a).

Enfin qu'on découpe selon Y1 plutôt que selon Yn doit pas changer grand chose.

[Lostounet]

Merci Doraki, il me semble que l'idée est d'utiliser une propriété des CM...
Et penses-tu que la constante C peut valoir 1 du coup?

[Doraki]

Ben oui mais on ne te demande pas forcément d'obtenir un truc avec C = 1.
Ni d'obtenir le meilleur c possible.
Souvent on veut juste avoir la nature de la convergence et on se fiche éperdument des constantes elles-mêmes et dans ces cas là bah ça nous dit de ne pas hésiter à faire des approximations brutales tant que le but reste atteignable (comme ici lol).

(et puis en fait je pense que tu t'es trompé si tu as fait ce que je pense parceque j'obtiens pas C=1 mais c'est pas une erreur insurmontable du tout)