Некоторые статистические задачи на графах

При гипотезе $H_0$ все ребра случайного графа на $n$ вершинах появляются независимо друг от друга с вероятностью $\beta$, $0<\beta<1$. При альтернативе $H_k$ появление части ребер случайного графа определяется так, как при гипотезе $H_0$, а ребра, соединяющие вершины из некоторого выделенного подмножества вершин $A$, $|A|=k$, $2\le k\le n$, появляются независимо с вероятностью $\alpha$, $\alpha>\beta$. В статье изучается асимптотика минимальных значений $k=k(n)$, при которых существует состоятельный критерий для проверки гипотезы $H_0$ против альтернативы $H_k$. Показано, что при $n\to\infty$
$$ k\le\frac2{\ln q}(\ln n-2\ln\ln n),\qquad q=\frac{(1-\alpha)^2}{1-\beta}+\frac{\alpha^2}\beta, $$
состоятельного критерия не существует. Для случая, когда случайный граф выбран в соответствии с мерой, которая определяется неизвестным множеством $A$, $|A|=k$, $k\ge\frac8{\alpha-\beta}\sqrt{n\ln n}$, построена асимптотически точная оценка множества $A$. Библ. 4 назв.