Suma współczynników rozkładu wielomianowego

$\newcommand{\P}{\mathbb{P}}$ 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 $N$$\geq 100000$$\P(N\geq 25)$

Po pierwsze wiem, że $\P(N\geq 11) = 1$ ponieważ $\log_3 100.000 \approx 10.48$ . A teraz, niech $a$ , $b$ i $c$ będą liczbą zapisanych odpowiednio 1, 2 i 3. Następnie:

$$\P(a,b,c\mid n) = \begin{cases}\displaystyle\binom {n}{a, b, c} \left(\frac 1 2\right) ^ a \left(\frac 1 6\right)^b\left(\frac 1 3\right)^c &\text{ if } a + b + c = n \\ 0 &\text{ otherwise}\end{cases}$$

Co chcę obliczyć to:

$$\P(a + b + c \geq 25 \mid 2^b3^c\geq 100000)$$

Jak to obliczyć?

--EDYTOWAĆ:

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

$$\P(a + b + c \geq 25 \mid \alpha a + \beta b + \gamma c \geq \delta)$$

gdzie , , , a .$\alpha = 0$$\beta = \log 2$$\gamma = \log 3$$\delta = \log 100000$

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

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 ) $1, 2, ..., m$$n \in \mathbb{N}$$\boldsymbol{X} \equiv \boldsymbol{X} (n) \equiv (X_1, X_2, ..., X_m)$$n$

$$\begin{array} \boldsymbol{X} \text{ ~ Mu}(n, \boldsymbol{\theta}) & & \boldsymbol{\theta} = \lim_{n \rightarrow \infty} \boldsymbol{X}(n)/n. \end{array}$$

Załóżmy teraz, że mamy jakiś wektor nieujemnych wag i używamy tych wag do zdefiniowania funkcji liniowej:$\boldsymbol{w} = (w_1, w_2, ..., w_m)$

$$A(n) \equiv \sum_{i=1}^m w_i X_i.$$

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 $n$$N(a) \equiv \min \{ n \in \mathbb{N} | A(n) \geqslant 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:$A(n)$$n$

$$\mathbb{P} (N(a) \geqslant n) = \mathbb{P} (N(a) > n - 1) = \mathbb{P} (A(n-1) < 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 ≠ $N$$A$$\boldsymbol{X}$$A(n)$$\mathbb{E}(X_i) = n \theta_i$$\mathbb{V}(X_i) = n \theta_i (1 - \theta_i)$$\mathbb{C}(X_i, X_j) = -n \theta_i \theta_j$$i \neq j$

$$\mu \equiv \mathbb{E}\left(\frac{1}{n} A(n)\right) = \sum_{i=1}^m w_i \theta_i,$$

$$\sigma^2 \equiv \mathbb{V}\left(\frac{1}{\sqrt{n}} A(n)\right) = \sum_{i=1}^m w_i \theta_i - \left(\sum_{i=1}^m w_i \theta_i\right)^2 = \mu (1 - \mu).$$

Przyjęcie normalnego przybliżenia do wielomianu daje nam teraz przybliżony rozkład . Zastosowanie tego przybliżenia daje:$A(n) \text{ ~ N} (n \mu, n \mu (1 - \mu))$

$$\mathbb{P} (N(a) \geqslant n) = \mathbb{P} (A(n-1) < a) \approx \Phi \left(\frac{a - (n-1) \mu}{\sqrt{(n-1) \mu (1 - \mu)}}\right).$$

(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 ) $\Phi$$N(a)$$a$

---

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μ=$\boldsymbol{\theta} = (\tfrac{1}{2}, \tfrac{1}{6}, \tfrac{1}{3})$$\boldsymbol{w} = (0, \ln 2, \ln 3)$$a = \ln 100000$$\mu = \tfrac{1}{6}\ln 2 + \tfrac{1}{3}\ln 3 = 0.481729$

$$\mathbb{P}(N(a) \geqslant 25) \approx \Phi \left(\frac{\ln 100000 - 24 \cdot 0.481729}{\sqrt{24} \cdot 0.499666}\right) =\Phi (-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.$\mathbb{P}(A(24) < a)$$\mathbb{P}(N(a) \geqslant 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.

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(10^5)$$N$

Mój kalkulator mówi mi, że średnia twoich przyrostów wynosi:$\approx 0.48$ a wariancja wynosi . Dla porównania punkt końcowy to więc dotrzemy do niego w około 24 krokach$\approx 0.25$$\approx 11.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żenie$p(N\geq25)\approx 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