Exemple de tirage aléatoire d'un sous-ensemble.

[Dlzlogic]

Bonjour,
Soit la question suivante : "Comment générer un sous-ensemble d'un ensemble donné ?" Elle a été posée dans un contexte informatique. L'auteur de la question voulait que les éléments du sous-ensemble soient tous différents, c'est à dire qu'il n'y ait pas de doublon, mais qu'ils résultent d'un tirage aléatoire.
Ma question : dans un contexte de simulation dans le domaine des probabilités, auriez-vous un exemple d'application où cette hypothèse est utile ?.
Précision : l'ensemble de départ est grand ainsi que le nombre d'éléments du sous-ensemble, ce qui entraine un grand nombre de tests.

Merci d'avance.
PS Il ne s'agit en aucun cas de discuter de problème lié à la fonction rand.
-----

[Tryss2]

Tout dépend de la distribution des sous ensembles que l'on souhaite obtenir. "au hasard", ça regroupe beaucoup de situations

[Dlzlogic]

Justement, je na sais pas et j'essaye d'imaginer des cas d'utilisation possible.
Une seule chose est sous-entendue : il s'agit d'une répartition normale, c'est à dire tirage suivant une loi uniforme, puisque la fonction rand est utilisée.
Je rappelle que la préoccupation qui a provoqué ma question est une préoccupation d'ordre informatique, cad temps de traitement. Ce n'est ma question dans le présent fil.

[Médiat]

Bonjour,

Un méthode très efficace en termes informatique (mais nul en cryptographie) :

Soit n le cardinal de l'ensemble (qui est donc égal à 0, 1, 2, ... n-1), soit p le cardinal du sous ensemble à déterminer, on choisi m un nombre premier, beaucoup plus grand que n, et k un nombre entre 0 et n-1

on pose s(i) = mod(m*(k + i), n) et on s'arrête à i = p

Cela devrait marcher

[A voir en vidéo sur Futura]

[Dlzlogic]

Bonjour Médiat,
Oui, astucieux, mais ce n'est pas vraiment ma question. Si j'avais à faire cela, je procéderais plutôt par hachage.
Effectivement la question était peut-être posée dans un contexte de cryptographie. En effet, il est intéressant d'avoir un résultat qui m'a pas une répartition normale.

[minushabens]

Il existe pas mal de modèles probabilistes de sous-ensembles aléatoires de R ou R^n. Le processus de Poisson en est un très simple, et à partir de lui on construit d'autres modèles, en attachant à chaque point du processus un ensemble généralement compact centré en zéro. Il y a de la biblio là-dessus dans le livre de Stoyan, Kendall & Mecke.

[Dlzlogic]

Bonsoir Minushabens,
Ma question porte exclusivement sur la volonté d'obtenir un sous-ensemble d'un plus grand ensemble. En gros, il s'agit de saisir un grand nombre d'éléments d'un tirage d'une urne contenant un très grand nombre d'éléments ET sans remise.
Cette question a été posée dans un cadre informatique, suivant le schéma suivant :
Tirage d'un élément, vérification que cet élément n'a pas déjà été tiré et cela jusqu'à remplir la liste souhaitée.
Si la liste est de l'ordre d'une dizaine, pas de problème, mais quand la liste voulue est grande, par exemple 1000, alors cela devient très long.
Différentes solutions ont été proposées, mais ma question : "je voudrais un exemple de cas réel où une telle simulation serait nécessaire".
Par contre, si ça intéresse quelqu'un, la solution de hachage est une bonne réponse au problème.

A partir du moment où on refuse les doublons, on n'est plus dans le cas d'un tirage aléatoire, lequel est donné par la fonction rand.
Désolé de ne pas rebondir sur la loi de Poisson, mais je la connais mal. De toute façon, c'est la loi des évènement rares, ce qui n'est pas le cas présentement. D'ailleurs, il ne semble pas que la loi de Poisson refuse les doublons.

[Médiat]

Bonjour,

je voudrais un exemple de cas réel où une telle simulation serait nécessaire

La solution que j'ai proposée plus haut, je l'ai mise au point après avoir essayé d'autres solutions, dans le cadre de la conception d'un générateur automatique de jeux de tests pour des bases de données (potentiellement l'ensemble dans lequel on pioche pouvant contenir plusieurs dizaines de millions de lignes, voire plus).

La première question était :

"Comment générer un sous-ensemble d'un ensemble donné ?"