salut

je ne vois pas l'intérêt de distinguer des types de triplet

un sommet de l'hypercube a pour coordonnées un n-uplet constitué uniquement de 0 ou de 1 ...

soit (x₁, x₂, ...., x_n) les coordonnées d'un sommet S fixé

1/ quelles sont les coordonnées d'un sommet adjacent (relié par une arête) à ce sommet ?
2/ combien y en a-t-il ?
3/ comment simuler le passage de ce sommet à un sommet adjacent ?

...

Je ne comprends pas l'intérêt d'une simulation (de type Monte-Carlo) sur un problème où on peut faire un calcul exact.

Pourquoi ne pas simplement propager les probabilités d'un état à l'autre, comme tu l'as probablement fait dans le cas du cube ?

En gros tu pars de ton hypercube initial avec 1 sur la position initiale et 0 partout ailleurs.
Puis tu écris pour chaque sommet la formule de passage permettant de passer de t à t+1 en sommant toutes les contributions en probabilités, de tous sommets voisins du sommet considéré.

En quelques lignes astucieuses c'est plié (surtout en répondant au préalable aux questions indiquées par carpediem)...
Tu te retrouveras avec tous les états de probabilité successifs de l'hypercube (la somme des probabilités de tous les sommets à chaque instant restant bien sûr égale à 1).

En sommant n * p(final), tu auras le calcul de l'espérance cherchée, en espérant qu'elle veuille bien converger...

effectivement faire une simulation sur une expérience qui ne converge pas (me semble-t-il) pour estimer l'espérance semble peu raisonnable ....

C'est possible que ça converge...
Lentement, mais sûrement.

Au bout d'un moment, le cube de probabilité doit s'homogénéiser...
Et dans ce cas, la probabilité de t à t+1 sera du genre géométrique avec une raison très proche de 1 mais inférieure à 1. Donc l'espérance devrait converger (avec le "truc" de la dérivée...). Je ne sais pas si c'est "clair", mais bon ...

Pour des dimensions de cube importante, un calcul direct demandera déjà pas mal de calculs à itérer un grand nombre de fois...

Alors pour une simulation, autant dire que c'est mal engagé...
Et puis surtout c'est mal venu de traiter par simulation un problème qu'on peut calculer exactement...

Je m'aperçois que j'ai imaginé pire qu'un cube : un truc avec plusieurs sommets par arête...
Donc les dimensions seront peut-être moins explosives que je ne l'ai suggéré.

N'en reste pas moins qu'utiliser du Monte-Carlo sur un problème directement calculable... c'est être un peu joueur ...

il me semble que dans le meilleur des cas pour passer du sommet (0, ..., 0) au sommet (1, ..., 1) il faut au minimum n étapes .....

pour n = 3 tu trouves une approximation de 10 > 3² ... si par hasard cela se généralise ... va falloir faire chauffer les puces pour pouvoir se servir des résultats d'une simulation ....

effectivement une étude théorique serait préférable ... même si cela reste un excellent exercice d'algorithmique ....

Merci pour ces reponses si rapides ! Je nai malheureusement pas le temps ce soir de my pencher, je tacherai dapprofondir les resultats ou pistes que vous mavez donnees.
Mais sinon, jai fait une espece de graphe avec le nombre de sommets et les probabilites de passer de lun a lautre en dimension n.
Ce que je desirerais en fait, ce serait de connaitre cette esperance en dimension quelconque, pensez vous quil existe une formule ? Enfin, je suppose, car un exo non corrigé demande de verifier le resultat de lesperance en dimension 47...
Merci de vos reponses.

Tu peux schématiquement traiter l'espérance à trois niveaux :
1. Simulation stochastique.
2. Calcul numérique direct approché (parce qu'en temps fini Tmax).
3. Calcul complet, avec passage à la limite (temps infini).

1 et 2 sont très similaires dans la programmation.
A la limite, la 1ère peut être rigolote à titre "expérimentale".
Mais la 2 est indispensable pour une valeur fiable.
Et elle est en fait plus simple que la simulation (qui requiert la répétition d'expériences et la synthèse des résultats).

Le calcul complet (3) est balaise à mon avis.
Il revient à élever une matrice à la puissance n...

Pour les 3 méthodes, la formule de passage est assez simple :



V(X) = voisinage direct de X : Sommet distant de plus ou moins un vecteur unitaire...
... c'est à dire requérant un déplacement avec un 1 et n-1 zéros

Le vecteur P(t=0) vaut 1 pour la position initiale X=(0,0,0,...0) et 0 pour toutes les autres positions.
Les vecteurs P(t) se calculent de proche en proche.

NB: adapter la formule de passage pour qu'une fois en position finale, on y reste...

tout simplement les n voisins de s'obtiennent en remplaçant l'une des coordonnées par il me semble ... ou non ...

Oui.
Et c'est exactement la même chose qu'effectuer un "déplacement" de 1 sur une des coordonnées.
M' = M + U,   avec U vecteur unitaire.  
... Comme ça on sait à la fois ce qu'il faut faire... et pourquoi on le fait .

Bonsoir,
j'ai fait un calcul, un peu rapide, mais j'ai l'impression qu'il sera difficile de faire une simulation pour n=47.
Pour n=10 l'espérance, sauf erreur de ma part, est supérieure à 1186 et j'ai l'impression qu'elle est plus grande que 2ⁿ pour tout n.

Sinon j'ai calculé directement les espérances, mais avec des sommes que je n'ai pas simplifiées.

Le tout sans aucune garantie, car griffonné en regardant le tournoi des 6 nations.
J'y retourne.

ha ces français qui jouent sans génie ... je bous !!!!  

Car le génie est «sans bouillir».
Ceci étant ce n'est pas le lieu pour une discussion de ce type.

Je viens de regarder pour n=4, en utilisant les puissances de matrices, mes résultats ont l'air cohérents.

J'ai donc la nette impression que palind0 ne pourra pas vérifier le résultat pour n=47 avec une simulation.

Pour recoupement voici ce que je trouve :

Pour n=2   E(T) = 4
Pour n=3   E(T) = 8
Pour n=4   E(T) = 64/3

Pour n=3 je trouve E(T)=10.
Sinon mes résultats sont identiques.
Pour n=5, je trouve E(T)=128/3.

Oups, erreur de retranscription : c'est bel et bien 10 que je trouve aussi pour n=3.

- On prend un tableau de n cases.
- On initialise les n cases à zéro.

Repeat
- On prend une case au hasard
- On y met "1" si elle vaut "0" et "0" si elle vaut 1
- Incrémentation d'un compteur
Until toutes les cases valent "1"

- On lit le compteur.

C'est ça qu'il faut faire ?

En gros oui, si on veut faire une simulation.
Après, il y a quelques problèmes pratiques.

C'est pour ça que je demandais si c'était ce qu'il faut faire. Au delà de la dimension 3, je ne visualise plus. Comment le passage d'un sommet à un autre se traduit-il dans les coordonnées en dimension n ? J'ai pensé que cela se traduisait par le passage de l'une des n coordonnées (cases) d'un état "1" à un état "0" ou inversement. Le procédé se fait autrement ? Comment ?

allez en dimension 10 ::

quels sont les voisins de (0, 0, 0, 0, 1, 0, 0, 0, 0, 0) ?

en dimension 3 quels sont les voisins de (0, 0, 1) ?

(1;0;1) , (0;1;1) , (0;0;0). En dimension 10, comme je viens de l'écrire, je ne sais pas. Mais si ça fonctionne comme en dimension 3, je ne vois pas où est l'erreur dans mon algorithme.

(0, 0, 0, 0, 1, 0, 0, 0, 0, 0)

(0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
(1, 0, 0, 0, 1, 0, 0, 0, 0, 0)
(0, 1, 0, 0, 1, 0, 0, 0, 0, 0)
(0, 0, 1, 0, 1, 0, 0, 0, 0, 0)
(0, 0, 0, 1, 1, 0, 0, 0, 0, 0)
(0, 0, 0, 0, 1, 1, 0, 0, 0, 0)
(0, 0, 0, 0, 1, 0, 1, 0, 0, 0)
(0, 0, 0, 0, 1, 0, 0, 1, 0, 0)
(0, 0, 0, 0, 1, 0, 0, 0, 1, 0)
(0, 0, 0, 0, 1, 0, 0, 0, 0, 1)

Oui, c'est donc bien comme ça que je le voyais. Donc, en quoi mon algorithme ne convient-il pas ?

Finalement, l'algorithme STOCHASTIQUE peut s'avérer très intéressant.
Il est très possible qu'il fournisse une valeur approchée de E(T) plus rapidement que l'algorithme par PROBABILITES EXACTES (tronqué à Tmax), parce qu'il est bien plus rapide sur chaque itération.

En revanche, il peinera à fournir une valeur proche.

ha je comprends mieux ... je me demandais ce que tu ne comprenais pas ...

par contre comme je l'ai dit plus haut et verdurin a proposé encore mieux, si l'espérance est supérieure à 2ⁿ alors pour en avoir une "bonne" approximation il va falloir proposer un T_MAX assez conséquent si n = 47 par exemple .... pour pouvoir faire une simulation qui conduise à un résultat acceptable ....

Pour n=47 je trouve E(T)= 42371436350940931526480650829824 / 294362129962575675 1.43943231952e+14.

Pour le calcul j'ai considéré les ensembles de sommets pour un sommet étant dans quand il a k composantes égales à 1.
Quand on est sur un sommet de toutes les arêtes conduisent soit à un sommet dans (avec une probabilité de ), soit à un sommet dans (avec une probabilité de ).
Ensuite on peut trouver une relation de récurrence pour déterminer l'espérance du nombre de mouvements permettant de passer de à .

Après il reste à faire faire l'addition par un machine.

Dans tous les cas que j'ai regardé il faut, en moyenne, mouvements pour passer de à , c'est à dire pour arriver au sommet final à partir d'un sommet voisin.

Bon, j'ai tenté de faire un algo en turbo pascal. Pour n=3, je retrouve bien E(T) = 10 et pour n=5 E(T) = 42.66 (mais il faut faire 1 000 000 de simulation pour arriver à ce résultat de façon stable).
Pour n=35, il faut jusqu'à 9 minutes à la machine pour faire UNE simulation. J'ai trouvé une valeur de 1.47*10^10 itérations. Pour n=47, je suppose qu'il faudrait au moins 2 jours pour parvenir au résultat d'UNE simulation.

Des premiers résultats que j'ai obtenus, E(T) semble suivre une loi exponentielle en fonction de n.

Pour n=47, je trouve alors une estimation pour E(T) = 9.8*10^13 ce qui est proche du résultat de Verdurin.

Estimation réalisée sur Excel, je précise.

verdurin, ton algorithme de calcul m'intéresse. (celui qui t'a mené au résultat de la dimension 47)

Comme un idiot, j'ai laissé les papiers qui traitent du sujet dans mon appartement, je ne pourrais les consulter qu'à partir de demain. C'est parfaitement de cette méthode dont il était question sur le papier pour calculer les espérances pour d quelconque, je me souviens l'avoir lu, mais ne pas l'avoir compris... Car on nous dit de démontrer des formules à la suite (raisonnement assez compliqué) qui mènent à un résultat, qui permet de calculer donc l'espérance pour d quelconque. Je vais tâcher de mettre demain soir les différentes démonstrations qui mènent à la formule (en fait ça se fait en 3 étapes).

Peux-tu préciser la phrase " Ensuite on peut trouver une relation de récurrence pour déterminer l'espérance du nombre de mouvements permettant de passer de S_k à S_k+1. " ?

Il s'agit de calculer l'espérance du nombre de mouvements pour arriver en en partant de .

On a de façon évidente : en partant de (0..0) on arrive forcément sur un sommet ayant une seule coordonnée égale à 1, donc dans .

Ensuite, on peut exprimer en fonction de (ainsi que k et n).
Après on peut calculer numériquement les et donner l'espérance du nombre de mouvements pour aller de (0...0) à (1...1) en faisant la somme de à des .

Il est peut-être possible de donner une formule pour le résultat, mais je n'ai rien vu (et pas beaucoup cherché).

En fait j'ai retrouvé la feuille. Voilà ce qui y est exposé, et qui permet donc de trouver la formule générale :

1. On considère la marche aléatoire sur un carré, on note T la matrice de transition.
Montrer que la probabilité que, partant du sommet a, le marcheur ne passe pas par b a avant le temps N vaut :
P_a[m_b > N] = (T*^N)_ca (la somme s'effectue sur les c)
où T* est la matrice T privée de sa b ième ligne et de sa b ième colonne.
En déduire que, partant d'un sommet du carré, le temps moyen <m> nécessaire pour atteindre le sommet opposé vaut exactement 4.

Bon, rien que cette formule à démontrer me pose déjà problème, j'ai du mal à comprendre ne serait-ce que le terme (T*^N)_ca ...

Ensuite :

2. On généralise l'exercice précédent en dimension d en réduisant le problème à une marche sur des graphes.
Les noeuds des graphes sont numérotés de 0 à d, le noeud k désignant, dans le d cube correspondant, la collection S_k des sommets ayant k coordonnées égales à  1 et d-k coordonnées nulles ( |S_k| = k parmi d). Chaque sommet de S_k est relié à k sommets de S_k-1 et à d-k sommets de S_k+1. Par conséquent, les probabilités de transition rapportées sur le graphe linéaire comportant d+1 noeuds valent :

(T_d)_k'k = p(k->k') = (k/d)_k',k-1 + [(d-k)/d]_k',k+1.

Là encore, je ne comprends pas la formule ni les notations... Si quelqu'un y est habitué je veux bien qu'il m'explique...

3. La question 1 demandait de calculer la moyenne du premier temps de passage au noeud d en partant du noeud 0, que nous notons <m_d>₀, mais on peut aussi bien s'intéresser à <m_d>_k (départ du noeud k < d).
Pour calculer ces quantités, on utilisera la formule de la question 1, ou la relation de récurrence suivante (adaptée à la situation présente) :

P_k[m_d=N] = (T_d)_k'kP_k'[m_d= N-1] (la somme s'effectue sur k')

avec P_k[m_d=0]=_k,d et P_d[m_d=N]=_N,0

et on en tirera ensuite le système linéaire :

<m_d>_k=1+(T_d)_k'k<m_d>_k' (somme sur k'<d) avec k<d.

4. Vérifier qu'avec d=4,5,6,7 on a <m_d>₀= (64/3), (128/3), (416/5), (2416/15).
Etablir finalement une formule aussi générale que possible pour <m_d>_k en termes de k<d et d. Montrer par exemple que <m_d>_d-1 = 2^d-1


Voilà donc le problème un peu éclairci, mais pour ma part ça ne l'est pas puisque je ne comprends pas la plupart des formules exposées...

verdurin, les quelques formules exposées sont les mêmes que tu as mises en oeuvre tout à l'heure. C'est rassurant...

Excuse-moi d'être aussi peu à l'aise dans les probabilités, je vais tenter d'appliquer ta méthode, mais quelle est la formule à appliquer pour calculer l'espérance ?
Je vais déjà regarder pour d=2,3,4 et essayer de trouver une formule de récurrence.

Dans le carré, l'espérance a₀ pour passer de S₀ à S₁ est de 1, mais quelle est l'espérance a₁ de passer de S₁ à S₂ ?

Sans aucune garantie, car je ne connais pas ces notations.

Je pense que (T*^N)_ca désigne la somme de la colonne correspondant au point a dans la matrice T* élevée à la puissance N.
En tous cas ça donne bien la probabilité cherchée.

(T_d)_k'k = p(k->k') = (k/d)_k',k-1 + [(d-k)/d]_k',k+1 dit que la probabilité de transition entre S_k et S_k' vaut
     k/d si k'= k-1
     (d-k)/d si k'=k+1
     0 sinon
le est le symbole de Kronecker (voir )
ce qui me semble une façon très pédante de s'exprimer.

Sur ce, je vais dormir.
En espérant t'avoir au moins un peu aidé.
À demain, peut-être.

Pendant que j'y pense je rajoute un résultat utile, que tu ne connais peut-être pas :
Soit   une variable aléatoire à valeurs dans




En ce qui concerne la récurrence, je te donnes mon calcul.

Je note l'espérance de la variable aléatoire qui donne le nombre de mouvements pour aboutir à en partant de , la probabilité de la transition et la probabilité de la transition


par linéarité de l'espérance.

Il en découle immédiatement

Bonjour,
Je trouve ce problème vraiment intéressant.
D'abord, petit commentaire perso, l'expression "valeur exacte" m'étonne toujours, sauf s'il s'agit de nombre entiers.

Je me suis amusé à "construire" un hypercube. C'est pas vraiment facile, mais c'est intéressant. Chaque sommet a un numéro et je décris le graphe. A mon avis cela ferait un bel exercice d'informatique.

A partir de la dimension 16, ma machine trouve que c'est suffisant.
L'évaluation pour 47, je trouve 1.080 10^14.

La méthode de Nombrilist est vraiment astucieuse, elle est plus rapide que la mienne et j'ai pu aller jusqu'à la dimension 20.
L'évaluation pour 47, je trouve 1.3085 10^14.

Concernant le nombre de simulations et la méthode de Monté-Carlo en général.
A mon avis, 1000 est suffisant pour obtenir une valeur satisfaisante. C'est la limite que j'ai adoptée. Le principe de la méthode est que l'on converge vite, d'où son intérêt.

Enfin, pour l'estimation à la dimension 47, c'est une très bonne application des méthodes de régression. Dans les deux cas, le coefficient de régression R² est 0.999, ce qui autorise à extrapoler.

Bonsoir,

Je confirme le résultat donné par Verdurin:
Pour n=47, .

Il existe des formules (mais avec un sigma) pour :


Il y a quelques informations avec la suite A3149:

Il existe même un développement asymptotique remarquable à tout ordre p (quand n tend vers l'infini):

où désigne le nombre de classements de k personnes en admettant des ex-aequos, suite A670: (1,1,3,13,75,541,...) .

Désolé d'être l'empêcheur de tourner en rond, mais à part l'intérêt intellectuel de l'exercice, quel peut être l'intérêt d'un résultat numérique "exact" ?
De toute façon, bien malin celui qui pourra vérifier réellement le résultat !
Petit ajout, dans le monde réel, un résultat à 5 chiffres significatifs, c'est déjà pas mal.

@ Dlzlogic
C'est un exercice de math, pas de physique.
Et, pour n=47, quand tu donnes 1.3085 10^14, il n'y a pas 5 chiffres significatifs, mais un seul.

@ Verdurin
Apparemment, le demandeur est dans une école d'ingénieur. Donc, il semble que toutes les études sont centrées sur les notions du monde réel.
Cela n'empêche pas de faire des exercices dans un monde théoriques, les hypercubes, fort intéressants par ailleurs, mais la question posée était très précise, trouver un algorithme qui vérifie ses calculs.
La solution proposée par Nombriliste est tout à fait intéressante, et à l'évidence, cela constitue la meilleure réponse, bien qu'elle soit un peu difficile à comprendre.
Le nombre défini par 1.3085 10^'n'importe quoi' a 5 chiffres significatifs, c'est la définition des chiffres significatifs, on appelle ça aussi "mantisse".
C'est un peu dommage que la discussion ne s'oriente pas plutôt sur la méthode de Nombriliste, de Monté-Carlo, des régressions, c'est à dire de choses plus positives, donc plus intéressantes.    

@ LeDino

Bonsoir verdurin ,

J'avoue que j'ai du mal à comprendre une intervention aussi stérile que peu à propos.

Si Dlzogic a des trucs intéressants à dire qu'il les dise et chacun le lira avec intérêt.
Mais là je ne comprends pas ce besoin de diriger l'échange.
Surtout avec une contribution aussi maigre et après un tel niveau de réponse des participants antérieurs.

Et le pire c'est qu'il se revendique de palind0... qui a pourtant clairement exprimé son intérêt pour les pistes que tu lui as ouvertes.

C'est totalement incompréhensible.
Et je n'aime pas ne pas comprendre ...

Ma réponse est évidemment l'une des moins bonnes. Elle n'est que bricolée. La meilleure réponse est celle qui donne le résultat vrai. De toute façon, je n'avais pas le niveau en maths pour trouver ce résultat, mais l'approche algorithmique m'a plu, donc je me suis permis. Peut-être qu'en programmant avec quelque chose de plus puissant que TP, j'aurais pu aller un peu plus loin que n=35 en 9 minutes ? Je ne sais même pas ça.

Bonjour,
Je n'ai pas l'intention d'envenimer le débat.

@ Verdurin : je me disais bien que je t'avais déjà croisé, mais je n'ai pas situé où. Par exemple, est-ce toi qui a introduit dans une discussion un générateur nommé GenRand, ou au contraire, as-tu répondu à un calcul d'une chaîne devant s'écarter d'un axe par force centrifuge ? Peux-tu me donner un indice.  

@ LeDino,
Pour en être sûr, j'ai relu l'ensemble des réponses, y compris les tiennes.
Je ne suis pas intervenu avant d'avoir terminé mes simulations.
Mais avoue que ceci