ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Теория вероятности. функция распределения для Пуассон-Биномиального распределения
11 сообщений из 11, страница 1 из 1
Теория вероятности. функция распределения для Пуассон-Биномиального распределения
    #37008335
Диклевич Александр
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Диклевич Александр
Участник
Доброго времени суток!
Несмотря на название темы, основной смысл ее не теория, а практическая реализация следующего алгоритма.
Допустим мы проводим три независимых испытания Бернулли (т.е. испытание имеет два исхода - успех и неудача), но в каждом из трех испытаний вероятность успеха разная.
Назовем их (вероятности успеха в каждом испытании) р1, р2 и р3. В конечном итоге мы заинтересованы в сумме успехов в этих трех испытаниях.
Понятно, что в сумме мы можем получить 0, 1, 2 или 3 успеха. Теперь предстает вопрос в подсчете вероятностей для каждого из вариантов. В общем-то не вопрос подсчета, а его реализация на каком-либо языке программирования.
Так, мы получаем 0 успехов - вероятность (1 - р1)*(1 - р2)*(1 - р3)
1 успех - вероятность р1*(1 - р2)*(1 - р3) + (1 - р1)*р2*(1 - р3) + (1 - р1)*(1 - р2)*р3 (т.е. мы проходим все сочетания из 3-х по 1-му, а это 1, 2 и 3 и берем сначала в множитель р1 умножить на (1 - р2)*(1 - р3) и т.д.)
2 успеха - вероятность р1*р2*(1 - р3) + р1*(1 - р2)*р3 + (1 - р1)*р2*р3 (т.е. мы проходим все сочетания из 3-х по 2-м, а это 12, 13 и 23 и берем сначала в множитель р1 умножить на р2 и (1 - р3) и т.д.)
3 успеха - р1*р2*р3
Т.е. в теории все не так сложно. Я реализовал этот алгоритм, что называется в лоб, на С.
 
Код: plaintext
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.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
#include <stdio.h>
#include <stdlib.h>

void Fastc(double *p, int N);

int main(){
   int N =  3 ;
    double p[ 3 ];
    p[ 0 ] =  0 . 1 ;
    p[ 1 ] =  0 . 8 ;
    p[ 2 ] =  0 . 5 ;
    Fastc (p, N);
	return  0 ;
}

void Fastc(double *p, int N){
    int l, s, *count;
    int i, k, nextk, stp;
    double prod, sprod;
    count = (int *)malloc(N * sizeof(int));
    for (l =  0 ; l < N -  1 ; l++){
        printf("l = %d\n",l);
        for(i =  0 ; i < N; i++){
            count[i] = i;
            printf("count = %d\n",count[i]);
        }
        stp =  1 ;
        sprod =  0 . 0 ;
        while ( 1  ==  1 ){
            for(i =  1 ; i < (l +  1 ); i++){
                if (count[i] >= N - ((l +  1 ) -  1  - i)) count[i] = count[i -  1 ] +  1 ;
            }
            for (i =  0 ; i < (l +  1 ); i++){
                if (count[i] >= N){stp =  0 ; break;}
            }
            if(stp ==  0 ) break;
            for(i =  0 ; i < (l +  1 ); i++){
                count[i]++;
            }
            prod =  1 ;
            for(k =  0 ; k < N; k++){
                nextk =  0 ;
                for(s =  0 ; s < (l +  1 ); s++){
                    if(count[s] == k +  1 ){
                        prod *= p[k];
                        nextk =  1 ;
                        break;
                    }
                }
                if(nextk ==  0 ) {prod *= ( 1  - p[k]);}
            }
            sprod += prod;
            for(i =  0 ; i < (l +  1 ); i++){
                count[i]--;
            }
            count[(l +  1 ) -  1 ]++;
            for (i = (l +  1 ) -  1 ; i >=  1 ; i--){
                if (count[i] >= N - ((l +  1 ) -  1  - i)) count[i -  1 ]++;
            }
        }
        printf("%f\n",sprod);
    }
    free(count);
}


Однако, если мы имеем дело с 30-ю и более испытаниями, данный алгоритм "задумывается" на очень длительное время, т.к., к примеру число комбинаций только из 30-ти по 15-ть равно 155117520! Пока он их все переберет...
Поэтому, ищу другие способы реализации. Наткнулся на такое. Эти вероятности можно представить как коэффициенты полинома, получающиеся если разложить произведение от 1 до n (рk*x - (1 - pk)) в сумму от 0 до n Рk*x^k, где коэффициенты Pk этого полинома и будут искомыми вероятностями, начиная с хвоста....
Теперь встает вопрос, как вычислять эти коэффициенты. Я знаю, что есть алгоритм восстановления полинома, имея его корни, но нигде не могу найти его реализацию. В данном случае мы таки имеем все корни - это дроби вида -(1 - pk)/pk, k от 1-го до n. Может кто знает, как это реализовать и с помощью какого языка программирования?
...
Рейтинг: 0 / 0
10.12.2010, 23:23
| Ответить | Цитировать | Написать  
Теория вероятности. функция распределения для Пуассон-Биномиального распределения
    #37008809
Kew
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Kew
Участник
Реализуйте операцию умножения полинома на бином:

(A k x k + A k-1 x k-1 + ... + A 0 x 0 )(B 1 x 1 + B 0 x 0 ) =
A k B 1 x k+1 + (A k B 0 + A k-1 B 1 )x k + (A k-1 B 0 + A k-2 B 1 )x k-1 + ... + A 0 B 0

И перемножьте биномы. Сложность квадратичная
...
Рейтинг: 0 / 0
11.12.2010, 13:51
| Ответить | Цитировать | Написать  
Теория вероятности. функция распределения для Пуассон-Биномиального распределения
    #37009814
Диклевич Александр
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Диклевич Александр
Участник
Если кому интересно, на С работает так
Код: plaintext
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.
29.
30.
31.
32.
33.
34.
35.
36.
#include <stdio.h>
#include <stdlib.h>
int main(){
    int n =  6 , l =  2 , i, j;
    double p[n], k[n], A[n +  1 ], X[n +  1 ], prod =  1 . 0 ;
    p[ 0 ] =  0 . 1 ;
    p[ 1 ] =  0 . 8 ;
    p[ 2 ] =  0 . 5 ;
    p[ 3 ] =  0 . 1 ;
    p[ 4 ] =  0 . 8 ;
    p[ 5 ] =  0 . 5 ;
	for(i =  0 ; i < n +  1 ; i++){
		X[i] =  0 ;
	}
	for(i =  0 ; i < n; i++){
	    prod *= p[i];
		k[i] = - ( 1  - p[i]) / p[i];
	}
	A[ 0 ] = -k[ 0 ];
	A[ 1 ] =  1 ;
	for (i =  1 ; i < n; i++){
		for (j =  0 ; j < l; j++){
			X[j] += -A[j] * k[i];
			X[j +  1 ] += A[j];
		}
		l++;
		for (j =  0 ; j < l; j++){
			A[j] = X[j];
			X[j] =  0 ;
		}
	}
    for (i = l -  1 ; i >=  0 ; i--){
        A[i] *= prod;
        printf("A[%d]=%lf\n", i, A[i]);
    }
    return  0 ;
}
для больших значений n (порядка десятка тысяч) лучше использовать тип long double.
...
Рейтинг: 0 / 0
12.12.2010, 15:09
| Ответить | Цитировать | Написать  
Теория вероятности. функция распределения для Пуассон-Биномиального распределения
    #37009838
Фотография AndreTM
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AndreTM
Участник
Да-а...
Вот когда мне не стало хватать любого _точного_ вычисления, я решил его реализовать напрямую.
Скажем, 1000!
Очень просто реализуется, если иметь прямой доступ к EAX и EBP без ASMа, но средствами языка.
Догадайтесь, - для этого я выбрал .NET, C# или что-то ещё?
А вы тут про VB...
...
Рейтинг: 0 / 0
12.12.2010, 15:38
| Ответить | Цитировать | Написать  
Теория вероятности. функция распределения для Пуассон-Биномиального распределения
    #37009840
Фотография AndreTM
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AndreTM
Участник
Торможу, про C# был неправ...
C++, впрочем, тоже не показатель.
...
Рейтинг: 0 / 0
12.12.2010, 15:40
| Ответить | Цитировать | Написать  
Теория вероятности. функция распределения для Пуассон-Биномиального распределения
    #37009901
Kew
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Kew
Участник
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
 4023872600770937735437024339230039857193748642107146325437999104299385123986290205920442084869694048004799886101971960586316668729948085589013238296699445909974 
 2450408707375991882362772718873251977950595099527612087497546249704360141827809464649629105639388743788648733711918104582578364784997701247663288983595573543251 
 3185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308 
 4313928444032812315586110369768013573042161687476096758713483120254785893207671691324484262361314125087802080002616831510273418279777047846358681701643650241536 
 9139828126481021309276124489635992870511496497541990934222156683257208082133318611681155361583654698404670897560290095053761647584772842188967964624494516076535 
 3408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545 
 2572238655414610628921879602238389714760885062768629671466746975629112340824392081601537808898939645182632436716167621791689097799119037540312746222899880051954 
 4441428201218736174599264295658174662830295557029902432415318161721046583203678690611726015878352075151628422554026517048330422614397428693306169089796848259012 
 5458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301 
 4356945272242063446317974605946825731037900840244324384656572450144028218852524709351906209290231364932734975655139587205596542287497740114133469627154228458623 
 7738753823048386568897646192738381490014076731044664025989949022222176590433990188601856652648506179970235619389701786004081188972991831102117122984590164192106 
 8884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290 
 1534830776445690990731524332782882698646027898643211390835062170950025973898635542771967428222487575867657523442202075736305694988250879689281627538488633969099 
 5982628095612145099487170124451646126037902930912088908694202851064018215439945715680594187274899809425474217358240106367740459574178516082923013535808184009699 
 6372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000 
 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 
00000000L
[src]
4023872600770937735437024339230039857193748642107146325437999104299385123986290205920442084869694048004799886101971960586316668729948085589013238296699445909974
2450408707375991882362772718873251977950595099527612087497546249704360141827809464649629105639388743788648733711918104582578364784997701247663288983595573543251
3185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308
4313928444032812315586110369768013573042161687476096758713483120254785893207671691324484262361314125087802080002616831510273418279777047846358681701643650241536
9139828126481021309276124489635992870511496497541990934222156683257208082133318611681155361583654698404670897560290095053761647584772842188967964624494516076535
3408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545
2572238655414610628921879602238389714760885062768629671466746975629112340824392081601537808898939645182632436716167621791689097799119037540312746222899880051954
4441428201218736174599264295658174662830295557029902432415318161721046583203678690611726015878352075151628422554026517048330422614397428693306169089796848259012
5458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301
4356945272242063446317974605946825731037900840244324384656572450144028218852524709351906209290231364932734975655139587205596542287497740114133469627154228458623
7738753823048386568897646192738381490014076731044664025989949022222176590433990188601856652648506179970235619389701786004081188972991831102117122984590164192106
8884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290
1534830776445690990731524332782882698646027898643211390835062170950025973898635542771967428222487575867657523442202075736305694988250879689281627538488633969099
5982628095612145099487170124451646126037902930912088908694202851064018215439945715680594187274899809425474217358240106367740459574178516082923013535808184009699
6372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000L
[/src]?
:)
...
Рейтинг: 0 / 0
12.12.2010, 16:28
| Ответить | Цитировать | Написать  
Теория вероятности. функция распределения для Пуассон-Биномиального распределения
    #37009911
Kew
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Kew
Участник
!?!?
Какой-то глюк :)
Исходный код:
[SRC python]
def fact(n):
return reduce(lambda i,j: i*j, range(1,n+1))

fact(1000)
[/SRC]
...
Рейтинг: 0 / 0
12.12.2010, 16:34
| Ответить | Цитировать | Написать  
Теория вероятности. функция распределения для Пуассон-Биномиального распределения
    #37009917
Фотография AndreTM
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AndreTM
Участник
Kew,

один вопрос - тайминг скорости, плиз...

Поскольку Forth (реализации в пределах -83) смог посчитать то же самое на ASUS P5QL + E5400 всего за 117.3 c
...
Рейтинг: 0 / 0
12.12.2010, 16:38
| Ответить | Цитировать | Написать  
Теория вероятности. функция распределения для Пуассон-Биномиального распределения
    #37009922
Фотография AndreTM
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AndreTM
Участник
И я попробую реализовать заточенный под факториал метод - тогда точно никакой Си его не сможет перекрыть.
Выложу сюда, не поленюсь...
...
Рейтинг: 0 / 0
12.12.2010, 16:40
| Ответить | Цитировать | Написать  
Теория вероятности. функция распределения для Пуассон-Биномиального распределения
    #37009942
Kew
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Kew
Участник
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
import time

def fact(n):
	return reduce(lambda i,j: i*j, range( 1 ,n+ 1 ))

def howfast():
    t1 = time.time()
    for i in range( 10000 ):
        tt = fact( 1000 )
    t2 = time.time()
    return (t2-t1)/ 10000 . 0 

print howfast()
Код: plaintext
1.
 0 . 00100620000362
Это в секундах на 1 факториал
...
Рейтинг: 0 / 0
12.12.2010, 16:56
| Ответить | Цитировать | Написать  
Теория вероятности. функция распределения для Пуассон-Биномиального распределения
    #37010155
Диклевич Александр
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Диклевич Александр
Участник
Все что после моего последнего сообщения - это о чем?
...
Рейтинг: 0 / 0
12.12.2010, 20:38
| Ответить | Цитировать | Написать  
11 сообщений из 11, страница 1 из 1
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Теория вероятности. функция распределения для Пуассон-Биномиального распределения
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&fpage=93&tid=1343260]:
 0ms
get settings:
 6ms
get forum list:
 12ms
check forum access:
 2ms
check topic access:
 2ms
track hit:
 58ms
get topic data:
 7ms
get forum data:
 2ms
get page messages:
 30ms
get tp. blocked users:
 1ms
others: 191ms
total:  311ms
созд. / загр.: 311ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]