/ Forside / Karriere / Uddannelse / Højere uddannelser / Nyhedsindlæg
Login
Glemt dit kodeord?
Brugernavn

Kodeord


Reklame
Top 10 brugere
Højere uddannelser
#NavnPoint
Nordsted1 1588
erling_l 1224
ans 1150
dova 895
gert_h 800
molokyle 661
berpox 610
creamygirl 610
3773 570
10  jomfruane 570
Sandsynlighedssjov
Fra : neckelmann@gmail.com


Dato : 28-11-07 04:37

Hej,

jeg har et problem som jeg har spekuleret over, som jeg håber der er
nogen der kan hjælpe med.

Jeg har et antal bits.

Hver af disse bits har en fast sandsynlighed for at være "høj", ellers
er den "lav". Det er ikke den samme sandsynlighed for hver bit.

Jeg vil gerne bestemme sandsynligheden for at X eller flere af disse
bits er høje.

Det er nemt nok hvis antallet af bits er lille... så kan jeg bare tage
hele udfaldsrummet, og for hvert udfald udregne sandsynligheden - og
hvis udfaldet opfylder min betingelse (X eller flere høje bits), så
summere til en samlet sandsynlighed.

Men hva gør jeg hvis der er mange bits? F.eks. 50... kan af gode
grunde ikke behandle hvert enkelt udfald når der er 2^50 af dem :)

Er der en smart sandsynlighedsregneregel jeg kan bruge?

På forhånd tak...

--
mvh Rasmus Neckelmann

 
 
Bertel Lund Hansen (28-11-2007)
Kommentar
Fra : Bertel Lund Hansen


Dato : 28-11-07 13:09

neckelmann@gmail.com skrev:

> Hver af disse bits har en fast sandsynlighed for at være "høj", ellers
> er den "lav".

Er disse sandsynligheder kendte?

--
Bertel
http://bertel.lundhansen.dk/   FIDUSO: http://fiduso.dk/

neckelmann@gmail.com (28-11-2007)
Kommentar
Fra : neckelmann@gmail.com


Dato : 28-11-07 06:56

On 28 Nov., 13:09, Bertel Lund Hansen <unosp...@lundhansen.dk> wrote:
> neckelm...@gmail.com skrev:
>
> > Hver af disse bits har en fast sandsynlighed for at være "høj", ellers
> > er den "lav".
>
> Er disse sandsynligheder kendte?

Jep, de er kendte.

--
mvh Rasmus Neckelmann

Martin Larsen (28-11-2007)
Kommentar
Fra : Martin Larsen


Dato : 28-11-07 16:19

<neckelmann@gmail.com> skrev i meddelelsen
news:baf7325e-4db1-4d09-81e4-29eeec8d9b08@w40g2000hsb.googlegroups.com...
On 28 Nov., 13:09, Bertel Lund Hansen <unosp...@lundhansen.dk> wrote:
> neckelm...@gmail.com skrev:
>
> > Hver af disse bits har en fast sandsynlighed for at være "høj", ellers
> > er den "lav".
>
> Er disse sandsynligheder kendte?

Jep, de er kendte.

--------------

Du kan for store N benytte at binomialfordelingen nærmer sig den normale
fordeling med parametre Np og sqrt(Np(1-p))

Mvh
Martin


Martin Larsen (29-11-2007)
Kommentar
Fra : Martin Larsen


Dato : 29-11-07 04:32

<neckelmann@gmail.com> skrev i meddelelsen
news:baf7325e-4db1-4d09-81e4-29eeec8d9b08@w40g2000hsb.googlegroups.com...
On 28 Nov., 13:09, Bertel Lund Hansen <unosp...@lundhansen.dk> wrote:
> neckelm...@gmail.com skrev:
>
> > Hver af disse bits har en fast sandsynlighed for at være "høj", ellers
> > er den "lav".
>
> Er disse sandsynligheder kendte?

Jep, de er kendte.


------

Hvis dine sandsynligheder ikke er ens for hver bit, så er her en formel hvor
SP står for at summere alle (n, k+j) kombinationer af produkter af k+j
sandsynligheder og n det samlede antal bits og k antal "on". (SP(n, 0) = 1).

Sum[j=0, n-k] {(-1)^j * binomial(k+j, k) * SP(n, k+j)}

Mvh
Martin


Martin Larsen (29-11-2007)
Kommentar
Fra : Martin Larsen


Dato : 29-11-07 17:08

"Martin Larsen" <mlarsen@post7.tele.dk> skrev i meddelelsen
news:474e32ac$0$15888$edfadb0f@dtext01.news.tele.dk...
> <neckelmann@gmail.com> skrev i meddelelsen
> news:baf7325e-4db1-4d09-81e4-29eeec8d9b08@w40g2000hsb.googlegroups.com...
> On 28 Nov., 13:09, Bertel Lund Hansen <unosp...@lundhansen.dk> wrote:
>> neckelm...@gmail.com skrev:
>>
>> > Hver af disse bits har en fast sandsynlighed for at være "høj", ellers
>> > er den "lav".
>>
>> Er disse sandsynligheder kendte?
>
> Jep, de er kendte.
>
>
> ------
>
> Hvis dine sandsynligheder ikke er ens for hver bit, så er her en formel
> hvor SP står for at summere alle (n, k+j) kombinationer af produkter af
> k+j sandsynligheder og n det samlede antal bits og k antal "on". (SP(n, 0)
> = 1).
>
> Sum[j=0, n-k] {(-1)^j * binomial(k+j, k) * SP(n, k+j)}

Man ser naturligvis straks at SP(n, k+j) er elementære symmetriske
polynomier i p_n, og kan fås som koefficient til x^(n-k-j) i
prod[i=1,n]{x+p_i)} (som tabuleres en gang for alle).

Mvh
Martin


Torben Ægidius Mogen~ (28-11-2007)
Kommentar
Fra : Torben Ægidius Mogen~


Dato : 28-11-07 17:41

neckelmann@gmail.com writes:

> Hej,
>
> jeg har et problem som jeg har spekuleret over, som jeg håber der er
> nogen der kan hjælpe med.
>
> Jeg har et antal bits.
>
> Hver af disse bits har en fast sandsynlighed for at være "høj", ellers
> er den "lav". Det er ikke den samme sandsynlighed for hver bit.
>
> Jeg vil gerne bestemme sandsynligheden for at X eller flere af disse
> bits er høje.
>
> Det er nemt nok hvis antallet af bits er lille... så kan jeg bare tage
> hele udfaldsrummet, og for hvert udfald udregne sandsynligheden - og
> hvis udfaldet opfylder min betingelse (X eller flere høje bits), så
> summere til en samlet sandsynlighed.
>
> Men hva gør jeg hvis der er mange bits? F.eks. 50... kan af gode
> grunde ikke behandle hvert enkelt udfald når der er 2^50 af dem :)
>
> Er der en smart sandsynlighedsregneregel jeg kan bruge?

Lad os se. Lad os kalde sandsynligheden for, at bit i er 1 for p_i.
Sandsynligheden for, at alle n bits er 1 er altså p_1*...*p_n, og
sandsynligheden for at ingen er 1 er (1-p_1)*...*(1-p_n).

Vi kan rekursivt skrive sandsynlighedsfunktionen p(m,k) for at præcis
m af de første k bits er 1:

p(0,0) = 1
p(m,k) = 0, hvis k<m
p(m,k) = p(m-1,k-1)*p_k + p(m,k-1)*(1-p_k), hvis k>=m

Vi kan nu lave en tabel p[m,k] for p(m,k). Vi starter med at udfylde
de ikke-rekursive tilfælde (de to første regler). Dernæst kan vi
fylde resten ud i en løkke:

for m:=0 to n do
for k:=m to n do
p[m,k] := p[m-1,k-1]*p_k + p[m,k-1]*(1-p_k)

Rækkefølgen betyder, at vi kun bruger tabelelementer, som allerede er
defineret. Det samlede tidsforbrug er kvadratisk i n.

Nu kan vi beregne sandsynligheden for at mindst j ud af de n bits er 1
som summen for m = j til n af p(m,n).

   Torben

neckelmann@gmail.com (30-11-2007)
Kommentar
Fra : neckelmann@gmail.com


Dato : 30-11-07 05:31

Tak alle sammen, vil prøve at se om jeg kan hitte ud af at
implementere det nu :)

--
mvh Rasmus Neckelmann

Martin Larsen (30-11-2007)
Kommentar
Fra : Martin Larsen


Dato : 30-11-07 16:10

<neckelmann@gmail.com> skrev i meddelelsen
news:1a7ac1ec-8261-444c-880b-bd02fccd951e@j20g2000hsi.googlegroups.com...
Tak alle sammen, vil prøve at se om jeg kan hitte ud af at
implementere det nu :)

---

Bemærk at binomialkoefficienter, der itereres ikke kræver større udregning.
I dette tilfælde er det Pascals 8. lighed, og du kan sige b_0 = 1, b =
b*(k/j+1), eller når du indrager alternerende fortegn b = -b*(k/j+1).

(Jeg har iøvrigt lige testet at formlen ser ud til at virke)

Mvh
Martin


Søg
Reklame
Statistik
Spørgsmål : 177552
Tips : 31968
Nyheder : 719565
Indlæg : 6408849
Brugere : 218887

Månedens bedste
Årets bedste
Sidste års bedste