Suite linéaire récurrente d'ordre 2

Alexique · October 2020

Bonjour,

je dispose d'une suite $(\pi_k)_{0 \leq k \leq N}$ vérifiant $\frac{k+1}{N}\pi_{k+1}+(1-\frac{k-1}{N})\pi_{k-1}=\pi_k$ pour tout $k \in [|0,N|]$ avec la convention $\pi_{-1}=\pi_{N+1}=0$. Comme il s'agit d'une loi invariante, on a aussi $\sum_{k=0}^N \pi_k=1$.

Je sais que je dois montrer que $\pi$ suit une $\mathcal{B}(N,\frac12)$.

1) Comment montrer que $\pi_k= \binom{N}{k}\frac{1}{2^N}$ ? Par récurrence ? Mais alors, comment initialiser ?
2) Comment trouver la formule de $\pi_k$ sans la connaitre ? Il s'agit d'une suite linéaire récurrente d'ordre 2 mais les coefficients ne sont pas constants... Je suppose que c'est faisable mais je ne connais pas la théorie...
Evitez les réponses qui trichent, par exemple : "montrer que $u_k:=\frac{\pi_k}{\binom{N}{k}}$ est constante"...

Merci

Noname42 · October 2020

Bonjour,

1. Il faut que tu aies le terme 0 et le terme 1 , et ensuite je pense qu'il faut faire une récurrence et tu montre que $P(n)$ et $P(n+1)$ vrai, implique $P(n+2) $ encore vraie.
2.Ce n'est pas une suite réccurente linéaire d'ordre 2 car les coefficients ne sont pas constant. Pour essayer de trouver la formule tu pourrais calculer les premiers termes et remarquer que cela fait $\pi_k=\begin{pmatrix}N\\k\end{pmatrix}\frac{1}{2^N}$ mais cela va être chaud, et tu risque de t'y perdre.

Alexique · October 2020

Bonjour, merci pour la réponse.

1) Je n'ai pas les termes 0 et 1. Ma suite est cependant définie de manière unique car la somme vaut 1. C'est pour ça que je demande par où je commence.

2) Oui en effet, c'est juste récurrent. Mais par analogie, je crois qu'on sait résoudre $y''+a(x)y'+b(x)y=c(x)$ si je ne dis pas de bêtises...donc les coefficients non constants complexifient la chose mais c'est faisable non ?

Noname42 · October 2020

1) j'ai essayé de démontrer l'hérédité mais j'ai dû faire une erreur de calcul quelque part et cela m'a rajouté quelque chose qu'il ne fallait pas, mais essaye de démontrer l'hérédité après on verra pour les termes 0 et 1 (je pense que le terme 0 vaut 0 car je ne sais pas si tu as fait une erreur ou quelque chose mais si tu fais un changement de variable tu te retrouves avec $\pi_0=0$.
2) Oui c'est possible mais compliqué car y a pas mal de calculs.

Si j'étais toi, je ferais le 1) car le 2) te fera faire que des erreurs et tu ne trouveras pas à la fin.

BobbyJoe · October 2020

Tu peux déclarer : $\displaystyle u_{0}=\lambda$ et alors avec les conditions initiales : $\displaystyle u_{-1}=0;\ u_{0}=\lambda$ et ta relation de récurrence, tu peux montrer (par récurrence double finie) $$\forall k\in \{-1,\ldots,N+1\},\quad u_{k}=\lambda\binom{N}{k}.
$$ Ensuite, tu peux utiliser la relation $\displaystyle \sum_{k=0}^{N}u_{k}=1$ pour trouver effectivement la valeur de $\lambda.$

bd2017 · October 2020

Bonjour
Bien entendu je connais la réponse. Mais si tu n'avais pas donné la réponse voici comment j'aurais fait.

Pour $k=0,\ldots,n$ ta suite correspond à la solution d'un système linéaire de taille $N+1$, i.e plus précisément en posant

$X= (\pi_0,\ldots,\pi_N)$ on a $AX=0,$ où $A$ est une matrice carrée de taille $N-1$, tridiagonale et en particulier la diagonale principale contient le même coef $-1$.

On est donc amener à déterminer le noyau (il n'est pas difficile de voir que le rang est $N$ donc le noyau est de dimension $1$ et visiblement la première composante est non nulle, je la choisis = à $1$).

Je commence à résoudre $\pi_0=1$, puis $\pi_1=N$ et $\pi_2=N(N-1)/2.$ Un expert devine la suite, ... on subodore que $\pi_3=C_{N} ^3$ et la récurrence est alors facile à finir.

Alexique · October 2020

@Noname42 : je sais faire l'hérédité double, ce n'est pas mon problème. Mon problème est l'initialisation.

@BobbyJoe : Ok, je n'étais pas convaincu que je pouvais "déclarer $u_0=\lambda$ mais entendu...et c'est seulement à la fin une fois la récurrence achevée qu'on calcule $\lambda=\frac{1}{2^N}$, pas avant. Car si on le fait dès le début, on doit démontrer par récurrence double que $\pi_k= \binom{k}{N}\frac{1}{2^N}$. Mais l'initialisation est infaisable car on ne sait pas que $\pi_0=\frac{1}{2^N}$ (on sait que $\pi_{-1}=0$ par contre). C'est bien ça ?

@bd2017 : comment obtiens tu $\pi_0=1$ ? Et sinon, tu devines la formule donc ça ne me satisfait pas vraiment. Ma question 2), c'est quels résultats a-t-on sur les formules explicites des suites $(u_n)_n$ de la forme $u_{n+2}+a_n u_{n+1}+b_n u_n = c_n$ ?

A la base, c'est un problème de chaine de Markov. $\pi$ est l'unique proba invariante d'une certaine chaîne $(X_n)_n$ d'espace d'états $\{0,...,N\}$. On a donc $\pi P = \pi$ où $P$ est la matrice stochastique de transition de la chaine $(X_n)_n$. Ainsi, $\pi(P-I)=0$ et en transposant $(P-I)^T\pi^T=0.$ ie $(P^T-I)\pi^T=0$. Ta matrice A est donc $A=P^T-I$ mais il te manque l'information $\sum_{k=0}^N \pi_k=1$ qui te donne un $\pi$ incorrect à un scalaire multiplicatif près.

BobbyJoe · October 2020

Tu peux également considérer le polynôme générateur de ta suite : $\displaystyle f(x)=\sum_{k=0}^{n}u_{k}x^{k}.$
Avec les conditions de bord que tu as imposées (à savoir $\displaystyle u_{-1}=0; u_{N+1}=0$), on obtient l'équation différentielle suivante satisfaite par $f$ (en multipliant la relation de récurrence par $x^{k}$ et en sommant les relations) : $$f'(x)=\frac{N}{1+x}f(x).$$
On trouve alors (compte-tenu de $f(1)=1$) : $\displaystyle f(x)=\frac{1}{2^{N}}(1+x)^{N}.$
Ainsi, il vient en développant par la formule du binôme : $$\forall k\in \{0,\ldots,N\}, u_{k}=\frac{1}{2^{N}}\binom{N}{k}.$$
Il ne reste plus qu'à faire les détails toi-même.

Alexique · October 2020

Ha merci, c'est très clair et ça résout assez joliment le problème. X:-((:D

Suite linéaire récurrente d'ordre 2

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 21