Compatible sequences and a slow Winkler percolation
MetadataShow full item record
Citation (published version)P Gacs. 2004. "Compatible sequences and a slow Winkler percolation." Combinatorics, Probability and Computing, Volume 13, Issue 6, pp. 815 - 856 (42). https://doi.org/10.1017/S0963548304006340
Two infinite 0–1 sequences are called compatible when it is possible to cast out $0\,$s from both in such a way that they become complementary to each other. Answering a question of Peter Winkler, we show that if the two 0–1 sequences are random i.i.d. and independent from each other, with probability $p$ of $1\,$s, then if $p$ is sufficiently small they are compatible with positive probability. The question is equivalent to a certain dependent percolation with a power-law behaviour: the probability that the origin is blocked at distance $n$ but not closer decreases only polynomially fast and not, as usual, exponentially.
Showing items related by title, author, creator and subject.
Integrating archaeology and ancient DNA analysis to address invasive species colonization in the Gulf of Alaska West, Catherine; Hofman, Courtney A.; Ebbert, Steve; Martin, John; Shirazi, Sabrina; Dunning, Samantha; Maldonado, Jesus E. (WILEY, 2017-10-01)The intentional and unintentional movement of plants and animals by humans has transformed ecosystems and landscapes globally. Assessing when and how a species was introduced are central to managing these transformed ...
Contribution of leaf specular reflection to canopy reflectance under black soil case using stochastic radiative transfer model Yang, Bin; Knyazikhin, Yuri; Zhao, Haimeng; Ma, Yuzhong (Elsevier Science BV, 2018-12-15)Numerous canopy radiative transfer models have been proposed based on the assumption of “ideal bi-Lambertian leaves” with the aim of simplifying the interactions between photons and vegetation canopies. This assumption may ...
Inconsistencies of interannual variability and trends in long-term satellite leaf area index products Jiang, Chongya; Ryu, Youngryel; Fang, Hongliang; Myneni, Ranga; Claverie, Martin; Zhu, Zaichun (2017-07-06)Understanding the long-term performance of global satellite leaf area index (LAI) products is important for global change research. However, few effort has been devoted to evaluating the long-term time-series consistencies ...