Skip to main content

All Questions

Filter by
Sorted by
Tagged with
3 votes
1 answer
1k views

Gradient of probability distribution

Given a random walk on a lattice $L$ (not necessarily centered - we allow $E[X_i] \neq 0$ for the i.i.d. increments $X_i$), let $p_t(x)$ denote the probability measure of state $x \in L$ after $t$ ...
0 votes
0 answers
45 views

On full rank submatrices of a construction

Take two matrices $T_1$ and $T_2$ in $\mathbb Z^{n\times n}$ with entries uniformly in $[-b,b]\cap\mathbb Z$ at some $b>0$. The matrices will be of rank $n$ each with probability at least $1-\frac1{...
13 votes
1 answer
564 views

Coincidences between average Catalan tableaux

There are Catalan number $C_n$ of standard Young tableaux of shape $(n,n)$, which we view as $2\times n$ matrices. Denote by $P_n$ the average of these matrices: $$ P_n \, := \, \frac{1}{C_n} \, \...
8 votes
1 answer
270 views

Sizes of connected components from a random choice in a grid

This is inspired by the illustration in this recently updated question. So we take a (fairly big) $n$ and an $n \times n$ grid where we draw at random one diagonal in each of the $1 \times 1$ squares. ...
1 vote
2 answers
50 views

Cyclic inequality for 2 dimensional simplex elements

Let $p=(p_{1},p_{2},p_{3})\in\Delta$, with $\Delta:=\lbrace p\in(0,1)^{3}\ |\ p_{1}+p_{2}+p_{3}=1 \rbrace$. I aim to prove (not knowing whether it is true though) that \begin{equation} p_{1}^{p_{3}-p_{...
3 votes
1 answer
181 views

Infimum of weakly dependent Gaussian process?

Consider some collection of weakly dependent Gaussians $\{w_i\}$ with a uniform bound of $r$ on the magnitude of their covariances. Are there any bounds or techniques towards: $$E[\inf_i|w_i|] \le f(r)...
2 votes
1 answer
195 views

Average number of elements of a subset S of a matrix A after inducing the rows and columns of m randomly selected elements from subset S

Let $A_{N{\times}N}$ be an $N{\times}N$ matrix and $\mathcal{S_{k}}$ be a subset of elements in $A$ such that exactly $k$ elements from every row and column in $A$ are in $\mathcal{S_{k}}$. Thus, $\...
1 vote
0 answers
140 views

Count shortest path with different lengths in random graph

Let $G(n,p)$ be an Erdos-Renyi random graph on $n$ vertices with probability $p$, i.e. for each pair of vertices, they are connected directly by an undirected edge with probability $p$. Suppose we are ...
0 votes
1 answer
148 views

A tiling of $\mathbb{Z}^2$ from M. Barlow's paper

In M. Barlow's paper: arxiv.org/pdf/math/0302004.pdf, P17- (2.7) formula. Let $k\geq 10$, and consider a tiling of $\mathbb{Z}^2$ by disjoint squares $$T(x):=\{y\in \mathbb{Z}^2: x_i\leq y_i< ...
2 votes
3 answers
498 views

High order central moments of a symmetric binomial variable

Consider a random variable $X\sim B(n,\frac 12)$. I'm trying to estimate the asymptotic behaviour of its central moments $E((X-\frac n2)^r)$, where $r$ is even and in the range $\Omega(1)\leq r\leq O(...
0 votes
1 answer
260 views

Express inclusion-exclusion principle in terms of matrix operations

First of all i denote $\{1,2,3,...,m\}$ by $[m]$ Let there be a collection of sets $\alpha=\{A_{1},A_{2},...,A_{m}\}$ such $\bigcup_{i\in[m]}A_{i}\subseteq [n]$ Consider any function $f:\mathcal{P}([...
0 votes
1 answer
208 views

Local behavior of the Vandermonde convolution

An interesting combinatorial identity is the Vandermonde convolution identity: $$ \sum_k {n\choose k}{m\choose s-k} = {n+m \choose s},$$ which can be proved by considering the coefficients in $(x+1)^{...
9 votes
2 answers
878 views

Is there a combinatorial/topological treatment of statistical independence?

Is there any reference which studies sets of random variables as independence systems, a type of combinatorial object (see below)? Motivation: In particular, since independence systems are abstract ...
1 vote
0 answers
54 views

Age of the most recent common ancestor for the neutral Wright-Fisher model

The neutral Wright-Fisher model with $n$ individuals is a genealogical model often used in population genetics that can be described as follows: at all generations, there are exactly $n$ individuals, ...
6 votes
1 answer
361 views

Random walks on infinite directed regular graphs

Let us consider a directed graph $\Gamma=(V,E,s,t)$ ($V$ set of vertices, $E$ set of edges, $s,t: E \rightarrow V$ are the "source" and "target" maps). Assume that $\Gamma$ is bi-regular, that is ...
8 votes
2 answers
484 views

Inductive definition of Bernstein polynomials

For $n\in \mathbb{N}$ let $B_n$ be the linear operator taking a function $f$ on the unit interval $I=[0,1]$ to its $n$-th Bernstein polynomial $B_nf$, $$ B_nf(x):=\sum_{k=0}^n\binom{n}{k} f\Big(\...
1 vote
1 answer
436 views

Size of minimum cut in random graph

Consider a uniform random tournament with $n$ vertices. (Between any two vertices $x,y$, with probability $0.5$ draw an edge from $x$ to $y$; otherwise draw an edge from $y$ to $x$.) The score of each ...
11 votes
1 answer
284 views

Asymptotic distribution of $\lambda_1$ under the $z$-measure for partitions

The following question about $z$-measures on Young diagrams came up in some ongoing work with Ofir Gorodetsky. I recall the background and then state our question below in the box. For parameters $z$ ...
2 votes
1 answer
635 views

Azuma's Inequality when the conditions hold with high probability?

In Azuma's Inequality, is the statement true when $|X_k - X_{k-1}| < c_k$ almost surely rather than with probability 1? If not, is there another result which gives strong concentration when the ...
3 votes
0 answers
342 views

Sum of products of irreducible characters of the symmetric group over a subgroup

When trying to build a dual formulation for lattice gauge theories using Weingarten integration I am getting sums of the kind $$I^{m, n}_{\mu, \nu} (\sigma, \tau) = \sum_{\pi \in S_n} \chi_\mu (\pi \...
0 votes
0 answers
39 views

hypergraph product that preserve expansion properties

I am looking for a hypergraphs product of hypergraph H1,H2 that preserves some expansion properties of H1,H2. The expansion property I am looking at is HD-random walk. The product I am looking for is ...
0 votes
1 answer
101 views

Question of expected number of consecutive coin flip with increasing bias [closed]

This is a question I found on the book and I don't know how to tackle it. Thanks to any help or hint in advance. I have a coin that, I could get the head 100% at the first flip, $\frac{1}{3}$ at the ...
2 votes
0 answers
80 views

Small set in partition-large class

A collection $\mathcal{A}\subseteq \mathcal{P}(X)$ is $k$-large in $X$ if for every $k$-partition of $X$ namely $X_1,\cdots,X_k$, there exists an $i\leq k$ such that $X_i\in \mathcal{A}$; $\mathcal{...
1 vote
1 answer
107 views

Concentration of maxima of a random polynomial with Rademacher coefficients

Let $X_1,\ldots, X_n$ be independent Rademacher random variables (i.e. $\mathbb{P}(X_i=\pm 1)=1/2$). Consider the random polynomial $$P_{n}(t)=c+X_{1}t+X_2t^2+\cdots+X_{n}t^n.$$ Is it well known how ...
1 vote
0 answers
61 views

What is the minimal $m$ for which the independence graph is $n$-universal?

Suppose, an $m$ sided die is rolled. Let's define the independence graph $I_m$ as a graph with the set of all possible events as vertices, and edges between two events iff they are independent. ...
2 votes
1 answer
148 views

Reference request - parallel rectangles discrepancy theory

I've been reading about discrepancy theory and trying to understand some of the open problems in the field. Wikipedia has a list of some of the open problems, but the descriptions are terrible. In ...
2 votes
2 answers
185 views

Independence depth of linearly dependent random variables

Suppose, $\Xi$ is a collection of random variables. We call $\Xi$ $k$-independent, iff any $k$ distinct elements of $\Xi$ are mutually independent. For example, $2$-independence is pairwise ...
0 votes
1 answer
196 views

Coupling between two distributions

Consider $s = \Theta(n^{\delta})$ for a $\delta\in (0,1)$ and let $p\in (0,1)$ with $m = \lfloor pn\rfloor$. Consider the random variable $Y$ which chooses $m$ elements from $\{1,\ldots,n\}$ such that ...
1 vote
1 answer
519 views

How typical are integer isometries on a hypercube? Littlewood-Offord problem for Bernoulli Gram matrices

Let $m\geq 3$ be fixed and $n\to\infty$. Consider $v=(v_j)_{j\leq m}$ with $v_1,\ldots,v_m\in \{-1,+1\}^n$. Let: $N_I(v)$ be the number of sequences $u_1,\ldots,u_m\in \{-1,+1\}^n$ isometric to $v$ ...
0 votes
1 answer
165 views

Bound for Large deviations of sums of independent (not identical) variables

I am working with a sum of variables $X_i$; they are all independent, but not identically distributed. For any $i$, I can show the bound $$\Lambda^*_{X_i}(t) := \sup_t \langle t, x \rangle - \Lambda_X(...
5 votes
1 answer
980 views

"Nice" eigenvectors for (square of) adjacency matrix of a bipartite graph?

Let $G$ be a bipartite graph, and let $A$ be its adjacency matrix. I was wondering in this case whether $A^2$ will have nice eigenvectors that reflect combinatorial structure of the graph. I'd be ...
75 votes
11 answers
28k views

Does War have infinite expected length?

My question concerns the (completely deterministic) card game known as War, played by seven-year-olds everywhere, such as my son Horatio, and sometimes also by others, such as their fathers. The ...
0 votes
1 answer
171 views

Closed form solution for a binomial coefficient relation?

In following, $x_{n}$ is a set of given numbers, n = 0, 1, 2, ..., $y_{n}$ is defined by the following recursive relation of $x_{n}$: For example: ${\displaystyle {x_{1}=x_{0}y_{1} }}.$ ${\...
7 votes
3 answers
330 views

Quantifying the noninvertibility of a function

Given a function $f$ from a finite set $X$ to itself, it seems natural to consider $\kappa_f := (\sum_{x \in X} |f^{-1}(x)|^2)/|X|$ as a measure of the non-invertibility of $f$: it equals 1 if $f$ is ...
1 vote
2 answers
203 views

Moments of a combinatorial ensemble of random variables

Suppose $X_1,\dots,X_n$ are jointly distributed random variables such that the random $n$-tuple $(X_1,\dots,X_n)$ is uniformly distributed on the set of $n$-tuples of nonnegative integers summing to $...
6 votes
2 answers
266 views

Lovasz local lemma for the edge model

In order to successfully apply the Lovasz local lemma, one needs the events to be relatively independent. This (sometimes) works well in the $G(n,p)$ model of random graphs, where the presence or ...
3 votes
1 answer
307 views

Concentration of monochromatic edges in a graph

Let $G$ be a graph of order $n$ with $m$ edges. Color each vertices uniformly at random with $q$ colors. It is easy to see that expected number of monochromatic edges (edge whose end vertices are of ...
2 votes
2 answers
256 views

Model for random graphs where clique number remains bounded

In the Erdös-Rényi model for random graphs,the clique number is seen to go to infinity as the number of vertices grows. Is anyone aware of models for random graphs with bounded clique number?
0 votes
1 answer
187 views

Proof of consistent of height function

I have a question about the consistent of height function defined on a domino tiling. I always see papers claims that height function is defined consistently. But I am confused with the consistent. ...
12 votes
2 answers
406 views

Does asymmetric fraction of finite groups tend to $0$?

Let’s define asymmetric fraction of a finite group $G$ as the number $$\mathrm{af}(G) = \frac{|\{(g, a) \in G \times \mathrm{Aut}(G)\mid a(g) = g\}|}{|G|\cdot|\mathrm{Aut}(G)|}.$$ Equivalently it can ...
2 votes
0 answers
85 views

How fast does a sum of Bernoulli distributions (of different parameters) decrease after its mean?

Let $X=\sum_{i=1}^nX_i$, where each $X_i$ is a random variable following a Bernoulli distribution of parameter $p_i$. All $X_i$ are independent, and for all $i$, $p_i<p$ for some small $p$. I'm ...
2 votes
1 answer
165 views

Covering subset with large probability

Let $c>0$, $0<\lambda<1$, and let $k\in \mathbb{N}$ be sufficiently large. Let $X$ be a uniformly random subset of $\{1,\cdots,N\}$. Denote by $[N]^x$ the collection of $[x]$-element subset ...
4 votes
1 answer
275 views

Probability of a subset of Bernoulli's being all 1's

Suppose we have $n$ iid Bernoulli's $X_1,\ldots,X_n$ with mean $p$, and a family $\mathcal{F}$ of subsets of $[n]$. The question is how to lower bound the probability that there is a set in the family ...
4 votes
2 answers
145 views

Understanding equiprobable trinomial identity

With $f(x_1,x_2,x_3,x_1+x_2+x_3;\,1/3,1/3,1/3):= \frac{(x_1+x_2+x_3)!}{x_1!\,x_2!\,x_3!\, 3^{x_1+x_2+x_3}}$ denoting the probability mass function of the equiprobable trinomial distribution as in wiki/...
1 vote
0 answers
130 views

Probabilistic lower bound on largest singular value of matrices

I have a distribution $\mathcal{D}$ that spits out vectors in $\{-1, 1\}^N$. Suppose I have a sample of $H$ of these vectors which I arrange into a matrix $M$ of the form $H \times N$. Consider the ...
4 votes
1 answer
272 views

How far do I have to go for the tail of a binomial distribution with small $p$ to be $O(1/n)$?

Let $n$ be a large integer, $p$ be a small number (say, $p=C/n$ for some constant $C \ll n$), and consider the tail of the binomial distribution $B(n,p)$, after $T$: $$ \delta = \sum_{s=T}^{n} p^s (1-...
5 votes
1 answer
301 views

Convexity of the expectation of boolean functions

Let $$f:\{-1,1\}^n \to \{-1,1\}$$ be a monotone, odd ($f(-x)=-f(x)$) Boolean function. Let $$F:[0,1]\to[0,1]$$ denote the probability that $f(x_1,...,x_n)$ where $x_1,...,x_n$ are i.i.d. $\pm1$ R.V. ...
4 votes
1 answer
115 views

What is the probability of an empty convex $k$-gon among many given points?

Given a finite number of points in the plane in general position, call a convex subset empty if its hull doesn't contain any other of the points. For a big number $n$ of randomly distributed ...
12 votes
2 answers
947 views

How rare are unholey permutations?

For $S\subset [n]:=\{1,2,\dotsc,n\}$, define $\delta(S)$ to be the number of $m\in S$ such that $m+1\notin S$. Given a permutation $\pi$ of $[n]$, we define the holeyness $D(\pi)$ of $\pi$ as being $...
4 votes
0 answers
216 views

How frequent are permutations with small interleaving?

For $S\subset [n]:=\{1,2,\dotsc,n\}$, define $\delta(S)$ to be the number of $m\in S$ such that $m+1\notin S$. Let $\pi$ be a permutation of $[n]$. For simplicity, assume that $\pi$ is an $n$-cycle. ...

1
4 5
6
7 8
17