1,721,348 research outputs found
An Exponential Bound for the Probability of a Specified Subgraph in a Random Graph
No full textJanson, Svante; Luczak, Tomasz; Rucinski, Andrzej. (1988). An Exponential Bound for the Probability of a Specified Subgraph in a Random Graph. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/4776
Quantitative bounds in the central limit theorem for m-dependent random variables
Full text linkFor each , let be real random variables and . Let be an integer. Suppose is -dependent, , E(X_{ni}^2)<\infty and \sigma_n^2:=E(S_n^2)>0 for all and . Then,
\begin{gather*}
d_W\Bigl(\frac{S_n}{\sigma_n},\,Z\Bigr)\le 30\,\bigl\{c^{1/3}+12\,U_n(c/2)^{1/2}\bigr\}\quad\quad\text{for all }n\ge 1\text{ and }c>0,
\end{gather*}
where is Wasserstein distance, a standard normal random variable and
U_n(c)=\frac{m_n}{\sigma_n^2}\,\sum_{i=1}^{N_n}E\Bigl[X_{n,i}^2\,1\bigl\{\abs{X_{n,i}}>c\,\sigma_n/m_n\bigr\}\Bigr].
Among other things, this estimate of yields a similar estimate of where is total variation distance
On semi-restricted Rock, Paper, Scissors
No full textSpiro, Surya and Zeng (Electron. J. Combin. 2023) recently studied a semirestricted variant of the well-known game Rock, Paper, Scissors; in this variant the game is played for 3n rounds, but one of the two players is restricted and has to use each of the three moves exactly n times. They show that the optimal strategy for the restricted player is the greedy strategy, and show that it results in an expected score for the unrestricted player Theta(N/n); they conjecture, based on numerical evidence, that the expectation is approximate to 1.46 N /n. We analyse the result of the strategy further and show that the average is similar to cN/n with c = 3N/3/2N/ pi =. 1.466, verifying the conjecture. The proof is based on considering the case when both players play greedily, which leads to the same expectation as optimal play; for this case we also find the asymptotic distribution of the score, and compute its variance
Patterns in Random Permutations Avoiding Some Sets of Multiple Patterns
No full textWe consider a random permutation drawn from the set of permutations of length n that avoid some given set of patterns of length 3. We show that the number of occurrences of another pattern sigma has a limit distribution, after suitable scaling. In several cases, the number is asymptotically normal; this contrasts to the cases of permutations avoiding a single pattern of length 3 studied in earlier papers
On general subtrees of a conditioned Galton-Watson tree
No full textWe show that the number of copies of a given rooted tree in a conditioned Galton-Watson tree satisfies a law of large numbers under a minimal moment condition on the offspring distribution
Random replacements in Polya urns with infinitely many colours
No full textWe consider the general version of Polya urns recently studied by Bandyopadhyay and Thacker (2016+) and Mailler and Marckert (2017), with the space of colours being any Borel space S and the state of the urn being a finite measure on S. We consider urns with random replacements, and show that these can be regarded as urns with deterministic replacements using the colour space S x [0, 1]
On convergence for graphexes
No full textWe study four different notions of convergence for graphexes, recently introduced by Borgs, Chayes, Cohn and Holden, and by Veitch and Roy. We give some properties of them and some relations between them. We also extend results by Veitch and Roy on convergence of empirical graphons
The number of occurrences of patterns in a random tree or forest permutation
No full textThe classes of tree permutations and forest permutations were defined by Acan and Hitczenko (2016). We study random permutations of a given length from these classes, and in particular the number of occurrences of a fixed pattern in one of these random permutations. The main results show that the distributions of these numbers are asymptotically normal. The proof uses representations of random tree and forest permutations that enable us to express the number of occurrences of a pattern by a type of U-statistics; we then use general limit theorems for the latter
On the probability that a binomial variable is at most its expectation
No full textConsider the probability that a binomial random variable Bi(n, m/n) with integer expectation m is at most its expectation. Chvatal conjectured that for any given n, this probability is smallest when m is the integer closest to 2n/3. We show that this holds when n is large
- …
