Hitting Time Theorems for Random Matrices
Hitting Time Theorems for Random Matrices
复制标题
随机矩阵的命中时间定理
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Laura Eslava
中科院分区：
文献类型：
--
作者：
L. Addario;Laura Eslava
从一个由零组成的n × n矩阵开始，选择均匀随机的零元素，并将它们改为1，一次一个，直到矩阵变得可逆。我们证明，当n → ∞时，概率趋于1，这发生在最后一个零行或零列消失的时刻。证明了随机对称Bernoulli矩阵的一个相关结果，并给出了一些相关问题的定量界。这些结果推广了Costello和Vu [10]的早期工作。
Starting from an n-by-n matrix of zeros, choose uniformly random zero entries and change them to ones, one at a time, until the matrix becomes invertible. We show that with probability tending to one as n → ∞, this occurs at the very moment the last zero row or zero column disappears. We prove a related result for random symmetric Bernoulli matrices, and give quantitative bounds for some related problems. These results extend earlier work by Costello and Vu [10].