SHARP THRESHOLD FOR THE ISING PERCEPTRON MODEL

• 成果类型: Article
• 署名作者: Xu, Changji
• 署名单位: Harvard University
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/21-AOP1511
• 发表日期: 2021
• 页码: 2399-2415
• 关键词: boolean functions; storage capacity; networks

摘要

Consider the discrete cube {-1, 1}(N) and a random collection of half spaces which includes each half space H(x) := {y is an element of {-1, 1}(N) : x center dot y >=kappa root N} for x. {-1, 1}(N) independently with probability p. Is the intersection of these half spaces empty? This is called the Ising perceptron model under Bernoulli disorder. We prove that this event has a sharp threshold, that is, the probability that the intersection is empty increases quickly from is an element of to 1 - is an element of when p increases only by a factor of 1 + o(1) as N ->infinity.