Testando certos contrastes: este é um problema difícil ou não?

12

Eu postei isso no mathoverflow e ninguém está respondendo:

O método de Scheffé para identificar contrastes estatisticamente significativos é amplamente conhecido. Um contraste entre as médias , i = 1 , , r de r populações é uma combinação linear r i = 1 c i μ i na qual r i = 1 c i = 0μii=1,,rri=1rciμii=1rci=0 , e um múltiplo escalar de um contraste é essencialmente a mesma Por outro lado, pode-se dizer que o conjunto de contrastes é um espaço projetivo. O método de Scheffé testa uma hipótese nula que diz que todos os contrastes entre essespopulações r são 0 e, dado um nível de significância α , rejeita a hipótese nula com probabilidade α, dado que a hipótese nula é verdadeira. E se a hipótese nula for rejeitada, Scheffé ressalta que seu teste nos dizquaiscontrastes diferem significativamente de 0 (não tenho certeza se o artigo da Wikipedia que vinculei a esse ponto).r0αα0

Eu gostaria de saber se alguém pode fazer algo semelhante em um tipo diferente de situação. Considere um modelo de regressão linear simples , onde ε ii . i . d . N ( 0 , σ 2 ) , i = 1 , , n .Yi=α+βxi+εiεii.i.d.N(0,σ2)i=1,,n

A hipótese nula que quero considerar diz respeito a um tipo diferente de contraste. Ele diz que não existe um subconjunto de tal modo que E ( Y i ) = α 1 + β x i para i A e E ( Y i ) = α 2 + β x i para i Um , onde α 1A{1,,n}E(Yi)=α1+βxiiAE(Yi)=α2+βxiiAα1α2. Se o subconjunto for especificado previamente, um teste t de duas amostras comum fará isso, mas queremos algo que considere todos os subconjuntos e reduza a probabilidade de rejeitar uma hipótese nula verdadeira.At

Pode-se descobrir isso se a eficiência não for uma preocupação: encontre um teste que passe por todas as possibilidades. Mesmo assim, é problemático; dois contrastes não seriam independentes. Perguntei a um especialista em detecção de irregularidades sobre isso e ele apenas disse que é um pesadelo combinatório. Então perguntei se alguém poderia provar que não há uma maneira eficiente de fazer isso, talvez reduzindo um problema difícil de NP a ele. Ele apenas disse que fica longe de problemas difíceis de NP.2n11

Então: Podemos provar que esse problema é "difícil" ou que não é?

Michael Hardy
fonte
(+1) Copiando um comentário para esclarecimento da versão MO : Apenas um pequeno ponto de esclarecimento: Enquanto eu o li, qualifica sob sua hipótese nula, mas ( 1 , 2 , 2 ) e ( 1 , 1 , 1 ) não (independentemente de β ). É isso que você pretendia? (Parece não coincidir com algumas das outras alusões feitas na pergunta.)(α1,α2,α3)=(1,2,3)(1,2,2)(1,1,1)β
cardeal
Como afirmado acima, a hipótese nula seria que precisamos de apenas um , e a hipótese alternativa é que precisamos de dois. Não sei por que você tem um terceiro. Pode-se também considerar a hipótese nula de apenas um α versus a hipótese alternativa de várias, e talvez seja isso que eu deveria fazer. αα
Michael Hardy
Yi=α+βxi+εiααi
αi

Respostas:

1

Percebeu que ninguém respondeu a essa pergunta até agora ...

Z

yi=α+βxi+γzi+ϵi
yi=α+βxi+ϵi.
f(z)t.
Essa é uma variante do problema de particionamento definido, conhecido como NP-hard.
user3697176
fonte
O problema de particionamento definido pode realmente ser reduzido a esse problema? Nesse caso, isso provaria que este é um problema difícil.
Michael Hardy
Esse problema é pelo menos tão difícil quanto o SPP (Classic Set Partitioning Problem). O SPP pega uma combinação linear de pesos e tenta multiplicá-los por +/- 1 para obter uma expressão que totalize 0. Aqui você deseja satisfazer uma desigualdade. Se isso fosse solucionável em tempo polinomial para entradas arbitrárias, um argumento de bissecção mostra que você também poderia resolver o SPP em tempo polinomial. Isso não é exatamente uma redução, mas está próximo.
user3697176