Suma współczynników rozkładu wielomianowego

10

Rzucam sprawiedliwą kostką. Ilekroć dostaję 1, 2 lub 3, zapisuję „1”; za każdym razem, gdy dostaję 4, zapisuję „2”; za każdym razem, gdy dostaję 5 lub 6, zapisuję „3”.

Niech będzie całkowitą liczbą rzutów, których potrzebuję, aby iloczyn wszystkich zapisanych przeze mnie liczb wynosił \ geq 100000 . Chcę obliczyć (lub w przybliżeniu) \ P (N \ geq 25) , a przybliżenie można podać jako funkcję rozkładu normalnego.100000 P ( N 25 )N100000P(N25)

Po pierwsze wiem, że P(N11)=1 ponieważ log3100.00010.48 . A teraz, niech a , b i c będą liczbą zapisanych odpowiednio 1, 2 i 3. Następnie:

P(a,b,cn)={(na,b,c)(12)a(16)b(13)c if a+b+c=n0 otherwise

Co chcę obliczyć to:

P(a+b+c252b3c100000)

Jak to obliczyć?

--EDYTOWAĆ:

Zasugerowano więc, że mogę zastąpić warunek:

P(a+b+c25αa+βb+γcδ)

gdzie , , , a .α=0β=log2γ=log3δ=log100000

To wygląda bardziej rozwiązalne! Niestety nie mam pojęcia, jak to rozwiązać.

Pedro Carvalho
źródło
2
+1 Ten problem może wydawać się nieco bardziej znany i bardziej oczywisty, że przydałby się w przybliżeniu do rozwiązań, gdybyś napisał warunek w postaci gdzie i . α = 0 , β = log ( 2 ) , γ = log ( 3 ) , δ = log ( 100000 )αa+βb+γcδα=0,β=log(2),γ=log(3),δ=log(100000)
whuber
Dodałem ten nowy sposób napisania warunku, ale niestety wciąż nie mam bladego pojęcia, jak to rozwiązać!
Pedro Carvalho,
Inna wskazówka jest taka, że ​​jeśli wystąpi wystąpień „2”, to przestaniesz. Więc możesz to przybliżyć za pomocą ujemnego dwumianu o parametrach i (także przy i ). Dokładna odpowiedź jest również wykonalna, ponieważ nie ma wielu kombinacji. Ponadto warunek nie jest dokładny - należy załączyć, że „2” lub „3” zostały zapisane na tym rzucie17 0,5 11 1 / 3 N17170.5111/3N
prawdopodobieństwo

Odpowiedzi:

1

Niniejsze pytanie jest szczególnym przypadkiem, w którym mamy do czynienia z wielkością, która jest funkcją liniową wielomianowej zmiennej losowej. Możliwe jest dokładne rozwiązanie problemu poprzez wyliczenie kombinacji wielomianowych, które spełniają wymaganą nierówność, i zsumowanie rozkładu w tym zakresie. W przypadku, gdy jest duży, może to stać się niewykonalne obliczeniowo. W takim przypadku możliwe jest uzyskanie przybliżonego rozkładu przy użyciu normalnego przybliżenia do wielomianu. Uogólniona wersja tego przybliżenia jest pokazana poniżej, a następnie jest stosowana do konkretnego przykładu.N


Ogólny problem aproksymacyjny: Załóżmy, że mamy ciąg wymiennych zmiennych losowych o zakresie . Dla dowolnego możemy utworzyć wektor liczenia , który liczy liczbę wystąpienia każdego wyniku w pierwszych wartościach sekwencji. Ponieważ sekwencja leżąca u podstaw jest wymienna, wektor zliczania jest dystrybuowany jako:n N X X ( n ) ( X 1 , X 2 , . . . , X m ) N1,2,...,mnNXX(n)(X1,X2,...,Xm)n

X ~ Mu(n,θ)θ=limnX(n)/n.

Załóżmy teraz, że mamy jakiś wektor nieujemnych wag i używamy tych wag do zdefiniowania funkcji liniowej:w=(w1,w2,...,wm)

A(n)i=1mwiXi.

Ponieważ wagi nie są ujemne, ta nowa ilość nie zmniejsza się w . Następnie definiujemy liczbę , która jest najmniejszą liczbę obserwacji wymagane do uzyskania określonej minimalnej wartości naszym funkcją liniową. Chcemy aproksymować rozkład w przypadku, gdy ta wartość jest (stochastycznie) duża.N ( a ) min { n N | A ( n ) a } N ( a )nN(a)min{nN|A(n)a}N(a)


Rozwiązywanie ogólnego problemu aproksymacji: Po pierwsze, zauważamy, że ponieważ nie zmniejsza się w (co jest ważne, ponieważ przyjęliśmy, że wszystkie wagi są nieujemne), mamy:nA(n)n

P(N(a)n)=P(N(a)>n1)=P(A(n1)<a).

W związku z tym, rozmieszczenie jest bezpośrednio związane z podziałem . Zakładając, że pierwsza wielkość jest duża, możemy w przybliżeniu rozmieścić tę drugą, zastępując dyskretny losowy wektor ciągłym przybliżeniem z wielowymiarowego rozkładu normalnego. Prowadzi to do normalnego przybliżenia kwantyfikacji liniowej i możemy bezpośrednio obliczyć momenty tej wielkości. W tym celu wykorzystujemy fakt, że , i dla . W przypadku podstawowej algebry daje to nam:A X A ( n ) E ( X i ) = n θ i V ( X i ) = n θ i ( 1 - θ i ) C ( X i , X j ) = - n θ i θ j i jNAXA(n)E(Xi)=nθiV(Xi)=nθi(1θi)C(Xi,Xj)=nθiθjij

μE(1nA(n))=i=1mwiθi,

σ2V(1nA(n))=i=1mwiθi(i=1mwiθi)2=μ(1μ).

Przyjęcie normalnego przybliżenia do wielomianu daje nam teraz przybliżony rozkład . Zastosowanie tego przybliżenia daje:A(n) ~ N(nμ,nμ(1μ))

P.(N.(za)n)=P.(ZA(n-1)<za)Φ(za-(n-1)μ(n-1)μ(1-μ)).

(Symbol jest standardowym oznaczeniem standardowej funkcji rozkładu normalnego.) Można zastosować to przybliżenie, aby znaleźć prawdopodobieństwa dotyczące wielkości dla określonej wartości . Jest to podstawowe przybliżenie, które nie próbowało uwzględnić korekty ciągłości wartości leżących u podstaw wartości liczby wielomianowej. Uzyskuje się to przez przyjęcie normalnego przybliżenia przy użyciu tych samych pierwszych dwóch centralnych momentów, co dokładna funkcja liniowa.N ( a ) aΦN.(za)za


Zastosowanie do twojego problemu: W twoim problemie masz prawdopodobieństwa , wagi , a wartość odcięcia . Masz zatem (zaokrąglając do sześciu miejsc po przecinku) . Stosując powyższe przybliżenie mamy (zaokrąglając do sześciu miejsc po przecinku):w=(0,ln2,ln3)a=ln100000μ=1θ=(12),16,13))w=(0,ln2,ln3)a=ln100000μ=16ln2+13ln3=0.481729

P(N(a)25)Φ(ln100000240.481729240.499666)=Φ(0.019838)=0.492086.

Stosując dokładny rozkład wielomianowy, sumując wszystkie kombinacje spełniające wymaganie , można wykazać, że dokładny wynik to . Stąd widzimy, że przybliżenie jest dość zbliżone do dokładnej odpowiedzi w niniejszej sprawie.P(A(24)<a)P(N(a)25)=0.483500

Mam nadzieję, że ta odpowiedź daje odpowiedź na konkretne pytanie, jednocześnie umieszczając ją w bardziej ogólnych ramach wyników probabilistycznych, które dotyczą funkcji liniowych wielomianowych wektorów losowych. Niniejsza metoda powinna pozwolić na uzyskanie przybliżonych rozwiązań problemów ogólnego rodzaju, z którymi się mierzysz, umożliwiając zróżnicowanie konkretnych liczb w twoim przykładzie.

Ben - Przywróć Monikę
źródło
0

Zróbmy normalne przybliżenie.

Najpierw przepiszmy całkowicie twój problem w logach. Zaczynasz od 0 w czasie t = 0. Następnie na każdym kroku dodajesz:

  • 0 z prawdopodobieństwem 1/2

  • log(2) z prawdopodobieństwem 1/6

  • log(3) z prawdopodobieństwem 1/3

Zatrzymujesz ten proces, gdy twoja suma przekroczy w którym momencie patrzysz, ile wykonałeś rzutów. Liczba rzutów, które zajęło ci dotarcie do tego punktu, to ^log(105)N

Mój kalkulator mówi mi, że średnia twoich przyrostów wynosi:0.48 a wariancja wynosi . Dla porównania punkt końcowy to więc dotrzemy do niego w około 24 krokach0.2511.51

Zależnie od tego, że wykonaliśmy 25 kroków, rozkład sumy jest w przybliżeniu gaussowskim wyśrodkowanym na 12,0 i z wariancją 6,25. To daje nam przybliżone Gaussowskie przybliżeniep(N25)0.5

Trzeba spojrzeć na kumulanty sumy przy N = 25, aby wiedzieć, czy przybliżenie Gaussa jest w porządku. Biorąc pod uwagę, że przyrosty nie są symetryczne, wartość przybliżona może nie być najlepsza

Guillaume Dehaene
źródło
1
Czy możesz dla mnie ukończyć wyprowadzenie? Trudno mi to zobaczyć. Ponadto, czy nie ma dokładnego sposobu, aby to obliczyć?
Pedro Carvalho
1
Czy nie masz na myśli „log (2)” i „log (3)”, gdzie masz log (1) i log (2)?
Glen_b
@GuillaumeDehaene napisał: .... Według moich obliczeń, na dwa różne sposoby, co jest bardzo różne od 0,5p(N25)0.5P(N25)=1P(N24)=1112729185663307164998372267786240.8266
wilki
jak uzyskać P (n \ leq24) \ około 0,18?
Guillaume Dehaene