Plus près c'est mieux ... ou pas !

[MClerc]

Soit une fonction numérique f définie sur E=[0,1] (pour simplifier).

On considère l'ensemble W des triplets (x1,x2,x3) de ExExE tels que :
1) f(x1) <f(x2) < f(x3)
2) abs(x1-x2) < abs(x1-x3)

Conditions que l'on peut résumer par « Plus près c'est mieux ! » (au sens d'une minimisation).

Si l'on tire t=(x1,x2,x3) au hasard (distribution uniforme sur [0,1] pour chacun), quelle est la probabilité p que t appartienne à W ?

Il est facile de voir que
- si f est strictement monotone, p=1;
- si f est constante, p=0;
- plus généralement, avec des plateaux, p peut prendre n'importe quelle valeur sur [0, 1[;
- même pour des fonctions « simples » sans plateau (comme (x-a)^2), p peut également être strictement inférieure à 1, mais apparemment toujours au moins égale à 0.5.

D'où la conjecture :
Si f est continue, p ne peut être inférieure à 0.5 que s'il existe au moins un plateau.

Merci d'avance pour toute idée permettant de prouver cette conjecture (ou de prouver qu'elle est fausse !)

[samoufar]

Bonjour,

Les triplets tiennent-ils compte de l'ordre dans lequel viennent les trois éléments ? Parce que si oui, alors en prenant le triplet ne vérifie pas 1) donc n'appartient pas à , et donc (même si est strictement monotone).

[MClerc]

Désolé, ma formulation est en effet incorrecte.
En fait :
- on tire trois points au hasard
- on les ordonne d'après les valeurs de f en ces points, de façon à avoir trois nombres x1, x2, x3 tels que f(x1)<=f(x2)<=f(x3)

Par exemple, si l'on tire (0, 1, 1/2), avec f(x)=x, on considère en fait le triplet (0, 1/2, 1).

[Ben314]

Salut,
L'énoncé me semble toujours ambigüe :

De ce que j'en comprend, pour x1,x2,x3 dans [0,1], on écrit que f(xi)<=f(xj)<=f(xk) pour une certaine permutation (i,j,k) de (1,2,3) puis on dit que le triplet (x1,x2,x3) est "correct" lorsque |xi-xj|<|xi-xk|.

Sauf que le problème, c'est que (surtout si f admet "des plateaux comme tu dit), il risque de ne pas y avoir unicité de la permutation (i,j,k).
Si f(x1)=f(x2)<f(x3), on peut écrire f(x1)<=f(x2)<=f(x3) qui conduit à regarder s'il est vrai ou pas que |x1-x2|<|x1-x3| (a) mais on pourrait aussi écrire que f(x2)<=f(x1)<=f(x3) qui conduit à regarder s'il est vrai ou pas que |x2-x1|<|x2-x3| (b).
Si une et une seule des deux inégalités (a) , (b) est vérifiée, le triplet (x1,x2,x3) est-il considéré comme "correct" ?

[MClerc]

En fait, si je regarde mon petit programme Matlab de simulation (cf. ci-dessous), le triplet n'est considéré comme correct que si l'on a
f(x2) < f(x3) ( x2 est meilleur que x3)
abs(x1-x2) < abs(x1-x3) (x2 est plus près de x1 que x3)

(contrairement à ce que j'avais écrit, on n'a pas besoin de f(x1)<f(x2)).

J'ai un programme plus complet qui permet des simulations pour de nombreuses fonctions de diverses dimensions. Comme signalé, je trouve que s'il n'y a pas de plateau, on a p>0,5.
Mais ce n'est qu'une conjecture expérimentale.

--------
function nisb(nbSample)
nisb=0; % Number of times "nearer is better"

% Generates and examines nbSample sets of three points
for n=1:nbSample
x=rand(3,1);

for k=1:3 % Evaluates
%f(k)=x(k);
%f(k)=1;
f(k)=(x(k)-0.5)^2;
end

% Sorts
[f, Ind]=sort(f);
x=x(Ind,:); % We have f(1)<=f(2)<=f(3)

% Distances
dist12=pdist([x(1,:);x(2,:)]);
dist13=pdist([x(1,:);x(3,:)]);

if f(2)<f(3) && dist12<dist13 % x2 is strictly better, and strictly nearer
nisb=nisb+1;
end
end

p=nisb/nbSample;
fprintf('\n p = %f',p);
end

[Ben314]

Oui, mais ça répond en rien à la question :
Quel est l'algorithme utilisé par Mathlab pour trier les f(xi) ? [ou, si tu préfère, que fait-il en cas d'homonymies ?]

Parce que le nombre de point "corrects" qu'il va trouver dépend clairement de la façon dont il trie le homonymes (dans le cas où la fonction est constante sur des intervalles, bien sûr, sinon ce cas est de mesure nulle)

[MClerc]

J'ai fait des tests. Apparemment, Matlab travaille « de gauche à droite » . Si les trois valeurs sont
(0.3 0.1 0.1)
les rangs donnés par le tri sont (2 3 1). Et, bien sûr, on a x1=0.1, x2=0.1, x3=0.3.