|
|
Principle Seminar of the Department of Probability Theory, Moscow State University
October 23, 2019 16:45–17:45, Moscow, MSU, auditorium 12-24
|
|
|
|
|
|
The distribution of the maximum of function of Bernoulli random variables
M. E. Zhukovskii Moscow Institute of Physics and Technology (State University), Dolgoprudny, Moscow region
|
|
Abstract:
Let $r_1,r_2,...$ be independent identically distributed Bernoulli random
variables, $S$ be a set of $s$-dimensional vectors consisting of this random
variables and f be a function from $R^s$ to $R$. What is the limit distribution
of the maximum of $f(x)$ over $x$ from $S$?
Consider the following particular case of the above general problem. In 1980,
B. Bollobas proved that, for the maximum degree $X_n$ of the binomial random graph
$G(n,p)$, the following is true. There exist non-random sequences $a_n, b_n$ such
that the limit distribution of $(X_n-a_n)/b_n$ is Gumbel distribution. To see that
this is really the particular case of the general problem it is sufficient to
choose indicators of edges on the role of Bernoulli random variables, on the
role of system $S$ to take $(n-1)$-vectors containing indicators of edges having a
common vertex and on the role of $f(x)$ to take the sum of elements of vector $x$.
Assume that the degrees of vertices of the random graph are independent random
variables. Then the result of Bollobas clearly follows from the convergence (in
distribution) of Binomial random variables with parameters $n$ and $c(1+o(1))/n$ to
Poisson random variable (apply this convergence result to the number of degrees
greater than $a_n+y b_n$, where $y=-ln c$). Unfortunately, for every two vertices,
their degrees are dependent due to the random edge between them. Nevertheless,
these dependencies are very weak, and so, convergences of moments of the
considered random variables to the respective moments of Poisson distribution
still hold.
The described techniques does not work if intersections of vectors from $S$
(as sets) are so large that the described moments diverge (for example, it
happens in the problem of studying the distribution of maximum number of
common neighbours of $k$ vertices). To solve this problem, we develop new
techniques based, in particular, on a new Janson type inequality. It works,
in particular, for the above mentioned problem of finding the limit
distribution of the maximum number of common neighbours of $k$ vertices.
|
|