---

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

---

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/

---

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

---

<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

---

<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" <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

---

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

---

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

--
mvh Rasmus Neckelmann

---

<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