Somme Partielle Combinatoire

Version imprimable

13/07/2010, 12h18
Nemerle

Somme Partielle Combinatoire

Salut,

comment calculeriez-vous avec une précision à deux chiffres après la virgule la somme des C(n,i)x^i(1-x)^(N-i) pour i de 0 à S<N, avec x<1 ? Pour N=5000 par exemple et S=4000...
13/07/2010, 13h24
Invité(e)
Bonjour,

Un petite question sur le terme à sommer : faut-il lire :
Code:

1 2 3 4 5 / \ | N | i N-i | | x (1-x) | i | \ /
ou
Code:

1 2 3 4 5 / \ N-i | N | i (1-x) | | x | i | \ /
?

Si c'est la première solution, on retombe sur le binôme de Newton (en fait non puisse qu'on s'arrête à S < N ...)
16/07/2010, 10h18
Nemerle

il faut lire ta 1ière proposition.

effectivement, le problème vient de la somme partielle...
16/07/2010, 11h09
pseudocode

Citation:

Envoyé par mabu

Si c'est la première solution, on retombe sur le binôme de Newton (en fait non puisse qu'on s'arrête à S < N ...)

Du coup, ca revient a calculer la somme pour S>=N et la retrancher à la somme globale ( = 1 ).
16/07/2010, 11h38
Nemerle

certes, mais ça n'avance pas le chimilimi...
16/07/2010, 11h54
Invité(e)
si on reprend le schéma du triangle, il y a peut etre quelque chose à fouiller :
Si N égale 5 et S 3
Code:

1 2 3 4 5 6 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10105 1
On pourrait dire que la somme à trouver est 1 moins les coefficients collés à droite, mais je pense qu'on retombe sur un problème similaire avec beaucoup de coefficients à sommer.

EDIT :
En creusant, on pourrait peut-être approximer les coefficients à sommer à une loi gaussienne, leur somme à l'intégrale donc une loi normale. (Mes anciens prof de maths doivent s'en retourner dans leur classe)
16/07/2010, 12h04
pseudocode

Citation:

Envoyé par Nemerle

certes, mais ça n'avance pas le chimilimi...

Ca fait déjà moins de terme à sommer si j'en juge ton exemple du 1er post. :P

En prenant le Log de la somme, ca allège un peu les calculs à faire, vu qu'on peut factoriser par Log(x) et Log(1-x).
16/07/2010, 12h14
Nemerle

Citation:

Envoyé par pseudocode

En prenant le Log de la somme, ca allège un peu les calculs à faire, vu qu'on peut factoriser par Log(x) et Log(1-x).

Gné???? Le log d'une SOMME?
16/07/2010, 14h06
pseudocode

Citation:

Envoyé par Nemerle

Gné???? Le log d'une SOMME?

Arf. J'ai besoin de vacances. :aie: Je pensais que le 1er terme de la somme valait 1 et donc que ca simplifiait la somme de Log.

Hum... bon. C'est vrai que c'est pas simple comme problème. Ca revient au calcul de la fonction de répartition d'une distribution binomiale, non ? :koi:
16/07/2010, 15h43
JeitEmgie

Citation:

Envoyé par Nemerle

Salut,

comment calculeriez-vous avec une précision à deux chiffres après la virgule la somme des C(n,i)x^i(1-x)^(N-i) pour i de 0 à S<N, avec x<1 ? Pour N=5000 par exemple et S=4000...

çà me fait penser à une courbe de Bezier de degré N ?
…sauf que vous "coupez" au degré S dans l'évaluation…

courbe de Bezier :

B(t) = Somme de i=0 à N de C(n,i) * (1-t)^(N-i) * t^i * Pi

votre formule, sauf erreur :

F(x) = Somme de i=0 à S de C(n,i) * (1-x)^(N-i) * x^i

Donc votre F(x) serait une courbe de Bezier de degré N avec Pi=(1,1) pour tout i <= S et Pi=(0,0) pour i > S…

?
17/07/2010, 11h30
Zavonen

Il me semble que la solution de ce problème se trouve entre (en combinant) les deux articles:
Cumulative Binomial Distribution
et
Incomplete Beta Fonction
de Numerical recipes in C
adresse:
http://www.fizyka.umk.pl/nrbook/bookcpdf.html
19/07/2010, 16h16
Nemerle

Merci Zavonen, je vais regarder ASAP.

Citation:

Envoyé par Nemerle

Merci Zavonen, je vais regarder ASAP.

examinez la similitude avec la courbe de Bezier, si c'est bien le cas ce n'est pas les algorithmes efficaces qui manquent… et dans votre cas vous n'avez qu'une dimension à évaluer…

par exemple :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
/*
 Simplified Casteljau algorithm for only one dimension
 and control "points" only 1 and 0
 t in [0-1]
 p array of N (number of control points) float
 */
float evaluate1(float *p,int n, int s, float t)
{	
	// we evaluate only one coordinates of the Bezier
	// with P[0 -> S].x = 1 and P[S+1 -> N-1].x = 0
	// n the degree of the "curve" == number of control points - 1 == N - 1
 
	for(int i=0;i<=s;i++)
		p[i] = 1.0 ;
	for(int i=s+1;i<=n;i++)
		p[i] = 0.0 ;
 
	float t1 = (1.0 - t) ;
 
	for(int j=1;j<n;j++) {
		for(int i=0;i<n-j;i++) {
			p[i] = t1 * p[i] + t * p[i+1] ;
		}
	}
 
	return p[0] ;
}

19/07/2010, 17h11
Nemerle

Zavonen: oui, ça répond à mon besoin.

Mais finalement, on a implémenté la représentation en rationnel & la norme MPFR, pour calculer tout ça! ;)