Jak nazywałem się ten rozkład dyskretny (równanie różnicy rekurencyjnej)?

Natknąłem się na tę dystrybucję w grze komputerowej i chciałem dowiedzieć się więcej o jej zachowaniu. To zależy od decyzji, czy określone zdarzenie powinno nastąpić po określonej liczbie akcji gracza. Szczegóły poza tym nie są istotne. Wydaje się, że ma zastosowanie w innych sytuacjach, i uważam to za interesujące, ponieważ jest łatwe do obliczenia i tworzy długi ogon.

Na każdym kroku gra generuje jednolitą liczbę losową . Jeśli , zdarzenie jest wyzwalane. Po wystąpieniu zdarzenia gra resetuje i ponownie przechodzi przez sekwencję. Interesuje mnie tylko jedno wystąpienie zdarzenia dotyczącego tego problemu, ponieważ reprezentuje ono dystrybucję używaną przez grę. (Na wszelkie pytania dotyczące wielu wystąpień można odpowiedzieć za pomocą jednego modelu wystąpienia). $n$ $0 \leq X < 1$ $X < p(n)$ $n = 0$

Główną „nienormalnością” jest tutaj to, że parametr prawdopodobieństwa w tym rozkładzie zwiększa się z czasem lub, innymi słowy, próg rośnie z czasem. W tym przykładzie zmienia się liniowo, ale przypuszczam, że mogą obowiązywać inne reguły. Po krokach lub czynnościach użytkownika $n$

p (n) = k n

$p(n) = kn$

dla niektórych stałych . W pewnym momencie otrzymujemy . Zdarzenie jest po prostu gwarantowane na tym etapie. $0 < k < 1$ $n_{\max}$ $p(n_{\max}) \geq 1$

Byłem w stanie to ustalić

f (n) = p (n) [1 - F (n - 1)]

$f(n) = p(n)\left[1 - F(n - 1)\right]$ i dla PMF i CDF . W skrócie, prawdopodobieństwo, że zdarzenie zajmie ty stopień, jest równe prawdopodobieństwu , pomniejszonemu o prawdopodobieństwo, że zdarzyło się to już na którymkolwiek poprzednim etapie.

F (n) = p (n) + F (n - 1) [1 - p (n)]

$F(n) = p(n) + F(n-1)\left[1 - p(n)\right]$

f (n)

$f(n)$

F (n)

$F(n)$

n

$n$

p (n)

$p(n)$

Oto fabuła naszego przyjaciela Monte Carlo, dla zabawy, z . Mediana osiąga wartość 21, a średnia wynosi 22. $k \approx 0.003$ wprowadź opis zdjęcia tutaj

Jest to zasadniczo równoznaczne z równaniem różnicy pierwszego rzędu z cyfrowego przetwarzania sygnału, które jest moim tłem, więc odkryłem, że jest to całkiem nowe. Intryguje mnie również to, że może się różnić zgodnie z dowolną dowolną formułą. $p(n)$

Moje pytania:

Jak nazywa się ta dystrybucja, jeśli ją posiada?
Czy istnieje sposób uzyskania wyrażenia dla bez odniesienia do ? $f(n)$ $F(n)$
Czy istnieją inne przykłady takich dyskretnych rozkładów rekurencyjnych?

Edycje Wyjaśniono proces dotyczący generowania liczb losowych.

— jbarlow
źródło

Czy jest jakiś powód, dla którego wybrałeś nawiasy kwadratowe zamiast ()?

— Cam.Davidson.Pilon

@ Cam.Davidson.Pilon: Moje tło DSP wślizgnęło się. Zazwyczaj używamy nawiasów kwadratowych do dyskretnych funkcji czasowych. Myślę, że to musi być denerwujące, więc to zmienię.

— jbarlow

Proces, który zakładasz, nie wydaje się tutaj jasno zdefiniowany. Mówisz „Na każdym kroku gra rzuca losową liczbą Jeśli , to zdarzenie jest wyzwalane”. Ale nie podajesz specyfikacji, jak rysowaćMyślę, że byłoby pomocne, gdyby proces ten można było opisać nieco dokładniej.

n

$n$

X

$X$

X < p (n)

$X < p(n)$

X

$X$

— kardynał

@jbarlow: Przepraszam, jeśli moja poprzednia uwaga była niejasna. Jeśli dla niektórych , to nie ma możliwości, aby twój proces mógł mieć więcej niż kroków, ponieważ jednolita losowa liczba od zera do jednego byłaby zdecydowanie mniejsza niż dla dowolnego . Wielkość jako funkcja jest bardzo ściśle związana z tak zwaną funkcją hazardu w podpolu statystyki znanej jako analiza przeżycia .

p (n) = k n

$p(n) = k n$

0 < k < 1

$0 < k < 1$

⌈ k^{- 1} ⌉

$\lceil k^{-1} \rceil$

p (n)

$p(n)$

n > 1 / k

$n > 1/k$

p (n)

$p(n)$

n

$n$

— kardynał

Dla małego użycie analogu różnicowego tego równania różnicowego pokazuje, że ( nie !) Jest zbliżone do Gaussa. (Z tego natychmiast wywnioskowujemy na przykład, że średnia musi być w pobliżu ). Należy również pamiętać, że istnieją pewne (silne) ograniczenia dla , w przeciwnym razie, gdy przekroczy (co ostatecznie to robi), nie ma gwarancji, że pozostaje mniejsze lub równe .

k

$k$

F

$F$

f

$f$

\sqrt{1 / k} = \sqrt{333} \approx 18

$\sqrt{1/k}=\sqrt{333}\approx 18$

k

$k$

p (n)

$p(n)$

1

$1$

F

$F$

1

$1$

— whuber

Odpowiedzi:

W pewnym sensie to, co zrobiłeś, to scharakteryzowanie wszystkich nieujemnych rozkładów o wartościach całkowitych.

Odłóżmy na chwilę opis losowego procesu i skupmy się na rekurencjach w pytaniu.

Jeśli , to z pewnością . Jeśli przepiszemy drugą rekurencję pod względem funkcji przeżycia (gdzie ma rozkład ), otrzymamy coś bardzo sugestywnego i łatwego w obsłudze. Oczywiście a więc Tak więc, o ile nasza sekwencja przyjmuje wartości w i nie zbiega się zbyt szybko do zera, to otrzymamy prawidłową funkcję przeżycia (tj. Monotonicznie zmniejszającą się do zera jako ). $f_n = p_n (1 - F_{n-1})$ $F_n = p_n + (1-p_n) F_{n-1}$ $S_n = 1 - F_n = \mathbb P(T > n)$ $T$ $F$

S_{n} = 1 - F_{n} = (1 - p_{n}) S_{n - 1},

$S_n = 1 - F_n = (1-p_n) S_{n-1} \>,$

S_{n} = \prod_{k = 0}^{n} (1 - p_{k}) .

$S_n = \prod_{k=0}^n (1-p_k) \> .$

(p_{n})

$(p_n)$

[0, 1]

$[0,1]$

n \to \infty

$n \to \infty$

Dokładniej,

Twierdzenie : Sekwencja przyjmująca wartości w określa rozkład na nieujemnych liczbach całkowitych wtedy i tylko wtedy, gdy i wszystkie takie rozkłady mają odpowiednią sekwencję (chociaż może nie być unikalna). $(p_n)$ $[0,1]$
$- \sum_{n = 0}^{\infty} \log (1 - p_{n}) = \infty,$ $-\sum_{n=0}^\infty \log(1-p_n) = \infty \>,$

Zatem rekurencja zapisana w pytaniu jest w pełni ogólna : każdy nieujemny rozkład wartości całkowitych ma odpowiednią sekwencję przyjmującą wartości wynoszącą . $(p_n)$ $[0,1]$

Jednak odwrotność nie jest prawdą; to znaczy istnieją sekwencje o wartościach w , które nie odpowiadają żadnemu prawidłowemu rozkładowi. (W szczególności rozważ dla wszystkich a dla ) $(p_n)$ $[0,1]$ $0 < p_n < 1$ $n \leq N$ $p_n = 0$ $n > N$

Ale czekaj, jest więcej!

Wskazaliśmy na związek z analizą przeżycia i warto to zbadać nieco głębiej. W klasycznej analizie przeżycia z absolutnie ciągłym rozkładem i odpowiednią gęstością , funkcja hazardu jest zdefiniowana jako $F$ $f$

h (t) = \frac{f (t)}{S (t)} .

$h(t) = \frac{f(t)}{S(t)} \>.$

Łączny zagrożenia następnie i prostą analizę pochodnych pokazuje, że Na tej podstawie możemy natychmiast podać charakterystykę dopuszczalnej funkcji hazardu: jest to dowolna mierzalna funkcja taka, że dla wszystkich i jako . $\Lambda(t) = \int_0^t h(s) \,\mathrm d s$

S (t) = \exp (- Λ (t)) = \exp (- \int_{0}^{t} h (s) d s) .

$S(t) = \exp(-\Lambda(t)) = \exp\Big(-\int_0^t h(s) \,\mathrm d s\Big)\>.$

h

$h$

h (t) \geq 0

$h(t) \geq 0$

t

$t$

\int_{0}^{t} h (s) d s ↑ \infty

$\int_0^t h(s) \,\mathrm d s \uparrow \infty$

t \to \infty

$t \to \infty$

Otrzymujemy podobną rekurencję dla funkcji przeżycia do powyższej, zauważając, że dla $t > t_0$

S (t) = e^{- \int_{t_{0}}^{t} h (s) d s} S (t_{0}) .

$S(t) = e^{-\int_{t_0}^t h(s) \,\mathrm d s} S(t_0) \>.$

Zauważ w szczególności , że moglibyśmy wybrać aby była stała kawałek po kawałku, każdy kawałek ma szerokość 1 i taki, że całka zbiega się w nieskończoność. Dałoby to funkcję przeżycia która pasuje do dowolnej pożądanej nieujemnej liczby całkowitej o wartości jednej przy każdej liczbie całkowitej dodatniej. $h(t)$ $S(t)$

Ponowne połączenie z dyskretną obudową

Aby dopasować pożądaną dyskretną na każdej liczbie całkowitej, powinniśmy wybrać funkcję hazardu, która jest częściowo stała, tak że on . To drugi dowód warunku koniecznego dla sekwencji aby zdefiniować prawidłowy rozkład. $S(n)$

h (t) = h_{n} = - \log (1 - p_{n}),

$h(t) = h_n = -\log(1-p_n)\>,$

(n - 1, n]

$(n-1,n]$

(p_{n})

$(p_n)$

Zauważ, że dla małych , który zapewnia heurystyczne połączenie między funkcją hazardu rozkładu ciągłego a rozkładem dyskretnym z dopasowaniem funkcji przeżycia na liczby całkowite. $p_n$ $-\log(1-p_n) \approx p_n = f_n / S_{n-1}$

Postscriptum : Jako ostatnia uwaga, przykład w pytaniu nie spełnia niezbędnych warunków bez odpowiedniej modyfikacji przy i ustawieniu dla wszystkich . $p_n = k n$ $f_n$ $n = \lceil k^{-1} \rceil$ $f_n = 0$ $n > \lceil k^{-1} \rceil$

— kardynał
źródło

+1 Bardzo rozświetlające. Jednak w odniesieniu do postscriptum wydaje mi się, że „odpowiednie obcięcie” występuje oczywiście dla specjalnych wartości . Na przykład, przy otrzymujemy , a bardziej ogólnie, przy otrzymujemy .

k

$k$

k = 1 / 2

$k=1/2$

f = (0, 1 / 2, 1 / 2, 0, \dots)

$f=(0,1/2,1/2,0,\ldots)$

k = 1 / m

$k=1/m$

f (m + 1) = f (m + 2) = \dots = 0

$f(m+1)=f(m+2)=\cdots=0$

— whuber

@whuber: Powinienem był jaśniej sprecyzować, co rozumiem przez „odpowiednie obcięcie”. Myślałem o obcięciu (zmniejszeniu) wartości w określonym punkcie (aby stał się jednością). Myślę, że pojęcie to jest nadal aktualne w przypadku, o którym wspominasz, po prostu, że obcięcie nie spowoduje zmiany wartości . Spróbuję to wyjaśnić wkrótce w edycji. Dziękuję Ci!

f_{n}

$f_n$

F_{n}

$F_n$

f_{n}

$f_n$

— kardynał

Świetna odpowiedź. To jest bardzo wnikliwe. Byłem bardzo zainteresowany tym problemem związanym z innymi obszarami i koncepcjami.

— jbarlow,

@jbarlow: Dziękuję. Cieszę się, że okaże się przydatny! Podobało mi się trochę o tym myśleć, bo to miłe pytanie.

— kardynał

W przypadku, gdy , mamy pewne znane właściwości. Możemy rozwiązać relację powtarzalności $p(n) = p < 1$

F (n) = p + F (n - 1) (1 - p); F (0) = p

$F(n) = p + F(n-1)(1-p); \; F(0) = p$

ma rozwiązanie

F (n) = P (N \leq n) = 1 - (1 - p)^{n + 1}

$F(n) = P(N \le n) = 1- (1-p)^{n+1}$ który jest rozkładem geometrycznym . Jest dobrze zbadany.

Bardziej ogólny przypadek prawdopodobnie nie może być obliczony w formie zamkniętej, a zatem prawdopodobnie nie ma znanego rozkładu. $p(n)$

Inne przypadki:

$p(n) = \frac{p}{n}; \; p<1; \;F(0) = p$ ma rozwiązanie co nie jest powszechnie znaną dystrybucją. $F (n) = 1 - \frac{(1 - p) Γ (n + 1 - p)}{Γ (1 - p) Γ (n + 1)}$ $F(n) = 1 - \frac{(1-p)\Gamma( n + 1 -p)}{\Gamma( 1-p)\Gamma(n+1)}$
Zdefiniuj (znany jako funkcja przeżycia w statystykach), powyższa relacja powtarzalności sprowadza się do prostszej postaci: $S(n) = 1-F(n)$ $S (n) = (1 - p (n)) S (n - 1)$ $S(n) =\left(1 - p(n) \right) S(n-1)$
Z twojego przykładu wynika, że potrzebujesz funkcji która zwiększa się w . Twój wybór nie jest świetny analitycznie z powodu przerwy przy . Matematycy i statystyki wolą gładkie rzeczy. Proponuję więc które i zbiega się do 1. Rozwiązanie relacji rekurencyjnej z tym ma ładną formę analityczną: Zastanów się . Znanym faktem statystycznym jest to, że $p(n)$ $n$ $p(n) = kn$ $p>1$ $p (n) = 1 - \frac{(1 - p)}{n + 1} p < 1$ $p(n) = 1 - \frac{(1-p)}{n+1} \; p<1$ $p(0) = p$ $p(n)$ $F (n) = 1 - \frac{(1 - p)^{n + 1}}{n!}$ $F(n) = 1 - \frac{ (1-p)^{n+1} }{ n! }$ $S(n) = 1 - F(n) = \frac{ (1-p)^{n+1} }{ n! }$ $\sum_{i = 0}^{\infty} S (i) = E [N]$ $\sum_{i=0}^{\infty} S(i) = E[N]$ który, jeśli pamiętacie jakiś rachunek różniczkowy, wygląda bardzo podobnie do wykładniczej serii Taylora, stąd $E [N] = (1 - p) e^{(1 - p)}$ $E[N] = (1-p)e^{(1-p) }$

— Cam.Davidson.Pilon
źródło