All Questions
45 questions
3
votes
1
answer
405
views
Moments of a random variable related to uniform distribution on sphere
Let $u$ be taken uniformly from the unit sphere $\mathbb S^{n-1}$ and $D$ be a diagonal matrix. I'd like to find a general formula for
$$
\mathbb E[(u^\top D u)^m]
$$
for $m=1,2,3, \dots$, in terms of ...
- 188k
4
votes
1
answer
261
views
What is the convergence rate of this "infinite monkey"-type probability?
Cross-posted from Math Stack Exchange, where it hasn’t received an answer yet:
Let $S$ be a finite set and $n,m\in\mathbb N$. Consider the process $R=(R_i)_{i\in\mathbb N}$ where all $R_i$ are iid ...
- 1,043
13
votes
3
answers
1k
views
A property of unimodal sequences
It is well-known that $(-1)^j \sum_{i=0}^j (-1)^i\binom{n}{i} \geq 0$. This inequality can be used to prove Bonferroni's inequalities for example. Recently I noticed that a similar inequality applies ...
- 97
0
votes
0
answers
55
views
Modeling player interactions in multi-dimensional rating systems
In traditional rating systems (such as Elo), a player's strength is represented by a single scalar value, which is assumed to be consistent across different opponents. However, in some games, the ...
- 1
1
vote
0
answers
91
views
Large deviation inequalities for number of coupon types collected by a coupon collector with fixed budget
In the generalized Coupon Collector's Problem, there are $N$ types of coupon, and for any $i \in [N] := \{1,2,\ldots,N\}$, $p_i \ge 0$ is the probability of obtaining a type-i coupon on any trial. ...
- 6,853
4
votes
1
answer
197
views
On a double sum involving binomial coefficients
For natural $n$, let
\begin{equation}
p_n:=2^{1-n}\sum_{v=1}^l \binom l{(v+l)/2}1(v\equiv l)
\sum_{u=1-v}^{v-1}\binom k{(u+k)/2}1(u\equiv k), \tag{1}\label{1}
\end{equation}
where $k:=\lfloor(n+1)/...
- 311
9
votes
1
answer
1k
views
The length of the longest consecutive string of heads or tails that occur asymptotically almost surely when a unbiased coin is flipped repeatedly
Consider an unbiased coin being flipped $n$ times, and suppose we label the outcomes as Heads = 0, and Tails = 1. Then the result of the flipping is a finite binary sequence of length $n$. Let us ...
- 10.4k
3
votes
1
answer
229
views
Maximum cardinality of separated sets in the Hamming distance
This question is motivated by section 15.1 (Codes) of Alon and Spencer's The probabilistic method.
Fix $\alpha<\frac{1}{2}$ and for each $n\in\mathbb{N}$ let $\{0,1\}^n$ be the length $n$ binary ...
- 10.4k
3
votes
1
answer
266
views
A linearly distributed version of the balls into bins problem
Some years ago, I found a paper with all the formulas for the balls into bins problem when the "areas" (i.e., probabilities to capture a ball) of the bins are all different. However, the ...
- 1,677
7
votes
1
answer
186
views
$d$-ball approximation for $d\gg 1$ with a convex hull of random points on its boundary
Given a $d$-ball $\mathcal{S}^{d}$, let $P_n$ a set of $n$ points selected uniformly at random on the boundary $\mathcal{S}^{d-1}$ of $\mathcal{S}^{d}$. Let $\mathcal{C}_n$ the convex hull of $P_n$. ...
- 1,043
15
votes
1
answer
1k
views
Has the technique of "sprinkling" been used in studying random matrices?
In 1982, while studying the component sizes of random subgraphs of a hypercube, Ajtai, Komlós, and Szemerédi introduced a technique that came to be known as sprinkling. In this technique, the edges of ...
- 114k
2
votes
1
answer
199
views
Do enough permutations of an initial set probably cover most permutations?
Fix $\alpha, \epsilon \in(0,1)$. Take $(S_n)_n$ to be any sequence of sets with each $S_n$ containing $ \lceil (n!)^\alpha\rceil$ permutations of $n$ elements. Also build another sequence of sets $(...
12
votes
1
answer
883
views
The dance marathon problem
In his book, "The Strange Logic of Random Graphs", Joel Spencer describes the "Dance Marathon" problem:
Imagine $n$ couples at a Dance Marathon. Each dance each couple remains ...
- 63.9k
8
votes
0
answers
181
views
Self-avoiding walks on strips
A strip is a locally finite graph which admits a quasi-transitive (i.e. finitley many orbits on vertices) action of $\mathbb Z$. A self avoiding walk is a walk which visits no vertex more than once.
...
- 2,671
19
votes
5
answers
18k
views
Time-inhomogeneous Markov chains
I'm trying to find out what is known about time-inhomogeneous ergodic Markov Chains where the transition matrix can vary over time. All textbooks and lecture notes I could find initially introduce ...
- 63.9k
3
votes
1
answer
229
views
Inequality for difference of consecutive atom probabilities for binomial distribution
Edit: This post was originally two questions, the first of which has been answered, but a reference would still be appreciated if existent. The second question has been removed and migrated to its ...
- 2,720
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$ ...
- 63.9k
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_{...
- 128k
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 ...
- 24.2k
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 $...
- 3,255
3
votes
1
answer
341
views
Spectral radius of Markov averaging operator on graphs
The definition of Markov operator which I am familiar with:
For a graph $G=(V,E)$, Markov's operator upon a function
$\varphi:V\rightarrow\mathbb{C}$ , $\varphi\in L^2(G,\nu)$ ($\nu(v):=\deg(v)$) ...
- 33
1
vote
2
answers
116
views
How to use probability to find a matching in a family of graphs?
In a conference, I heard that we can use some probabilistic methods to find a matching in some kind of graphs. I would like to see some examples of such technics. Can someone provide some references ...
- 14.2k
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 ...
- 1,462
16
votes
3
answers
918
views
What is the minimal $C_k$, such that every $f\colon \{-1,1\}^n\to \mathbb{R}$ of degree at most $k$ satisfies $\|f\|_2\le C_k\|f\|_1$
Every $f\colon\{-1,1\}^n\to \mathbb{R}$ can be repsenented as a multilinean polynomial of the form $$f(x_1,x_2,\ldots ,x_n)=\sum _{S\subseteq [n]} \hat{f}(S)\prod_{i\in S} x_i $$ The degree of the ...
- 3,946
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$
$$\...
- 13.6k
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 ...
- 1,658
7
votes
2
answers
3k
views
The largest Wasserstein distance to uniform distribution among all probability distributions with uniform marginals
I am looking for the largest Wasserstein distance to the uniform distribution among all probability distributions with uniform marginals.
More specifically, let $\Xi=\{1,2,\ldots,N\}^2$, and let $\nu$...
- 1
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^...
- 2,175
2
votes
0
answers
91
views
Semigroups of nondecreasing functions
Consider some partially ordered set $(E,\leq)$. Assume either that it is countable with the discrete topology, or that it has some topology compatible with the order, preferably one that makes it into ...
4
votes
0
answers
188
views
Distributions over permutation groups $\mathcal{S}_n$
Partly inspired by recent developments in enumeration of pattern avoiding permutations, which is known to be connected with Brownian excursions [Hoffman&Rizzolo]. The exciting milestone is the ...
- 8,071
8
votes
2
answers
512
views
The average of reciprocal binomials
This question is motivated by the MO problem here. Perhaps it is not that difficult.
Question. Here is an cute formula.
$$\frac1n\sum_{k=0}^{n-1}\frac1{\binom{n-1}k}=\sum_{k=1}^n\frac1{k2^{n-k}}...
CommunityBot
- 1
9
votes
0
answers
1k
views
Balls and bins -- concentration bounds pertaining to the minimal load bin
Consider the standard balls and bins process, where $m$ balls are thrown uniformly at random into $n$ bins. Previous work has been done on estimating the value of the maximum load (i.e., the number of ...
- 618
3
votes
0
answers
303
views
Exchangeable or iid random variables and linear conditioning
Let $X_1,\ldots ,X_N$ be independent identically distributed random variables (or, more generally, exchangeable random variables,
but let's assume independence for simplicity). Then
$$
E(X_i\mid X_1+\...
- 1,765
2
votes
1
answer
177
views
Representations of zero as the sum of integers
Considering certain random walks I came up with the following question: Given a finite set $A$ containing positive and negative integers, how many representations of zero as the sum of $n$ integers ...
- 1,305
1
vote
1
answer
95
views
Reference for a local density theorem for binary vectors
I have the following theorem written on my whiteboard, but have misplaced the reference. I believe the probabilistic method may be involved in the proof. Any pointers appreciated.
Theorem Let $v\in\{...
- 10.4k
11
votes
0
answers
282
views
Reference request: a combinatoric result [closed]
When I tried to construct a counterexample in my research, I encountered the following result, which should be true.
Let $m=m(n)$ be a function that grows faster than $\sqrt n$, so $m(n) = \omega(\...
CommunityBot
- 1
1
vote
0
answers
339
views
Occupancy problem with limited capacity and two types of balls [closed]
I am considering the following problem that I suspect to be standard.
One has a set of $N$ balls composed of a fraction $\alpha$ of red balls and $(1-\alpha)$ of black balls (we assume $\alpha N$ is ...
- 9,650
9
votes
0
answers
778
views
Faa di Bruno and Free Probability?
It is possible to glean many combinatorial identities using Faa di Bruno’s formula for the coefficients of higher derivatives of a composite function. For many examples, see David Vella’s paper. The ...
- 10.5k
1
vote
0
answers
255
views
An extrasensory perception strategy :-)
I asked this question at MSE some months ago
but I received only partial answers, so I put it here. The following sounds nice for me and I spent a good time during the investigation. But I am a ...
CommunityBot
- 1
5
votes
0
answers
215
views
Asymptotics of a Splitting Process
Consider $p(n)$ defined recursively by $p(1)=1$ and
$\displaystyle p(n)=\frac{1}{(n-1)^n}\sum_{i=1}^{n-1}\left\{\sum_{j=i}^{n-1}(-1)^{j-i}{n \choose j}{j\choose i}(n-j)^j(n-j-1)^{n-j}\right\}p(i)$.
...
CommunityBot
- 1
9
votes
2
answers
441
views
From very many sets of fixed measure in a probability space, can we select many that have a positive intersection?
I assume the following Lemma is either well known or, more probably, a
Corollary of a much stronger well known Theorem, and I would be grateful for a
reference:
For all $\delta\in (0,1)$ and all $\...
- 894
3
votes
1
answer
253
views
Bounds for duplicate finding with limited independence
(This is a follow up to this previous question on math.stackexchange.com.)
Assume a process that samples uniformly at random from the range $[1,\ldots,n]$. I am interested in the time to find a ...
CommunityBot
- 1
4
votes
1
answer
151
views
Mean occurrences of letters in complete strings given by a Bernoulli scheme
Suppose one has an alphabet of $K$ letters, from which we draw sequentially letters; assume that the $n$-th letter occurs with a fixed probability $p_n$ independently of the others and of the previous ...
- 96.4k
5
votes
0
answers
227
views
Number of times lead changes in a multi-candidate election (reference-request)
In a two candidate election where votes are distributed uniformly at random between the candidates, the probability that the lead changes when tallying the $i$-th vote is the same as the probability ...
- 51
13
votes
2
answers
3k
views
The probabilistic method - reference to less challenging questions
I am teaching a course in combinatorics and large part of it is dedicated to the probabilistic method especially in the case of graphs. The course is an undergraduate level (almost none of the ...
- 502