bonsoir

on veut donc n-4 bits avec jamais trois 1 de suite, puis 4 bits "0111"
je ne saurais aller plus loin pour le moment :D

En partant de la décomposition de Zormuche.
La probabilité de la partie droite est de 2/3*(1/3)^3 = 2/81.
Il nous reste donc juste à calculer la probabilité de la partie gauche et la multiplier par ce facteur.

On a 4 états : 0, 1 et 11 désigne les états ou on a 0, 1 et 2 '1' en bout de chaine. 111 désigne l'état ou on a vu au moins une fois 3 '1' d'affilée.

On a la récurrence suivante:





En notation matricielle:



La probabilité recherchée est celle de l'union des états 0,1 et 11 pour n-4 caractères multipliée par 2/81. On a donc comme probabilité finale:

Bonjour,

il n'y a pas de formule explicite pour la probabilité demandée mais seulement une relation de récurrence d'ordre 3. Par exemple pour la probabilité vaut .

 Cliquez pour afficher

Si est la probabilité demandée on a .

Pour , en tenant compte des 3 débuts possibles , on a la relation de récurrence .

On peut aussi écrire avec et .
En commençant à c'est la suite A077835 de l'OEIS .

Il n'y a pas de formule explicite mais pour n grand ( >> 15), Q(n) tend vers .
Avec a solution réelle de



et

Il est plus correct d'écrire : Q(n) est équivalent à quand n tend vers l'infini.

D'accord mais elle le fait très vite. À partir de Q(16) on dépasse les 8 décimales de précision.

Je suis d'accord que est une très bonne valeur approchée de .
Ce qui n'est pas correct c'est la phrase " Q(n) tend vers " car une suite ne peut pas tendre vers quelque chose qui dépend de .

Bonjour à tous.

On peut donner une formulation plus précise de l'excellente approximation de LittleFox de la manière suivante:

soit l'unique racine réelle du polynôme   (avec les notations de LittleFox,   )

alors         ,   où   est l'entier le plus proche de    
                                                                                                    (avec les notations de LittleFox  )

@perroquet
Comment as-tu calculé le b? Je n'avais qu'une approximation numérique en calculant une centaine de Q(n).

@perroquet
Ta formule donne la bonne réponse même pour les premiers termes Q(n) avec 0 n 3. Je les pensais dur à approximer.

Je suis impressionné

@Littlefox:

En fait, je n'aurais jamais entrepris ces calculs si je n'avais pas lu tes messages sur la question.

Voici quelques indications.

Factorisation du polynôme
On a déjà écrit que ce polynôme admet une unique racine réelle avec . On a:


Calcul du coefficient :
Notons et les 2 racines non réelles de .

On sait que est défini par la relation de récurrence   et par ses premiers termes et .

On en déduit qu'il existe trois constantes telles que:
On détermine grâce aux valeurs de :
              
        
        
Sachant que sont racines du polynôme , on effectue et on obtient:
     donc    
                                                                  (sachant que   )

Je n'ai pas eu le courage de calculer explicitement et .

Qualité de l'approximation de :
On remarque que .
On en déduit que est de module strictement inférieur à 1.
Comme      , on en déduit qu'à partir d'un certain rang  ,   et donc que est l'entier le plus proche de .
Mais j'ai affirmé que ce résultat était vrai pour tout de . En fait, on peut déterminer une valeur de à partir d'une approximation de et ; et ensuite, on peut vérifier le résultat pour . Je dois avouer que je n'ai pas fait ces calculs ...

Impressionnant
De mon côté, tout part de la relation de récurrence que jandri a trouvée. Même si j'ai pu la vérifier avec ma matrice, je ne l'aurais pas trouvée si facilement.

Peut-on dire que pour toute relation de récurrence



on a une solution de la forme



?

Oui si le polynôme    admet racines distinctes 2 à 2.
Si les racines de ce polynôme ne sont pas distinctes 2 à 2, notons les racines (distinctes 2 à 2) d'ordres de multiplicité . Dans ce cas, les solutions sont de la forme: