Choisir parmi 100 prétendants

freddy · 05-07-2009 21:58:29

Hi,

je viens de trouver la source des pbs de mon copain. Le pb ci dessous résume bien la problématique du temps d'arrêt optimal.

Dans des temps très reculés, il était inconcevable qu'une jeune femme reste célibataire au delà de 25 ans.

Au voisinage de la Sainte Catherine, le 25 novembre, tous les villageois s'organisaient pour soumettre à la jeune fille concernée de beaux gars (pas plus de 30 ans), célibataires et heureux de convoler en justes noces avec la jeune femme.

La cérémonie de choix se déroulait sous huis-clos, en présence de deux anciens pour veiller à la bonne régularité de la procédure. Dans une grande grange aménagée, les jeunes hommes passaient l'un après l'autre devant la jeune femme pour être auditionnés, à quinze pieds d'elle.

La jeune fille devait soit retenir le candidat en fin d'audition, soit auditionner le suivant. Dans ce cas, elle ne pouvait pas choisir parmi ceux déjà entendus. Si elle n'avait point trouvé, elle devait épouser le dernier candidat.

Quel était le bon moment pour s'arrêter ?

thadrien · 05-07-2009 22:24:19

A mon avis, cela dépend de si la jeune fille concernée connait ou non le nombre total de prétendants.

Ensuite, il faudrait quantifier les qualités et les défauts des candidats pour faire un bilan gain/pertes. Je serai tenté d'attribuer à chaque candidat une note comprise entre -1 (candidat vraiment mauvais) et 1 (candidat excellent). Ensuite, je tenterai un calcul en partant d'une distribution gaussienne.

freddy · 06-07-2009 08:31:27

Bonjour,

elle sait qu'ils sont au nombre de 100, elle ne les connait pas par avance, elle n'a pas le temps de leur faire faire un check-up complet.

@+

thadrien · 06-07-2009 10:25:56

Autant pour moi, je n'avais pas bien lu le titre pour le nombre.

Soit n le nombre de maris potentiels. Ici, n = 100.
Soient X1, ..., Xn les n variables aléatoires indépendantes représentant la qualité apparente de chacun des maris. On suppose que ces variables suivent des lois normales de moyenne [tex]\mu[/tex] et de variance [tex]\sigma[/tex].

On suppose que la mariée à déjà vu p maris. Soit X la variable aléatoire correspondant à la qualité que la mariée peut espérer obtenir si elle attend.

[tex]X = \max(X_{p+1}, ..., X_n)[/tex]

Donc [tex]p(X \leq t) = p(X_{p+1} \leq t) \times ... \times p(X_{n} \leq t) = \Phi(\frac{t-\mu}{\sigma})^{n-p}[/tex], avec [tex]\Phi[/tex] la fonction de répartition de la loi normale centrée réduite.

La mariée s'arrête donc quand [tex]X_p \geq \Phi(\frac{X_p-\mu}{\sigma})^{n-p}[/tex]. On suppose bien sûr que la mariée dispose d'une calculatrice ou, à défaut, d'une règle à calcul et d'une table de valeurs de la fonction [tex]\Phi[/tex].

Dernière modification par thadrien (06-07-2009 11:29:29)

freddy · 06-07-2009 14:20:38

Salut thadrien,

deux hypothèses (loi normale + table de la loi normale) pour résoudre de manière générale ce problème de choix, c'est un peu trop, non ?

Essaie plus simple !

Par exemple, peut elle faire mieux que d'épouser le premier qui lui est présenté ? ou bien le second ? ou bien attendre le dernier ?

Quant aux qualités vivisbles et invisibles de l'individu, je pense qu'il faudrait construire des modèles dans des espaces de Hilbert pour répliquer l'infinie subtilité de nos compagnes, non ? ;-)

+

freddy · 17-07-2009 16:57:04

Bonjour,

on sait que les mathématiciens aiment bien ramener un problème à un autre dont l'accessibilité est plus simple.

En l'occurrence, on va dire que ce problème est "isomorphe" au problème suivant : j'ai devant moi cent enveloppes contenant chacune un nombre entier. Je peux ouvrir une après l'autre chacune de ces enveloppes.

A chaque ouverture d'enveloppe, je peux m'arrêter si je pense avoir trouvé le plus grand, ou bien continuer à ouvrir une autre autre enveloppe. Je ne peux pas aller en arrière.

Si j'ai trouvé le plus grand, j'ai gagné 15 fois ce nombre en millions d'euros. Sinon, je dois payer 100.000 fois ce nombre, toujours en euro.

A quel moment s'arrêter ?

vbnul · 17-07-2009 17:46:47

Y a t il vraiment une solution ne dépendant pas des entiers et de leur distribution ?

Je donne ma langue au chat.

Valfravier · 18-07-2009 05:45:21

il faut laisser passer les 37 premiers (en fait N/e où N est le nbre de prétendants et e=exp(1)) et noter quel est le meilleurs. On choisit alors le premier meilleur prétendant. si on n'en trouve pas on se contente du 100ème car le meilleur était dans les 37 premiers. En suivant ce protocole, on trouve le meilleur dans 37,8 % des cas (en fait la probabilité vaut 1/e). J'ai essayé tous les cas avec excel et ça marche mais je ne suis pas encore arrivé à démontrer les valeurs exactes. Si qq'un à une démo claire, je suis preneur.

Pour référence, lisez le pour la science de ce mois où il y a un article sur les pb d'arrêt et un paragraphe sur le pb de la mariée.

freddy · 18-07-2009 09:26:11

Salut Val et bienvenue sur le site.

c'est l'établissement de ce résultat que je cherchais à (faire) établir de manière heuristique. C'est dommage, va falloir que tu t'y colles ... :-)))

Freddy

Dernière modification par freddy (18-07-2009 09:46:52)

Valfravier · 19-07-2009 00:20:45

Bonjour Freddy (et les autres s'il y en a d'autres qui lisent encore cette discussion),
Je suis désolé d'écrire avec autant de retard mais je ne suis pas en France et le décalage horaire est de 7 heures.
Je suis également désolé d'avoir vendu la mèche. Je ne connaissais pas le principe de ce type de forum.

Pour ce qui est de ce problème, cela fait un petit moment que j'y travail (rien de bien violent...).
Il faudrait arriver à maximiser la fonction P définie par: [tex]P\left(L\right)=\sum^{N-L+1}_{n=1}\frac{L\times \left(N-L)!\right}{n{\times N}^{n+1}\times \left(N-L-n\right)!}[/tex] où N est le nombre total de prétendants et L le nombre prétendants que l'on laisse passer avant de choisir le meilleur.Cette fonction est la probabilité de trouver le meilleur. La formule manque d'élégance, d'autant qu'il faut la dériver par rapport à L. Je l'ai trouvé par des méthodes de probabilité simple. Je peux vous en donner le détail si ça vous intéresse d'autant que chaque terme de la somme se déduit du précédent:[tex]{t}_{n+1}=\frac{\left(N-L-n\right)\times n}{N\times \left(n+1\right)}\times {t}_{n}[/tex].

Ce que je n'arrive pas à faire, c'est trouver le maximum de cette fonction. Théoriquement c'est L=N/e mais ça me semble assez incroyable. J'ai, grâce à la forme par récurrence précédente, fait une simulation sur excel et on obtient bien un maximum au alentours de N/e qui vaut (presque) 1/e (j'ai essayé avec N=100 puis N=1000 et mon vieux dell à passé plus de 2 min à me donner le résultat). J'aimerai bien savoir comment arriver à justifier ce résultat. Pour l'instant, je le trouve trop beau pour être vrai mais la simulation semble le confirmer.

C'est assez frustrant de n'arriver qu'à faire des simulations.

Avez-vous d'autre idées ?

freddy · 19-07-2009 21:53:24

Salut,

non, pas de principe, mais ... Sinon, je vais regarder la formule proposée et voir comment la maximiser. Mais pour trouver e, en général, cela signifie qu'on a utilisé la formule de Stirling pour approximer une "grosse" factorielle ...

A plus ...

freddy · 20-07-2009 09:58:08

Re,

sans chercher à vérifier si la Proba que tu nous donnes est bonne, je pense qu'il faut raisonner plus simplement du genre : le meilleur est dans le premier ou second groupe (dont je dois définir la taille T) de telle sorte que Espérance (Gain/T) soit max.

En toute modestie, je n'ai pas encore compris pourquoi ce problème de décision revenait à partitionner en deux groupes disjoints le référentiel et à trouver la césure idéale pour maximiser mes chances de gains.

Comment se fonde logiquement cette stratégie, je ne sais encore.

Répondre à cette question permettra de déduire le calcul de cette taille idéale, je ne suis pas sûr que la bonne méthode consiste à inférer de la conclusion la méthode idoine.

F.

Dernière modification par freddy (20-07-2009 15:57:04)

diop · 21-07-2009 00:56:56

bonjour
pour ce probléme je crois qu'il faut savoir si les hommes sont classés, selon le critère beau, par ordre croissant, décroissant ou mélangés.Donc elle doit laisser passer quelques hommes et remarquer c'est lequelle des trois hypothèses citées est la bonne.Si c'est croissant elle est obligé de choisir le dernier,si c'est décroissant elle doit se limiter aux premiers.Par contre il reste le 3ieme cas qui en mon sens n'est pas simple car nécessitant des connaissances en mathématiques telles que les probabilités conditionnelles.

freddy · 22-07-2009 12:25:44

Bonjour,

ne cherchez plus, j'ai trouvé la solution.

Accrochez vous bien, c'est du très haut niveau.

http://www.ceremade.dauphine.fr/~mgubi/ … opping.pdf

F.

PS : pour information, le CEREMADE est le CEntre de REcherche en MAthématiques de la DEcision.

Dernière modification par freddy (22-07-2009 12:30:36)

yoshi · 22-07-2009 19:27:24

Bonsoir,

Boufre !!!! Rien que ça...

Bon, concrètement, la minette qui a droit à 100 présentations de mecs pour choisir s'arrête quand et comment ?

@+

Le béotien de service

freddy · 22-07-2009 21:07:38

Salut Yoshi,

Bon, c'est simple en pratique : elle auditionne les 100/e = 37 premiers sans s'arrêter sur aucun. Par contre, elle sait celui qui lui est paru le meilleur parmi eux.

Puis elle reprend l'audition des suivants et s'arrête sur le premier qui lui paraît mieux que le meilleur des 37 premiers. Et il est démontré par le lien supra que c'est la meilleure stratégie conçue par l'esprit humain.

Tu peux développer l'analogie avec les nombres entiers, ça marche très bien.

Ensuite (devinette simple), le matin qui suit la nuit de noce, on a cet étrange échange entre le jeune épousé et la mère de la Belle (devenu par un usage consacré la belle-mère) :

7 3, 13 3

La mère de la Belle répond :

67 3, 79

Dernière modification par freddy (22-07-2009 21:08:29)

Valfravier · 23-07-2009 04:59:21

Bonjour,
C'est effectivement du lourd mais merci beaucoup pour le lien. Reste plus qu'à déchiffrer et y a du boulot. À noter que le coup des places de parking qui suit et peut être utile et est assez intressant. Je continu à dire que ma formule reste bonne aussi sauf que je n'arrive pas à la maximiser (formule de stirling inutile car N n'est pas assez grand).

PS: la belle mère répond plutôt 6 7 3, 7 9

yoshi · 23-07-2009 06:48:45

Bonjour,

Freddy a écrit :

...(devinette simple)...

Ah ? Certes, pour celui qui sait ! Mon niveau intellectuel a donc dû sérieusement baisser : l'âge sans nul doute ;-)

@+

freddy · 23-07-2009 11:01:08

Re,

ne te fais pas du mal, yoshi, on dira que tu n'étais pas assez attentif. Perso, j'ai compris tout de suite, avec la réponse de la belle mère ... J'ai des copains de ton âge (X66 et 67, il voulait ULM) qui sont toujours aussi jeune d'esprit, comme toi.

Valfavrier, exact, j'ai mal écrit la réponse, au temps pour moi.

++ ...

yoshi · 23-07-2009 16:43:10

Salut,

T'es gentil (et involontairement un rien condescendant : "J'ai des copains de ton âge (X66 et 67, il voulait ULM) qui sont toujours aussi jeune d'esprit, comme toi"), mais je ne vois pas, mais alors absolument pas, ce n'est pas une question d'inattention !
Et je devrais me creuser les méninges, alors que
1. Quelqu'un m'annonce : MOI, j'ai compris tout de suite,
2. Un 2e renchérit dans la même veine,
3. Je n'ai absolument pas le moindre début de commencement de lueur...
4. Vu le 1., le 2. et le 3., je retourne jouer avec ce qui est accessible à mon entendement...
Affaire classée.

Ce n'est pas grave, il y a bien plus important : j'sais encore compter sur mes doigts : 1,3, 5,2,9... C'est toujours ça ... ;-)
Donc, ne perds pas de temps avec ce post, pense éventuellement à répondre à ceux qui demanderont peut-être à savoir...

@+

nerosson · 24-07-2009 13:49:03

Salut à tous,
Remarquons d'abord que si la jeune fille n'a que le droit de les auditionner, c'est nettement insuffisant comme critère. Vous voyez ce que je veux dire ? Nos "jeunes filles" modernes ne se contenteraient pas de ça, et les prétendants auraient bien tort de s'en plaindre .... Vous en connaissez beaucoup, vous, des "jeunes filles" de 25 ans ?
Il me semble que si elle veut avoir une attitude rationnelle, la jeune fille doit se constituer un barème de notation de 0 à 19 (la perfection n'est pas de ce monde. Même moi...)
A partir de là, elle doit admettre la conjecture non démontrée que les 100 prétendants se répartissent à peu près uniformément entre ces vingt notes.
Après avoir attribué une note à un prétendant, elle devra A CHAQUE FOIS recalculer, toujours selon le principe d'une répartition uniforme des prétendants RESTANTS entre les différentes notes, la probabilité qu'il y en ait un qui ait une note supérieure à celle qu'elle vient d'attribuer. Si cette probabilité est inférieure à 50 %, elle arrête.
Je laisse aux matheux, qui pullulent sur ce site comme les poux sur la tête d'un teigneux, le soin de définir la procédure de calcul.
Cordialement à tous.
P.S. un salut particulier à toi, Freddy. Tu sais comme je suis toujours heureux de te retrouver. Au fait, comment va ta prostate ?

freddy · 24-07-2009 14:29:42

Salut néro,

c'est "idiot" comme système, ne penses tu pas ? Même l'hypothèse de base est stupide : par exemple, si je nous prends en exemple, toi, moi et Yoshi, c'est sûr qu'on va créer un sérieux point d'accumulation sur la meilleure note, ce qui met en l'air ton hypothèse d'équirépartition uniforme sur le segment entier [0, 19].

Il y a bcp mieux, comme indiqué dans le lien joint, qui ne formule aucun hypothèse de ce genre mais qui postule qu'il y en a sûrement un dans le paquet meilleur que les 99 autres, du point de vue de la jeune fille de 25 ans au plus.

Au fait, c'est quoi, la prostate ? Un nouveau procédé mathématique pour estimer le nombre de poux sur la tête d'un teigneux ?

Bien cordialement

Dernière modification par freddy (24-07-2009 17:43:04)

nerosson · 24-07-2009 16:51:32

Bonsoir, freddy,
C'est ta réponse qui ne tient pas la route (pour ne pas employer de mot excessif, même entre guillemets). Tout le monde sait que yoshi, toi et moi, les femmes se sont battues pour nous mettre le grappin dessus. On ne peut pas fonder un raisonnement défendable là dessus.
Bien que 100 ne soit pas un très grand nombre, on peut tout à fait légitimement tenir pour probable qu'il représentera un échantillonnage à peu près équilibré de bons, de moyens et de mauvais. C'est le point de départ de mon raisonnement, et je soutiens contre vents et marées qu'il est parfaitement valable. On a parfois l'impression que le bon sens ne fait pas toujours très bon ménage avec les hautes mathématiques.Dire qu'il y en a sûrement un qui vaut mieux que les 99 autres, c'est une Lapalissade, mais c'est une évidence qu'elle n'aura pas de moyen de l'identifier, mathématiques ou pas, car pour l'identifier, il faudrait qu'elle puisse tous les passer en revue, or, c'est précisément ce qu'elle ne peut pas faire. D'autre part, l'idée d'éliminer d'autorité les 37 premiers, quelle que soit leur valeur, si c'est à des idées de ce genre que mènent les mathématiques, cette pauvre fille ferait mieux d'entrer au couvent. Qu'est-ce qui permet d'affirmer que le meilleur ne se trouve pas dans les 37 premiers ?
Cordialement quand même.
P.S. ta devinette 7 3 , 13 3 est incomplète. Elle circulait quand j'étais au collège, dans les années trente. Le libellé complet est : 7 3 , 13 3 , 7 9 .

Dernière modification par nerosson (24-07-2009 17:54:41)

yoshi · 25-07-2009 08:17:48

Bonjour,

" Lavé avec Mir laine ? " comme dit la pub...
Onc n'aurais-je pu imaginer pareille gaudriole dans un aussi sérieux sujet !
Un peu de tenue, S.V.P...

Bon, revenons à nos moutons :

freddy a écrit :

Bon, c'est simple en pratique : elle auditionne les 100/e = 37 premiers sans s'arrêter sur aucun. Par contre, elle sait celui qui lui est paru le meilleur parmi eux.
Puis elle reprend l'audition des suivants et s'arrête sur le premier qui lui paraît mieux que le meilleur des 37 premiers. Et il est démontré par le lien supra que c'est la meilleure stratégie conçue par l'esprit humain.

Je rejoins plus ou moins Nerosson : il me paraît totalement aberrant de procéder ainsi...
J'ai toujours entendu mon père me dire que << le mieux était l'ennemi du bien ! >>, variante du dicton << Un bon tien vaut mieux que tu l'auras ! >>
Alors, admettons que le 1er candidat dans les 37 premiers lui paraisse très bien, qu'elle ait le coup de foudre, au nom des mathématiques elle devrait alors le rejeter, sous prétexte qu'en gros il y a 2 chances sur 3 qu'il y en ait encore un mieux parmi les représentants de la série 38 --> 100...

Et je récuse pareillement l'analogie avec les nombres. Lesdits nombres sont des objets in-mutables pour lesquels il est facile de trouver le plus grand lorsqu'ils sont pris entre 1 et 100 consécutivement et même si on en choisit 100 entre 1 et 100000...
Alors, dans ce cas, oui, la stratégie exposée est celle qui offre le plus de chances de trouver le plus grand (à condition bien sûr que l'on ne sache seulement qu'il a été choisi 100 nombres différents. Point)
Mais vouloir conditionner un choix totalement subjectif au niveau des critères de sélection à une procédure mathématique me paraît un tantinet... aléatoire ;-)
Ce n'est pas le procédé mathématique que je remets en cause, mais l'EMPLOI du procédé dans ce cas...

Autre phrase classique : << La beauté ne se mange pas en salade >>, pas plus que les qualités humaines d'une personne ne sont quantifiables mathématiquement : on n'est pas encore dans l'univers d'Aldous Huxley ou celui (moins connu) d' Ira Levin (l'auteur de Rosemary's Baby) dans "Un bonheur insoutenable " !

@+

freddy · 25-07-2009 11:14:23

Hi,

D'accord avec vous deux, pour bien choisir sa compagne ou son compagnon, le procédé est "idiot". En fait, c'est la métaphore du journaliste de "Pour la science" qui n'est pas de la meilleure farine. Mais ce même journaliste racontait comment un G'I (mathématicien dans le civil) s'était fait un petite fortune par ce procédé : les copains du régiment inscrivaient sur un papier un nombre entier relatif et lui, pariait qu'il trouverait le plus grand avant d'avoir retourné tous les petits bouts de papier. Les parieurs payaient 10 $ s'il gagnait, et lui donnait aux parieurs 1 $ s'il perdait.

Donc, si on reprend l'analogie avec 100 nombre choisis parmi 1 et 10 milliards par exemple, alors le problème du choix à temps limité reprend son droit. Comme celui de choisir son mari parmi 100 via des procédures type speed dating coûteuse. Car, comme on ne le sait que trop, le temps, c'est de l'argent !

Sinon, ma grand mère disait :" Un bon tien vaut mieux que deux, tu l'auras". Et j'essayais de lui expliquer que ça ressemblait trop à une philosophie de la résignation, à une attitude très (trop) risk-adverse. ... Tiens, cela me rappelle un petit sujet de derrière les fagots des années 70 que je m'en vais poster de ce pas.

C'est plus adapté au problème du choix de la secrétaire en un temps donné, j'en conviens. Ou de la première place à retenir pour se garer pour assister à une représentation au théâtre. Faut juste savoir que ce sont des problèmes qui donnent encore lieu à de nombreux travaux.

+++

Pour neroSson : un échantillon de 100 personnes ne peut être représentatif d'une population, les résultats sont trop entachés d'incertitude. Il faut "pousser" vers 1.000, et c'est encore souvent trop insuffisant. C'est pour cela que la nature nous a doté de procédés neurochimiques plus efficaces pour assurer la survie de l'espèce (l'amour n'est qu'une image poétique desdits procédés ...)

Dernière modification par freddy (26-07-2009 19:30:58)

Forum de mathématiques - Bibm@th.net

#1 05-07-2009 21:58:29

Choisir parmi 100 prétendants

#2 05-07-2009 22:24:19

Re : Choisir parmi 100 prétendants

#3 06-07-2009 08:31:27

Re : Choisir parmi 100 prétendants

#4 06-07-2009 10:25:56

Re : Choisir parmi 100 prétendants

#5 06-07-2009 14:20:38

Re : Choisir parmi 100 prétendants

#6 17-07-2009 16:57:04

Re : Choisir parmi 100 prétendants

#7 17-07-2009 17:46:47

Re : Choisir parmi 100 prétendants

#8 18-07-2009 05:45:21

Re : Choisir parmi 100 prétendants

#9 18-07-2009 09:26:11

Re : Choisir parmi 100 prétendants

#10 19-07-2009 00:20:45

Re : Choisir parmi 100 prétendants

#11 19-07-2009 21:53:24

Re : Choisir parmi 100 prétendants

#12 20-07-2009 09:58:08

Re : Choisir parmi 100 prétendants

#13 21-07-2009 00:56:56

Re : Choisir parmi 100 prétendants

#14 22-07-2009 12:25:44

Re : Choisir parmi 100 prétendants

#15 22-07-2009 19:27:24

Re : Choisir parmi 100 prétendants

#16 22-07-2009 21:07:38

Re : Choisir parmi 100 prétendants

#17 23-07-2009 04:59:21

Re : Choisir parmi 100 prétendants

#18 23-07-2009 06:48:45

Re : Choisir parmi 100 prétendants

#19 23-07-2009 11:01:08

Re : Choisir parmi 100 prétendants

#20 23-07-2009 16:43:10

Re : Choisir parmi 100 prétendants

#21 24-07-2009 13:49:03

Re : Choisir parmi 100 prétendants

#22 24-07-2009 14:29:42

Re : Choisir parmi 100 prétendants

#23 24-07-2009 16:51:32

Re : Choisir parmi 100 prétendants

#24 25-07-2009 08:17:48

Re : Choisir parmi 100 prétendants

#25 25-07-2009 11:14:23

Re : Choisir parmi 100 prétendants

Pied de page des forums