# compte les surjections de n sur q
def surj(n,q) :
return add((-1)^(q-i)*binomial(q,i)*i^n for i in range(q+1))
# proba qu'il reste q urnes vides après lancer de n boules dans k urnes
def proba(n,k,q) :
return surj(n,k-q)*binomial(k,q)/k^n
# prend le nombre n de boules et la liste L des probas
# qu'il y ait 1,2,3,... urnes et retourne la liste des
# probas qu'il y ait 1,2,3,... urnes vides après le
# lancer de n boules
def tour(n,L) :
k=len(L)
return [add(L[i]*proba(n,i+1,j+1) for i in range(j,k)) for j in range(k)]
# prend le nombre n de boules, le nombre k d'urnes
# au départ et le nombre x de tours de lancers,
# et retourne la liste des probabs qu'il reste
# 1,2,...,k urnes vides après x tours de lancers
def reste(n,k,x) :
L=(k-1)*[0]+[1]
for i in range(x) :
L=tour(n,L)
return L
# prend le nombre n de boules, le nombre k d'urnes
# au départ et le nombre x de tours de lancers,
# et retourne la probabilité qu'il reste au moins
# une urne vide après x tours de lancers
def probareste(n,k,x) :
return add(reste(n,k,x))
for i in range(7) :
print "proba qu'il reste une urne vide après",i,\
"tours :", probareste(4,10,i).n(10)
proba qu'il reste une urne vide après 0 tours : 1.0
proba qu'il reste une urne vide après 1 tours : 1.0
proba qu'il reste une urne vide après 2 tours : 1.0
proba qu'il reste une urne vide après 3 tours : 0.65
proba qu'il reste une urne vide après 4 tours : 0.040
proba qu'il reste une urne vide après 5 tours : 0.00025
proba qu'il reste une urne vide après 6 tours : 2.4e-7
# coefficients binomiaux
def binomial(n, k):
if 0 <= k <= n:
ntok = 1
ktok = 1
for t in range(1, min(k, n - k) + 1):
ntok *= n
ktok *= t
n -= 1
return ntok // ktok
else:
return 0
# somme des nombres d'une liste
def add(L):
S=0
for l in L : S+=l
return S
# compte les surjections de n sur q
def surj(n,q) :
return add([(-1)**(q-i)*binomial(q,i)*i**n for i in range(q+1)])
# proba qu'il reste q urnes vides après lancer de n boules dans k urnes
def proba(n,k,q) :
return surj(n,k-q)*binomial(k,q)/k**n
# prend le nombre n de boules et la liste L des probas
# qu'il y ait 1,2,3,... urnes et retourne la liste des
# probas qu'il y ait 1,2,3,... urnes vides après le
# lancer de n boules
def tour(n,L) :
k=len(L)
return [add([L[i]*proba(n,i+1,j+1) for i in range(j,k)]) for j in range(k)]
# prend le nombre n de boules, le nombre k d'urnes
# au départ et le nombre x de tours de lancers,
# et retourne la liste des probabs qu'il reste
# 1,2,...,k urnes vides après x tours de lancers
def reste(n,k,x) :
L=(k-1)*[0]+[1]
for i in range(x) :
L=tour(n,L)
return L
# prend le nombre n de boules, le nombre k d'urnes
# au départ et le nombre x de tours de lancers,
# et retourne la probabilité qu'il reste au moins
# une urne vide après x tours de lancers
def probareste(n,k,x) :
return add(reste(n,k,x))
[262463183261841957740693574439/1684976604586659191808000000000,
300541752318615126800841114661/13479812836693273534464000000000,
2940907301575323007492135321/1497756981854808170496000000000,
9956847451424466151353727/93609811365925510656000000000,
2107891037980516069651/599102792741923268198400000,
46428834951715344041/665669769713248075776000000,
14057061918646519/17466553724254322688000000,
176198408611/34114362742684224000000,
5107/303870831264000000,
1/46796108014656000,
0,
0,
0,
0,
0]
GaBuZoMeu a écrit:Tu te poses peut-être un problème qui dépasse tes capacités, alors.
GaBuZoMeu a écrit:Fixer Y à 100% me semble complètement idiot, désolé de te le dire : il est clair que dès que x fois n est supérieur ou égal à k, il y a une probabilité non nulle qu'il ne reste aucune urne vide.
GaBuZoMeu a écrit:Il est instructif de faire quelques expériences : on constate que le passage de la situation où on est quasi-sûr d'avoir au moins une urne vide à celle où on est quasi-sûr ne n'en avoir aucune se fait très rapidement.
GaBuZoMeu a écrit:Je précise que les résultats que je donne ne sont bien sûr pas des simulations, mais des résultats exacts correspondant aux données du problème
Stubbs a écrit:GaBuZoMeu a écrit:Fixer Y à 100% me semble complètement idiot, désolé de te le dire : il est clair que dès que x fois n est supérieur ou égal à k, il y a une probabilité non nulle qu'il ne reste aucune urne vide.
Ne sois pas désolé, ce n'est pas si étonnant étant donné ma faible compréhension des probabilités. Lorsque je simule un scénario un million de fois et que j'en fais la moyenne, j'arrive clairement à un stade où on est “certain” d'avoir une urne vide à la fin. Mauvais raisonnement.
GaBuZoMeu a écrit:Il est instructif de faire quelques expériences : on constate que le passage de la situation où on est quasi-sûr d'avoir au moins une urne vide à celle où on est quasi-sûr ne n'en avoir aucune se fait très rapidement.
Tu mets justement le doigt sur ce pourquoi j'ai besoin de la réponse à cette question
GaBuZoMeu a écrit:Je précise que les résultats que je donne ne sont bien sûr pas des simulations, mais des résultats exacts correspondant aux données du problème
Je vais tenter de porter ton code pyton en javascript, puisque c'est ce que j'utilise. Ça représente déjà une grande avancée pour la résolution de mon problème. Un grand merci pour le temps investi dans tes réponses !
Le problème restant est qu'il faut simuler avec plusieurs valeurs pour K jusqu'à trouver une réponse satisfaisante. Je vais voir ce que ça donne !
Après, je ne suis pas convaincu que javascript soit ce qu'on fait de mieux pour manipuler des matrices
GaBuZoMeu a écrit:Il ne s'agit pas ici de probabilité, mais de bon sens.
GaBuZoMeu a écrit:Peux-tu en dire plus sur ta problématique, ou c'est secret d'état?
# coefficients binomiaux
def binomial(n, k):
if 0 <= k <= n:
ntok = 1
ktok = 1
for t in range(1, min(k, n - k) + 1):
ntok *= n
ktok *= t
n -= 1
return ntok // ktok
else:
return 0
# somme des nombres d'une liste
def addlist(L):
S=0
for l in L : S+=l
return S
# compte les surjections de n sur q
def surj(n,q) :
return addlist([(-1)**(q-i)*binomial(q,i)*i**n for i in range(q+1)])
# proba qu'il reste q urnes vides après lancer de n boules dans k urnes,
# avec traitement spécial du cas k=0
def proba(n,k,q) :
if k==0 :
if q==0: return 1
else : return 0
else :
return surj(n,k-q)*binomial(k,q)/k**n
# matrice de transition de la chaîne de Markov
# comme liste de listes
def transition(n,k) :
return [[proba(n,i,j) for i in range(k+1)] for j in range(k+1)]
# ersatz de multiplication matrice-vecteur
def multmatvect(A,V) :
d=len(V)
return [addlist([A[i][j]*V[j] for j in range(d)]) for i in range(d)]
# prend le nombre n de boules, le nombre k d'urnes
# au départ et le nombre x de tours de lancers,
# et retourne la liste des probas qu'il reste
# 0,1,2,...,k urnes vides après x tours de lancers
def reste(n,k,x) :
A=transition(n,k)
L=k*[0]+[1]
for i in range(x) :
L=multmatvect(A,L)
return L
# prend le nombre n de boules, le nombre k d'urnes
# au départ et le nombre x de tours de lancers,
# et retourne la probabilité qu'il ne reste plus
# d'urne vide après x tours de lancers
def probaelimine(n,k,x) :
return reste(n,k,x)[0]
k= 30 : (0.9999976271689872,)
k= 31 : (0.9999919716319614,)
k= 32 : (0.9999744791666196,)
k= 33 : (0.9999237589619842,)
k= 34 : (0.9997859539210946,)
k= 35 : (0.99943531732955,)
k= 36 : (0.998600280284522,)
k= 37 : (0.9967400497244271,)
k= 38 : (0.9928657180242075,)
k= 39 : (0.9853263956327388,)
k= 40 : (0.9716281944763874,)
k= 41 : (0.9484111415517404,)
k= 42 : (0.911743699645405,)
k= 43 : (0.8578571637572017,)
k= 44 : (0.784294054181758,)
k= 45 : (0.6912024261774197,)
k= 46 : (0.5822758924919857,)
k= 47 : (0.46478360711051236,)
k= 48 : (0.3483837873513694,)
k= 49 : (0.2429319844756179,)
k= 50 : (0.1560345472492654,)
k= 51 : (0.09131951274309069,)
k= 52 : (0.04810690054960892,)
k= 53 : (0.02248761858425984,)
k= 54 : (0.009166804586803674,)
k= 55 : (0.003187398578702116,)
k= 56 : (0.0009178652319919577,)
k= 57 : (0.00020987901015420132,)
k= 58 : (3.568232982519628e-05,)
k= 59 : (4.004652037074188e-06,)
k= 60 : (2.2225415310903611e-07,)
Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 31 invités
Tu pars déja ?
Identification
Pas encore inscrit ?
Ou identifiez-vous :