Discussion :

[yogitetradim]

Bonjour à tous,

j'espère ne pas poser une question trop idiote mais je galère pas mal depuis quelques jours sur un problème sans doute simple, malheureusement Google et moi n'arrivons pas à nous comprendre sur ce pb (je manque sans doute de bases et de formalisme mathématique) , aussi plutôt que de m'acharner dans des voies qui ne mènent nulle part je me tourne vers vous.

Le problème est le suivant :
je voudrais échantilloner un n-uplet de fréquences f_{i} vérifiant :
\sum_{i=1}^{n} f_{i}^{2} = H (H = 0.8 par exemple) [1]
et
\sum_{i=1}^{n} f_{i}=1 [2]
Avec f_{i} appartient à ]0;1[

pour le cas ou n=2, je n'avais pas de problèmes.
Mais pour le cas ou n >2 je ne vois pas comment procéder (ou plutôt j'ai essayé de travailler récursivement en tirant des valeurs de f_{i} dans un intervalle qui permettait de ne pas dépasser H dans [1] et la valeur 1 dans [2]...mais j'ai sans doute des bourdes dans mon calcul de bornes)

Le n-uplet peut ne pas être unique (je réalise des simulations et donc si différents n-uplets sont tirés ça ne pose pas de problème, c'est même préfèrable)

Auriez-vous des pistes svp ? Par avance merci.

[FrancisSourd]

Tu as une solution (f,f,...,f,1-(n-1)f)
avec
f= 1-sqrt(1-n(1-H)/(n-1))/n si H ≥ 1/n (ce qui as l'air d'être le cas)

Il y a effectivement un continuum de solution. Tu peux regarder du côté des systèmes quadratiques et des systèmes polynomiaux en général (je crois que MAPLE les résoud bien de manière formelle).

D'une manière numérique, tu peux regarder la minimisation de la fonction de degré 4
(H- \sum (f_i)^2)^2 sous les contraintes linéaires \sum f_i = 1 et 0 ≤ f_i ≤ 1. Cela peut se faire par la méthode de Newton (logiciel solvopt par exemple). Le résultat de la minimisation sera toujours 0 mais, en faisant la recherche à partir de différents points de départ, tu trouveras différentes solutions optimales (donc satisfaisant tes contraintes).

[Nemerle]

C'est rigolo... c'est l'intersection de la sphère de centre O et de rayon sqrt(H) avec l'hypercube de sommets les (0,...,0,1,0,...,0). Tu peux jeter un coup d'oeil aux résultats en 3D (pour généraliser en dimension n) de Monge en géométrie descriptive (en faisant ça en 2de il y a 40 ans!), ou bien simplement calculer les intersections de la sphère avec les hyperplans définis par chacun des cotés sous ta contrainte de l'hypercube (ex pour n=3: http://www.accromaths.fr/fiches/ficheG6.pdf)

[FrancisSourd]

Il me semble qu'il faut aussi considérer l'intersection avec le plan P d'équation
f1+f2+...+fn=1.

L'intersection de ce plan et de la sphère de rayon sqrt(H). Donne une sphère (de dimension n-2) centrée en C=(1/n,.....,1/n) et de rayon sqrt(H-1/n).

Pour trouver un point sur cette sphère, tu prends un point X dans le plan P.
Tu obtiens ton point sur la sphère en faisant C + sqrt(H-1/n) CX / |CX|
où |CX| représente la norme du vecteur CX.

A priori, le point obtenu n'est pas forcément dans le cube unité. Si cela ne convient pas, on peut essayer avec un nouveau point X pris au hasard... Jusqu'à obtenir un point satisfaisant (c'est du Monte-Carlo...)

Pour être sûr d'avoir un point dans la sphère unité tu prends X=(0,..,0,1,0,..,0).
ou alors X=(eps1,eps2,... eps{i-1},1-\sum_j eps{j], eps{i+1},....,eps{n})
en s'assurant que |CX| ≥ sqrt(H-1/n). (donc prendre des "petits" eps{i}!) L'inconvénient, c'est que l'échantillonage est assez biaisé.

[pseudocode]

hypercube de sommets les (0,...,0,1,0,...,0).

le plan P d'équation f1+f2+...+fn=1

Ca serait pas un peu la meme chose ?

[FrancisSourd]

Ca serait pas un peu la meme chose ?

C'est le mot hypercube qui m'a fait pensé à l'hypercube unité. Effectivement, si on parle du polyèdre de sommets les (0,...,0,1,0,...,0), c'est bien la même chose! (ce polyèdre n'est pas un hypercube).

[pseudocode]

C'est le mot hypercube qui m'a fait pensé à l'hypercube unité. Effectivement, si on parle du polyèdre de sommets les (0,...,0,1,0,...,0), c'est bien la même chose! (ce polyèdre n'est pas un hypercube).

une sorte d'hyperplan...

[yogitetradim]

Merci beaucoup à tous,

en fait, je me suis trouvé en face du problème cité par Francis

donc prendre des "petits" eps{i}!) L'inconvénient, c'est que l'échantillonage est assez biaisé.

Du coup, j'ai eu un doute sur mes résultats, pensant que quelque chose clochait.
Encore merci à vos tous.