Alternatywa rozkładu empirycznego

HOJNOŚĆ:

Pełne nagroda zostanie przyznana osobie, która stanowi odniesienie do wszelkich opublikowanych papieru, który używa lub wymienia prognozy $\tilde{F}$ poniżej.

Motywacja:

Ta sekcja prawdopodobnie nie jest dla ciebie ważna i podejrzewam, że nie pomoże ci zdobyć nagrody, ale ponieważ ktoś zapytał o motywację, oto nad czym pracuję.

Pracuję nad problemem teorii grafów statystycznych. Standardowy obiekt ograniczający wykres gęsty $W : [0,1]^2 \to [0,1]$ jest funkcją symetryczną w tym sensie, że $W(u,v) = W(v,u)$ . Próbkowanie wykresu na $n$ wierzchołkach można traktować jako próbkowanie $n$ jednolitych wartości w jednostkowym przedziale ( $U_i$ dla $i = 1, \dots, n$), a następnie prawdopodobieństwo krawędzi $(i,j)$ wynosi $W(U_i, U_j)$ . Niech otrzymaną macierz sąsiedztwa nazwać .$A$

$W$$f = W / \iint W$$\iint W > 0$$f$$A$$f$$f$$f$$\sum A$$W$

Niestety metoda, którą znalazłem, wykazuje spójność, gdy próbkujemy z rozkładu o gęstości . Sposób, w jaki jest wymaga próbkowania siatki punktów (w przeciwieństwie do pobierania losowań z oryginalnego ). W tym pytaniu stats.SE pytam o jednowymiarowy (prostszy) problem tego, co się dzieje, gdy możemy tylko próbkować Bernoullisa tylko na takiej siatce, a nie próbować bezpośrednio z rozkładu.$f$$A$$f$

odniesienia do granic wykresów:

L. Lovasz i B. Szegedy. Granice gęstych sekwencji grafów ( arxiv ).

C. Borgs, J. Chayes, L. Lovasz, V. Sos i K. Vesztergombi. Zbieżne sekwencje gęstych wykresów i: Częstotliwości podgraphów, właściwości metryczne i testowanie. ( arxiv ).

Notacja:

Rozważ ciągły rozkład z cdf i pdf który ma dodatnie wsparcie dla przedziału . Załóżmy, że nie ma masy punktowej, jest wszędzie różna, a także, że jest supremum w przedziale . Niech oznacza, że zmienna losowa jest próbą z rozkładu . to iid jednolite zmienne losowe na .$F$$f$$[0,1]$$f$$F$$\sup_{z \in [0,1]} f(z) = c < \infty$$f$$[0,1]$$X \sim F$$X$$F$$U_i$$[0,1]$

Konfiguracja problemu:

Często możemy pozwolić być zmiennymi losowymi o rozkładzie i pracować ze zwykłą empiryczną funkcją rozkładu jako gdzie jest funkcją wskaźnika. Zauważ, że ten rozkład empiryczny jest sam w sobie losowy (gdzie jest ustalone).$X_1, \dots, X_n$$F$

$$\hat{F}_n(t) = \frac{1}{n} \sum_{i=1}^n I\{X_i \leq t\}$$ $I$$\hat{F}_n(t)$$t$

Niestety, nie jestem w stanie wyciągnąć próbek bezpośrednio z . Wiem jednak, że ma wsparcie dodatnie tylko na i mogę generować zmienne losowe gdzie jest zmienną losową o rozkładzie Bernoulliego z prawdopodobieństwem sukcesu gdzie i są zdefiniowane powyżej. Tak więc . Jednym oczywistym sposobem, w jaki mógłbym oszacować podstawie tych wartości , jest przyjęcie gdzie$F$$f$$[0,1]$$Y_1, \dots, Y_n$$Y_i$

$$p_i = f((i-1+U_i)/n)/c$$ $c$$U_i$$Y_i \sim \text{Bern}(p_i)$$F$$Y_i$ $$\tilde{F}_n(t) = \frac{1}{\sum_{i=1}^n Y_i} \sum_{i=1}^{\lceil tn \rceil} Y_i$$ $\lceil \cdot \rceil$ jest funkcją pułapu (to znaczy, po prostu zaokrąglij w górę do najbliższej liczby całkowitej) i przerysuj, jeśli (aby uniknąć dzielenia przez zero i powodowania upadku wszechświata) . Zauważ, że jest również zmienną losową, ponieważ są zmiennymi losowymi.$\sum_{i=1}^n Y_i = 0$$\tilde{F}(t)$$Y_i$

Pytania:

Od (co moim zdaniem powinno być) najłatwiejszego do najtrudniejszego.

1. Czy ktoś wie, czy ten (lub coś podobnego) ma nazwę? Czy możesz podać odniesienie, w którym mogę zobaczyć niektóre z jego właściwości?$\tilde{F}_n$

2. Jako , czy jest spójnym estymatorem (i czy możesz to udowodnić)?$n \to \infty$$\tilde{F}_n(t)$$F(t)$

3. Jaki jest limit dystrybucji jako ?$\tilde{F}_n(t)$$n \to \infty$

4. Idealnie chciałbym ograniczyć następujące w funkcji - np. , ale nie wiem, jaka jest prawda. oznacza Big O prawdopodobieństwa$n$$O_P(\log(n) /\sqrt{n})$$O_P$

$$\sup_{C \subset [0,1]} \int_C |\tilde{F}_n(t) - F(t)| \, dt$$

Kilka pomysłów i notatek:

1. Wygląda to bardzo podobnie do próbkowania z odrzuceniem akceptacji i stratyfikacji opartej na siatce. Należy pamiętać, że tak nie jest, ponieważ nie odrzucamy kolejnej próby, jeśli odrzucimy propozycję.

2. Jestem prawie pewien, że ten jest stronniczy. Myślę, że alternatywa jest obiektywna, ale ma nieprzyjemną właściwość .$\tilde{F}_n$

   $$\tilde{F^*}_n(t) = \frac{c}{n} \sum_{i=1}^{\lceil tn \rceil} Y_i$$ $\mathbb{P}\left(\tilde{F^*}(1) = 1\right) < 1$

3. Interesuje mnie użycie jako estymatora wtyczek . Nie sądzę, aby była to przydatna informacja, ale może znasz jakiś powód, dla którego może być.$\tilde{F}_n$

Przykład w R.

Oto trochę kodu R, jeśli chcesz porównać rozkład empiryczny z . Przepraszam, że niektóre wcięcia są nieprawidłowe ... Nie wiem, jak to naprawić.$\tilde{F}_n$

# sample from a beta distribution with parameters a and b
a <- 4 # make this > 1 to get the mode right
b <- 1.1 # make this > 1 to get the mode right
qD <- function(x){qbeta(x, a, b)} # inverse
dD <- function(x){dbeta(x, a, b)} # density
pD <- function(x){pbeta(x, a, b)} # cdf
mD <- dbeta((a-1)/(a+b-2), a, b) # maximum value sup_z f(z)


# draw samples for the empirical distribution and \tilde{F}
draw <- function(n){ # n is the number of observations
  u <- sort(runif(n)) 
  x <- qD(u) # samples for empirical dist
  z <- 0 # keep track of how many y_i == 1
  # take bernoulli samples at the points s
  s <- seq(0,1-1/n,length=n) + runif(n,0,1/n) 
  p <- dD(s) # density at s
  while(z == 0){ # make sure we get at least one y_i == 1
    y <- rbinom(rep(1,n), 1, p/mD) # y_i that we sampled
    z <- sum(y)
  }
  result <- list(x=x, y=y, z=z)
  return(result)
}

sim <- function(simdat, n, w){
  # F hat -- empirical dist at w
  fh <- mean(simdat$x < w) 
  # F tilde
  ft <- sum(simdat$y[1:ceiling(n*w)])/simdat$z
  # Uncomment this if we want an unbiased estimate.
  # This can take on values > 1 which is undesirable for a cdf.
  ### ft <- sum(simdat$y[1:ceiling(n*w)]) * (mD / n)
  return(c(fh, ft))
}


set.seed(1) # for reproducibility

n <- 50 # number observations
w <- 0.5555 # some value to test this at (called t above)
reps <- 1000 # look at this many values of Fhat(w) and Ftilde(w)
# simulate this data
samps <- replicate(reps, sim(draw(n), n, w))

# compare the true value to the empirical means
pD(w) # the truth 
apply(samps, 1, mean) # sample mean of (Fhat(w), Ftilde(w))
apply(samps, 1, var)  # sample variance of (Fhat(w), Ftilde(w))
apply((samps - pD(w))^2, 1, mean) # variance around truth


# now lets look at what a single realization might look like
dat <- draw(n)
plot(NA, xlim=0:1, ylim=0:1, xlab="t", ylab="empirical cdf",
     main="comparing ECDF (red), Ftilde (blue), true CDF (black)")
s <- seq(0,1,length=1000)
lines(s, pD(s), lwd=3) # truth in black
abline(h=0:1)
lines(c(0,rep(dat$x,each=2),Inf),
     rep(seq(0,1,length=n+1),each=2),
     col="red")
lines(c(0,rep(which(dat$y==1)/n, each=2),1),
      rep(seq(0,1,length=dat$z+1),each=2),
      col="blue")

EDYCJE:

EDYCJA 1 -

Zredagowałem to, aby odpowiedzieć na komentarze @ whuber.

EDYCJA 2 -

Dodałem kod R i trochę go wyczyściłem. Zmieniłem nieznacznie notację dla czytelności, ale zasadniczo jest taka sama. Planuję wystawić nagrodę za to, gdy tylko będę mógł, więc daj mi znać, jeśli chcesz uzyskać dodatkowe wyjaśnienia.

EDYCJA 3 -

Myślę, że odniosłem się do uwag kardynała. Poprawiłem literówki w całkowitej odmianie. Dodam nagrodę.

EDYCJA 4 -

Dodano sekcję „motywacja” dla @cardinal.

Chociaż to odniesienie

EDYCJA: DODATKOWE ODNIESIENIE DO BARDZO PODOBNYCH STATYSTYK „Nieparametryczne oszacowanie z niekompletnych obserwacji” EL Kaplan i Paul Meier, Journal of American Statistics Association, t. 53, nr 282 (Jun., 1958), str. 457-481

nie jest zgodny z estymatorem podobnym do ECDF w Uważam, że jest logicznie równoważny z estymatorem Kaplana-Meiera (czyli estymatorem limitu produktu) stosowanym w analizie przeżycia, nawet jeśli ma to zastosowanie do przedziału czasu .$[0,1]$$[0,\infty)$

Oszacowanie stronniczości byłoby możliwe, gdy masz rozsądne oszacowanie dystrybucji za pomocą wygładzania jądra, jeśli jest ono odpowiednio zachowane (patrz np. Transformacja Khmaladze na Wikipedii).

W przypadku dwuwymiarowym na wykresie problem oszacowania z choć z trywialnym ograniczeniem symetrii, wydaje się podobny do podejścia Jean-Davida Fermaniana, Dragana Radulovica i Martena Wegkampa (2004): Słaba zbieżność kopuły empirycznej Procesy , Bernoulli , vol. 10, nr 5, 847–860, jak wskazuje kardynał @ „Metoda wielowymiarowej delty”.$f = W / \iint W$$A$

To odpowiada na pytania 2 i 3 powyżej. Nadal jednak chcę referencji (od pytania 1).

Nie bierze to jeszcze pod uwagę, gdy .$\sum Y_i = 0$

Rozważ , a następnie gdzie indeksy dolne oznaczają pochodne. Przypomnijmy . Niech Więc zwróć uwagę, że i . Również, $g(A,B) = A/(A+B)$

$$\begin{align} g_A(A,B) &= (A+B)^{-1} + A(A+B)^{-2}\\ g_B(A,B) &= -A(A+B)^{-2}\\ g_{AA}(A,B) &= 2B(A+B)^{-3}\\ g_{AB}(A,B) &= (A-B)(A+B)^{-3}\\ g_{BB}(B,B) &= 2A(A+B)^{-3} \end{align}$$ $p_i = f((i-1+U_i)/n)/c$ $$\begin{align} R = \frac{1}{n}\sum_{i=1}^{\lceil nt \rceil} Y_i, \quad& \mu_R = \mathbb{E}(R) = \int_0^t p(u) \, d u = c^{-1}F(t)\\ S = \frac{1}{n}\sum_{\lceil nt \rceil +1}^n Y_i, \quad& \mu_S = \mathbb{E}(S) = \int_t^1 p(u) \, d u = c^{-1}(1-F(t)) \end{align}$$ $\mu_R + \mu_S = c^{-1}F(t) + c^{-1}(1-F(t)) = c^{-1}$$g(\mu_R, \mu_S) = F(t)$ $$\begin{align} \text{ Var}(R) &= \frac{1}{n^2} \sum_{i=1}^{\lceil nt \rceil} \text{ Var}(Y_i) = \frac{1}{n} \int_0^t f(u)/c(1-f(u)/c) \, d u = \frac{1}{nc^2} \int_0^t f(u)(c-f(u)) \, d u\\ \text{ Var}(S) &= \frac{1}{nc^2} \int_t^1 f(u)(c-f(u)) \, d u \end{align}$$ Zauważ, że przez niezależność .$\text{ Cov}(R,S) = 0$$Y_i$

Teraz używamy rozszerzenia Taylor, aby uzyskać

$$\begin{align} &\mathbb{E}\left(\tilde{F}_n(t)\right) =\mathbb{E}\left( \frac{1}{\sum_{i=1}^n Y_i} \sum_{i=1}^{\lceil tn \rceil} Y_i \right) =\mathbb{E}\left(\frac{nR}{nR+nS}\right) =\mathbb{E}\left(\frac{R}{R+S}\right) =\mathbb{E}\left(g(R,S)\right)\\ &=g(\mu_R,\mu_S) + \frac{1}{2}\mathbb{E}((R - \mu_R)^2)g_{RR}(\mu_R, \mu_S) \nonumber\\ &\quad + \mathbb{E}((R - \mu_R)(S-\mu_S))g_{RS}(\mu_R, \mu_S) + \frac{1}{2}\mathbb{E}((S - \mu_S)^2)g_{SS}(\mu_R, \mu_S) + \dots \\ &= F(t) + \frac{1}{2}\mathbb{E}((R - \mu_R)^2)2\mu_S(\mu_R+\mu_S)^{-3} \nonumber\\ &\quad + \mathbb{E}((R - \mu_R)(S-\mu_S))(\mu_R-\mu_S)(\mu_R+\mu_S)^{-3} \nonumber\\ &\quad + \frac{1}{2}\mathbb{E}((S - \mu_S)^2) 2\mu_R(\mu_R+\mu_S)^{-3} + \dots\\ &= F(t) + (\mu_R+\mu_S)^{-3} \bigg( \mathbb{E}((R - \mu_R)^2)\mu_S + \mathbb{E}((R - \mu_R)(S-\mu_S))(\mu_R-\mu_S) \nonumber\\ &\quad + \mathbb{E}((S - \mu_S)^2) \mu_R \bigg) + \dots \\ &= F(t) + c^3 \left( \text{ Var}(R)c(1-F(t)) \right. \nonumber\\ &\quad + \left.\text{ Cov}(R,S)(cF(t) - c(1-F(t))) + \text{ Var}(S) cF(t) \right) + \dots \\ &= F(t) + c^4 \left( \left(\frac{1}{n} \int_0^t f(u)(c-f(u)) \, d u\right) (1-F(t)) \right. \nonumber\\ &\quad \left. + \left(\frac{1}{n} \int_t^1 f(u)(c-f(u)) \, d u \right) F(t) \right) + \dots\\ &= F(t) + \tilde{V}_{F(t)}/n + \dots\\ &= F(t) + {\cal O}(n^{-1}) \end{align}$$ gdzie W szczególności otrzymujemy $$\begin{align} \tilde{V}_{F(t)} &= c^2\left(\int_0^t f(u)(c-f(u)) \, d u\right) (1-F(t)) + c^2\left(\int_t^1 f(u)(c-f(u)) \, d u \right) F(t)\\ &< c^2\left( \int_0^t cf(u) \, d u\right)(1 - F(t)) + c^2\left( \int_t^1 cf(u) \, d u\right)F(t)\\ &< c^3 2F(t)(1-F(t)) \end{align}$$ $$\begin{align} \sqrt{n}\left(\tilde{F}_n(t) - F(t)\right) \overset{d}{\to} N(0,V_{F(t)}) \end{align}$$

Skomentuj, jeśli zauważysz coś nie tak.

EDYCJE:

Edycja 1 -

Naprawiono literówkę w . Dzięki @cardinal za sugestię w komentarzach do pytania 4.$V_{F(t)}$

Edycja 2 -

Naprawiono wiele literówek: miałem gdzie powinienem mieć w wielu miejscach. Nadal muszę odpowiedzieć na odpowiedź @ kardynała na temat .$c^{-1}$$c$$\sum Y_i = 0$