Skip to main content

All Questions

Filter by
Sorted by
Tagged with
12 votes
3 answers
1k views

A Modern Proof of Erdos and Renyi's 1959 Random Graph Paper?

In their paper, Erdos and Renyi consider a random graph with a fixed number of edges, as opposed to the more modern approach of adding each edge independently with probability $p$. From what I ...
Sam Spiro's user avatar
  • 470
7 votes
1 answer
876 views

What is the six positive real number for a dice producing a highest chance?

Say there is a dice with six faces, each face has a positive real number different from others. There is a chessman on the origin of the number axis. In each trial, the dice rolls infinite times. ...
rube wang's user avatar
  • 143
7 votes
0 answers
171 views

What is known about the distribution of lengths of the cycle you get by adding an edge to a uniform spanning tree?

Let $G$ be a finite, connected graph. Let $T$ be a uniform spanning tree, and let $e$ be a uniformly random edge not in $T$. When we add $e$ to $T$, we get a subgraph with a unique cycle, $C$. I am ...
Elle Najt's user avatar
  • 1,462
2 votes
1 answer
607 views

Component size distribution in small Erdos-Renyi networks

I'm looking at $\mathcal{G}(n,p)$ (I'll call these Erdos-Renyi networks) where $n$ is, say, at most 10. I would like to know the probability a random node is in a component of size $m$. It's ...
Joel's user avatar
  • 121
3 votes
1 answer
167 views

Lower bound on the sum of pmf squared of a hypergeometric distribution

I am working on a proof of correctness for an algorithm I came up with. I encountered the following problem en route. I would appreciate if anyone had some idea or could point me to the relevant ...
User93's user avatar
  • 33
5 votes
1 answer
281 views

Transfer-impedance matrix for edge correlations in random spanning tree

Suppose $G$ is a (weighted) connected graph and let $T$ denote a random spanning tree of $G$, chosen uniformly (or respecting the edge weights). It is known that for any distinct edges $e, f$ $$\...
Harry Richman's user avatar
2 votes
1 answer
188 views

Colored balls and bins -- asymptotic behavior

Suppose I have $N$ bins and a set of balls with $m$ different colors, where there are $n_i$ balls of color $i$. I also have values $0 < p_i \leq 1$ for all colors $i$. I throw all $\sum_i n_i$ ...
Tom Solberg's user avatar
  • 4,049
4 votes
1 answer
648 views

What is the probability for a Binomial to be greater than other?

Let $X = B(n, p)$ and $Y = B(k, q)$ be two random variables with binomial distribution and, let $s$ be a positive integer. Assume that $n > k+s$ and $np \geq kq+s$. What is the probability for $X$ ...
Mohamad Latifian's user avatar
4 votes
1 answer
239 views

$Pr(A>B)$, where $A$ and $B$ are sum of Bernoullies

Let $X= x_1 + x_2 + \ldots + x_m$, $Y=y_1 + y_2 + y_3 + \ldots + y_n$, and $Y' = y'_1 + y'_2 + \ldots + y'_n$, where Each $x_i$ is a Bernoulli variable which takes value $1$ with probability $p_i>...
Masood's user avatar
  • 169
2 votes
0 answers
78 views

Width of symmetric groups

MSE crosspost For any (finite) group $G$ its length $l(G)$ is the length of maximal chain of proper subgroups (it's known and pretty widely used invariant). But we can also define width function $w_G(...
Denis T's user avatar
  • 4,600
2 votes
1 answer
90 views

Generalization: (The "number" of) smaller sized clusters in large random binary matrices follow a descending order. Why?

This is a sequel to the question: Why is number of single cell clusters always greatest in a random matrix? In their answer, @Aaron Meyerowitz came up with a nice strategy to prove why the number of ...
user avatar
3 votes
1 answer
184 views

Why is number of single cell clusters always greatest in a random matrix?

Consider a large $N\times N$ square lattice, where each cell has a probability $p$ of being "occupied" (let's call denote them as "black") and a probability $1-p$ of being empty (let's denote them as "...
user avatar
15 votes
1 answer
1k views

Math journal publishing work related to combinatorics, probability, counting problems etc.?

I'm a high school student. My peer and I have done some work on the Ballot Theorem counting problem and Catalan Numbers. We have come up with a new proof to the Ballot Theorem and we demonstrate the ...
0 votes
0 answers
119 views

the enumeration of 2 dimensional lattice walks with fixed number steps and largest distance from the end point ti the origin

There is actually an one dimensional version of this problem. For each step of the lattice walk, we can move either east for one unit or west for one unit. The problem is that given a fixed $n$ steps ...
Mclalalala's user avatar
5 votes
1 answer
340 views

Show a sequence of sums involving Catalan Numbers converges

Let $C_n$ be the $n$-th Catalan Number and let $\mathcal{O}_{s,j} = {{2s-j-1}\choose{j}} C_{s-j}^2$. Then we want to consider $\mathcal{E}_s = \sum_{j=0}^{s-1} (-1)^j\mathcal{O}_{s,j}$. We want to ...
N. Owad's user avatar
  • 313
3 votes
1 answer
228 views

Density of a somewhat random set

The density of a set $X\subseteq\omega$ refers to: $\limsup\limits_{n\rightarrow\infty}\dfrac{C\cap n}{n}$. Given a set of positive integers $F= \{m_0<\cdots<m_{k-1}\}$, let $C\subseteq \omega$...
Jiayi Liu's user avatar
  • 909
1 vote
1 answer
114 views

Probability for a group of stones to live on an infinite Go board

Suppose on an infinite two dimensional Go board the tengen is occupied by a black stone, and every other grid point is occupied by a black stone, or a white stone, or nothing, with probability 1/3 ...
Fan Zheng's user avatar
  • 5,169
3 votes
2 answers
503 views

Lower bound for the probability of binomial variable to be less than her expectation

Let $X$ a binomial variable of parameter $(N,p)$, with $0<p<0.5$ I would like to lower bound $\mathbb{P}\left(X <Np \right)$ by a constant ($\frac{1}{5}$ seems true and is enough for me). ...
Ievgeni's user avatar
  • 215
7 votes
3 answers
790 views

Expected cardinality of a randomly chosen element of the family of subsets of $\{1,\ldots,n\}$ with at most $k$-elements

Assume that $1\le k \le n$ and let $\mathscr{Z}$ be the family of all subsets of $\{1,\ldots,n\}$ with at most $k$ elements. Pick a random element $X$ of $\mathscr{Z}$ (we consider the probablity ...
Dominik Kwietniak's user avatar
7 votes
1 answer
390 views

Combinatorial/probabilistic statements having $F_{\text{un}}$/$F_q$ geometric interpetation

$\newcommand{\Fun}{F_\text{un}}$There was lots of "Fun with $\Fun$" (field with one element) in recent years. One of the points is that it provides bridge between geometrical and ...
Alexander Chervov's user avatar
11 votes
3 answers
243 views

How many operad structures are there on the symmetric sequence of simplices / finitely-supported probability measures?

Consider the symmetric sequence $P_n = \Delta^{n-1}$ of probability measures on finite sets, with coordinatewise $\Sigma_n$-action. There is a natural topological operad structure on $P$ given by ...
Tim Campion's user avatar
  • 63.9k
0 votes
0 answers
72 views

Generating function for number of r-disjoint subsets each of size k

Fix $n, k$. Let $$ C^{n,k}_r =\frac{1}{r!} \binom{n}{\underbrace{k, \ldots, k}_{\text{r times}}, n-rk} = \frac{n!}{r!(k!)^r(n - kr)!} $$ be the number of ways to form $r$ disjoint subsets each of ...
Miheer's user avatar
  • 101
2 votes
1 answer
508 views

Proof and interpretation of the following percolation theory result for $n\times n$ square grid

While I was discussing this question with @JamesMartin, he mentioned a result here that: In a $n\times n$ finite square grid, if $p\geq p_c+\epsilon$, such that $\epsilon>0$ and $p_c$ is the ...
user avatar
2 votes
1 answer
299 views

Can this particular random matrix model be converted/related to any existing graph theory model?

Context: This a sequel to the question: Is the Erdős–Rényi giant component result applicable here? Consider a matrix whose elements are independently assigned a value $1$ with probability $p$ ...
user avatar
-1 votes
1 answer
76 views

Transforming random variables for having good property?

For arbitrary functions $A$ and $B$ and independent random variables $X$ and $Y$, assume that \begin{align} \Omega&\triangleq \{(x,y): A(x,y)=1\},\\ \Lambda&\triangleq \{x: B(x)=1\}. \end{...
Math_Y's user avatar
  • 287
2 votes
2 answers
357 views

Is the Erdős–Rényi giant component result applicable here?

Consider a matrix whose elements are independently assigned a value $1$ with probability $p$ and a value $0$ with probability $1-p$. Define a cluster of cells as a maximal connected component in the ...
alphauser's user avatar
2 votes
1 answer
132 views

Independent decomposition of coordinate distribution

Let $\mathbf{x}$ be a random Gaussian vector in $\mathbb{R}^n$, i.e. $\mathbf{x}\sim\mathcal{N}(\mathbf{0},\mathbf{I}_n)$. Then for any fixed unit vector $\mathbf{u}$, one has $\mathbf{u}\mathbf{u}^\...
Wuchen's user avatar
  • 515
3 votes
0 answers
116 views

Trace of Symmetric matrices in fixed rank

I am solving some problem related to symmetric matrices over a finite field $\mathbb{F}_q$ and I am stuck at the following problem: For every $a\in\mathbb{F}_q $, let $S_a(t,m)$ be the set of all $m\...
Singh's user avatar
  • 179
3 votes
0 answers
178 views

Partitioning the coupons collected in the classical coupon collector's problem

Suppose that there is an urn containing $n$ different coupons, from which $m$ coupons are being collected, equally likely, with replacement. Let $C(m)$ be the whole set of the $m$ collected coupons. ...
Penelope Benenati's user avatar
4 votes
2 answers
261 views

Probability question about random shuffling of piles of rocks

I have $k$ piles of rocks placed on a circle so that every pile has exactly two neighboring piles. We know that initially the piles have $x_1,\dots,x_k$ rocks in each respectively. A monkey plays the ...
David's user avatar
  • 41
8 votes
2 answers
240 views

Mixed moments for the birthday problem

Let $X_1,X_2,\dots$ be iid draws from the uniform distribution on $\{1,2,...,m\}$, and let the random variable $N$ be the minimum $j$ such that $X_j = X_i$ for some $i<j$. I'm aware that the ...
James Propp's user avatar
  • 19.7k
4 votes
2 answers
432 views

How to prove the sum of n squared binomial probabilities does not increase as n increases

Let $F\left( n \right) = \sum\limits_{k = 0}^n {{{\left( {C_n^k{p^k}{{\left( {1 - p} \right)}^{n - k}}} \right)}^2}} $, prove $F\left( n \right) \ge F\left( {n + 1} \right)$. UPDATE: More general, ...
Jack's user avatar
  • 43
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$ ...
Brad Rodgers's user avatar
  • 2,151
4 votes
0 answers
111 views

Set version of ramsey type problem

For two sets of numbers $A,B$, write $A<B$ iff $\max A<\min B$. For a sequence of integers $a_0,\cdots,a_{n-1}>0$, let $Prop(a_0,\cdots,a_{n-1})$ denote the following proposition: Given $n$ ...
Jiayi Liu's user avatar
  • 909
6 votes
1 answer
349 views

Ramsey type theorem

Let $\mathcal{P}(\{0,\dotsc,7\})$ denote the power set of $\{0,\dotsc,7\}$. Is the following true? For any function $f: \mathcal{P}(\{0,\dotsc,7\})\rightarrow\{0,1\}$ there exists $0\leq k\leq 3$ ...
Jiayi Liu's user avatar
  • 909
11 votes
1 answer
867 views

Simulate coin tossing by die tossing

On the one hand we toss $n$ times a fair coin, and we sum the outcomes (+1 for heads, -1 for tails). Let $f:\mathbb{N}\to\mathbb{R}$ describe the probability distribution of the outcome. On the other ...
smapers's user avatar
  • 338
1 vote
1 answer
188 views

KPZ relation $\chi = 2 \xi -1$ in a random geometric graph

If I have $n$ points uniformly distributed on the surface of a torus, and form a graph by adding an edge between pairs whenever they are within a unit distance (induced by the Euclidean metric), I ...
apg's user avatar
  • 640
6 votes
1 answer
224 views

A Markov consensus

Consider the following process. You start with $n$ nodes in different colors $c=c1,c2,...$ (representing an opinion). Say, $n=5, c=1,2,3,4,5$. Now each node checks which colors have weak majority (...
Hauke Reddmann's user avatar
4 votes
0 answers
355 views

Distribution of min/max row sum of matrix with i.i.d. uniform random variables

Given a $n\times n$ symmetric random matrix such that all diagonal elements are all fixed as $1$. all elements in upper triangle (excluding the diagonal) are i.i.d. uniform random variables ...
Tony's user avatar
  • 272
2 votes
0 answers
59 views

Min/max row-sum distribution of a symmetric matrix of uniform random variables over $[0,1]$ and fixed $1$s along diagonal and scattered $1$s

Given a $n\times n$ symmetric random matrix such that all diagonal elements are all fixed as $0$. randomly select $k$ distinct cells in the upper triangle (excluding the diagonal), and then ...
Tony's user avatar
  • 272
7 votes
1 answer
880 views

Bound for largest eigenvalue of symmetric matrices of uniform random variables over $[0,1]$ and fixed $1$s along diagonal and scattered $1$s

Given a $n\times n$ symmetric random matrix whose diagonal elements are all fixed as $1$. In addition, there are $k$ $1$s will be randomly scattered in upper triangular (of course, the corresponding ...
Tony's user avatar
  • 272
1 vote
1 answer
154 views

Is the Krawtchouk ensemble a determinantal process?

The Krawtchouk ensemble is defined by a weight: $w(x) = \binom{K}{x}p^x q^{K-x} $ and in fact it comes from a conditioned random walk on $\mathbb{Z}^N$. It is a probability measure on the set $\{ 0, ...
john mangual's user avatar
  • 22.8k
3 votes
2 answers
1k views

Proof of identity involving Stirling numbers of the second kind

While computing conditional expectations of certain functionals of a Poisson white noise field (details are long and probably irrelevant), I've stumbled upon the need to use the following identity ...
Rodrigo Vargas's user avatar
2 votes
1 answer
266 views

A question about finite free convolution

For any square matrix $Y$ let $\chi_x(Y) = det(xI -Y)$ denote its characteristic polynomial. Say $A$ and $B$ are two $n-$dimensional symmetric matrices with constant row sums $a$ and $b$. Lets ...
gradstudent's user avatar
  • 2,246
5 votes
0 answers
352 views

0-1 matrix combinatorial problem

Let $M \in \{0,1\}^{n \times n}$ and let $r_i$ be its $i$-th row. Given constant $p \in (0,1/2]$, let the number of $1$s in each row be at least $p\,n$. Given constant $c \in (0,1)$, what is the ...
Penelope Benenati's user avatar
3 votes
2 answers
228 views

Percolation on finite irregular trees

Consider a rooted tree of height $h$, such that all the leaves are at last layer. We perform the following random process: each edge is deleted with probability $0.5$, and otherwise it is retained. We ...
Or Meir's user avatar
  • 419
3 votes
0 answers
89 views

Two game-set inequalities

Here are a couple of curious related results about a generalized 2-player 1-set tennis game: the winner of the set is the first player to win $n$ games, and the winner of each game is the first player ...
Alexander Burstein's user avatar
6 votes
0 answers
105 views

Long loops in critical random graphs

A simple calculation seems to show that the expected number $X_k$ of loops of length $k$ in a critical Erdös-Renyi random graph $G(n,n^{-1})$ is approximately given by $$ \mathbb{E} X_k=\frac1{2k}{e^...
Johannes Kleinholz's user avatar
8 votes
1 answer
198 views

Tail bound of a distribution

Let $X_1, X_2, \ldots, X_n, Y_1, Y_2, \ldots, Y_n$ be independent binary random variables each being $1$ with probability $\frac{1}{k}$. Let $Z = X_1(Y_1 + \cdots + Y_k) + X_2(Y_2 + \cdots + Y_{k+1})...
user47772's user avatar
  • 305
6 votes
1 answer
370 views

Mean minimum distance for M and N uniformly random points on reals between 0 and 1

Similar to Mean minimum distance for N random points on a one-dimensional line, but instead of only N random points, choose N and M random points and find the mean minimum distance between points of N ...
J. Smitherson's user avatar

1
5 6
7
8 9
17