All Questions
Tagged with pr.probability co.combinatorics
802 questions
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 ...
- 393
3
votes
3
answers
3k
views
Expected Number of Bernoulli trials before you get N more heads than tails
Hello,
I'd like to find the expected number of Bernoulli trials that I'll need before I will get exactly n more heads than tails, given a coin which gets a heads with probability p.
My approach ...
3
votes
1
answer
539
views
Probability of generating the symmetric group
The statement is simple:
What is the probability that a set of n-1 transpositions generates the symmetric group, $S_n$?
The motivation is that I remembered reading that this was an open problem ...
- 543
3
votes
4
answers
1k
views
Apply doubly stochastic matrix M to a probability vector, then entropy increases?
Consider a vector $p =(p_1,\dots,p_n)$, $p_i>0$, $\sum p_i = 1$
and a matrix $M_{ij}$, which is doubly stochastic: $\sum_i M_{ij} = 1, \sum_j M_{ij} = 1, M_{ij} > 0$.
Question 1 Just apply ...
- 24.9k
3
votes
2
answers
946
views
Cardinality of intersection of a random subset with a fixed subset
How can I simply prove the following fact:
Let $A := \{1, \dots n \}$ and $B := \{1, \dots, \lfloor \frac{n}{4} \rfloor \}$. Let $d \in (0,1)$ and let $R$ be a randomly choosen (with uniform ...
- 395
3
votes
3
answers
942
views
implementations of domino shuffling algorithm
Are there many implementations of the "domino shuffling" algorithm as found in William Jockusch, James Propp amd Peter Shor's Random Domino Tilings and the Arctic Circle Theorem math.CO/...
- 22.8k
3
votes
1
answer
315
views
Distribution of the first occurrence of a maximum (record) run of zeros in the digits of a normal number (say $\pi$)
If the question was stated to appeal to the general public, it would be something like this. For a number such as $\pi$ or $\sqrt{2}$, the digits in base $b$ appear to be randomly distributed. We are ...
- 3,098
3
votes
1
answer
1k
views
How many times does a simple symmetric random walk of length n return to the origin?
Consider the simple symmetric random walk on the integers starting from
the origin of length $n$. More precisely, I will denote an $n$ step random walk $w$ as
$$ w:= \omega_0 \omega_1 \ldots \...
- 3,245
3
votes
2
answers
251
views
Designing a tree to match a distribution
I want to design a tree to approximate a given
sequence of numbers, in the following sense.
Let $X=(x_1,\ldots,x_n)$ be $n$ numbers, with $0 < x_i \le 1$
and $\sum_i x_1 = 1$.
For a rooted tree $T$,...
- 151k
3
votes
2
answers
421
views
Sufficiently random sample
Let $d$ be an integer $\geq 2$, and let $\Omega = \lbrace 0,1 \rbrace^d$, $A \subseteq \lbrace 0,1 \rbrace^2 $ and $i,j$ integers with $1 \leq i < j \leq d$. If we select an element $(x_1,x_2, \...
- 3,595
3
votes
1
answer
610
views
Looking for a probability distribution
Recently I discussed an experiment with a friend. Assume we start a random experiment. At first there is an array with size 100 000, all set to 0. We calculate at each round a random number modulo 2 ...
- 133
3
votes
1
answer
822
views
Open Problems in Random Graphs [closed]
I am a PhD student in mathematics. I'm interested in probabilistic methods in combinatorics and especially random graphs. I am looking for an open problem in this area for my PhD proposal. I know that ...
- 57
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).
...
- 215
3
votes
1
answer
266
views
Probability that a randomly filled Go board has a set of white stones connected through their von Neumann neighborhoods
I have an $N$ by $M$ grid (a Go board for example), where for every square in the grid, I place a white stone with probability $p$ and a black stone with probability $(1-p)$. We call two white stones ...
- 67
3
votes
2
answers
257
views
Grouping lists together in a proportional election: image of a Dirichlet distribution by the D'Hondt method of proportional allotment
A real-world motivation for this question is given below. But first let me recall what the Jefferson-D'Hondt “greatest divisors” method of proportional allotment (often used in electoral systems to ...
- 32.5k
3
votes
1
answer
271
views
The number of $3$-CNF formulas in $n$-variables and the fraction of satisfiable ones
What is the number of $3$-CNF (conjunctive normal form) formulas with $n$ sentential variables and what is the fraction of satisfiable ones? I consider two formulas the same if they are syntactically ...
- 33
3
votes
1
answer
162
views
Probability permutation in turned to cycle
Let $M$ be a $0/1$ square matrix having one $1$ per row and column (permutation matrix).
If you permute the columns and rows independently what is the probability resulting permutation matrix is a ...
- 13.9k
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
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 ...
- 419
3
votes
2
answers
706
views
Birthday inequality for non-uniform distributions for fixed collision probability (random allocation, collision probability)
Question: Consider a distribution $D$, and $n$ i.i.d. random variables $X_i$, all distributed according to $D$. Let $p^D_2:=\Pr[X_1=X_2]$. What is a lower bound for $p^D_n:=\Pr[\exists i\neq j. X_i=...
- 896
3
votes
1
answer
179
views
Domino Shuffling and Warren's process
In this paper by Nordenstam, it is shown that a certain interlacing particle process that arises from uniformly random Aztec diamond tilings is amazingly similar to Warren's process. One of the ...
- 4,952
3
votes
1
answer
220
views
Number rank-k 0-1 matrices (characteristic 0)
What is the number of $n\times n$ 0/1-matrices with rank $k$?
(The rank is taken over the rationals.)
- 103
3
votes
1
answer
1k
views
Cumulative distribution function of hypergeometric distribution
Does anyone know a closed form or a good approximation of the cumulative distribution function of hypergeometric distribution?
- 177
3
votes
1
answer
927
views
How to choose $L$ size-$m$ subsets of $\{1,\ldots,n\}$ to maximize expected max overlap with another randomly chosen subset?
GIVEN: Positive integers $n,m,L$ and probabilities $p_1, p_2, \ldots, p_n$.
GOAL: Choose $L$ size-$m$ subsets $S_1, S_2, \ldots, S_L$ of $\{1,2,\ldots,n\}$ to maximize $\displaystyle \mathbb{E}[ \...
- 31
3
votes
1
answer
208
views
The signs of some mean-zero random variables
Let $X$ be a discrete random variable supported on $\{−5,\dots, 6\}$ in which the outcomes have the following respective probabilities: $$\begin{array}{rc}
n & p(n) \\ \hline −5 & 6/36 \\ −4 &...
- 19.7k
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.6k
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
3
votes
1
answer
135
views
Cycle counts in Ewens measure as $\theta$ diverges
For $w$ a permutation, let $c(w)$ denote the total number of cycles and $c_i(w)$ denote the number of $i$-cycles.
The Ewens measure is a one-parameter probability distribution on permutations where ...
- 1,989
3
votes
1
answer
206
views
Random planes separating points in $\mathbb{R}^3$
We are given a unit origin-centered sphere $S$ in $\mathbb{R}^3$, and three points $\mathbf{x},\mathbf{y},\mathbf{z}\in S$. Let $\mathbf{h}$ be a point selected uniformly at random from $S$ and let $H$...
- 1,677
3
votes
1
answer
109
views
Asymptotic estimate of the cardinality of $H_{2n}=\{\vec{a} \in [-N,N]^{2n}:\sum_{i=1}^{2n} a_i = 0\}$
Let's suppose $a_i \sim \mathcal{U}([-N,N])$ where $[-N,N] \subset \mathbb{Z}$. We may then define:
\begin{equation}
S_n = \sum_{i=1}^n a_i \tag{1}
\end{equation}
Now, in order to estimate $\lvert ...
- 3,871
3
votes
1
answer
108
views
Expected size of matchings in a cubic graph
Let $G$ be a random cubic graph on $n$ vertices. Let $M$ be the set of (not necessarily maximum) matchings of $G$. What is the expected size (i.e. number of edges) of an element of $M$?
In other ...
- 9,501
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$...
- 909
3
votes
2
answers
254
views
Probability of no $k$ 1's in arithmetic progression in binary sequence of length $n$
It is well known [it's on Wolfram Mathworld, for example] that the probability of no runs of $k$ consecutive $1$'s will occur in a $\{0,1\}$-valued sequence of length $n$ is exactly equal to $$\frac{F^...
- 10.4k
3
votes
1
answer
114
views
Proof for the emergence of a ranking with paired comparisons [closed]
Take a set {A, B, C, D, E}, and assume each of the set elements has a random real value attached to it between 0 and 1. For example, this gives us: {A, B, C, D, E} = {0.1, 0.9, 0.4, 0.6, 0.5}. Assume ...
- 43
3
votes
1
answer
142
views
Probabilistic method Alon and Spencer Azuma's inequality
Theorem 7.5.2 states:
Let $v_1, \dots, v_n$ be vectors with $\|v_i\| \leq 1.$ Let $\epsilon_1, \dots, \epsilon_n \in \{-1, 1\}$ be independent with uniform probability and let $X=\|\epsilon_1 v_1 + \...
3
votes
1
answer
218
views
Bounding the number of facets of a polytope to approximate a given convex shape in higher dimensions
We are given a convex shape $S$ lying inside the hypercube $[0,1]^d$ in the $d$-dimensional Euclidean space. Let the volume $V(S)$ of $S$ be $\tfrac12$ (I guess nothing changes for any other fixed ...
- 1,677
3
votes
1
answer
271
views
A quantity associated to a probability measure space
Let $(S,P)$ be a (finite) probability space. We associate to $(S,P)$ a quantity $n(S,P)$ as follows:
The probability of two randomly chosen events $A,B\subset S$ being independent is denoted by $n(S,P)...
- 356
3
votes
1
answer
241
views
Probability that k randomly drawn permutations can be arranged to compose to the identity
Consider the symmetric group $S_n$ under the uniform distribution. For integer $k > 1$, suppose we draw $k$ elements $s_1, \dots, s_k$ independently at random. What is the probability that there ...
- 6,223
3
votes
2
answers
488
views
Question about a new pseudo-random number generator
While investigating non-periodic RNG's (random number generators) for irrational numbers, I came up with a version that actually produces pseudo-random words consisting of $N$ bits, where $N$ is ...
- 3,098
3
votes
1
answer
395
views
Symmetric distribution optimization problem of distances between points in $[0,1]$
Let $\mathcal{D}$ be a probability distribution with support $[0,1]$. Let $x, y, z$ the outcomes of three i.i.d. random variables $X, Y, Z$ with distribution $\mathcal{D}$, sorted in increasing order, ...
- 1,677
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
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 ...
- 33
3
votes
1
answer
282
views
Longest runs and concentration of measure
Consider the longest runs $\ell_\sigma(x)$ of the pattern $\sigma$ for $\sigma\in \{0, 1, 01, 10, 001,\dots\}$ etc. in a binary sequence $x=x_1\dots x_n$.
For example, $\ell_{001}(0001110010011001)=2$...
- 24.8k
3
votes
1
answer
724
views
Expected value (probability) maximization with binomial distribution
I need to solve an optimization problem that involves an expected value like
$$F(n,x) = \sum_{k=0}^n \binom{n}{k} p^k(1 - p)^{n - k} f(k,x).$$
Here $f(k,x)$ is actually a probability coming from a ...
- 43
3
votes
2
answers
440
views
Graph game minimum vertex degree
Consider the following graph game, given a graph $G=(V,E)$ on $n$ vertices with minimum degree $ \gg \log(n)$. Players are BR and MA (BR moves first):
BR claims an unclaimed edge from $E$, adds it to ...
- 75
3
votes
1
answer
219
views
Uniformly permutation and the length of a size biased cycle
The cycle containing $1$ of a uniform permutation has length which is uniformly distributed. I was wondering if the converse is true:
Suppose $\sigma$ is a permutation on $\{1,\dots,n\}$ and let $u ...
- 491
3
votes
1
answer
242
views
Calculating the probability that all possible length $r$ subwords exists in a string, with or without overlaps allowed
Let $S$ be a length $L$ string, where each character in the string is chosen with uniform random probability over an alphabet with $q$ characters. For example, a binary string would imply $q = 2$, a ...
- 31
3
votes
1
answer
443
views
What is the expected value for this
If there are $8$ random points in the plane whose horizontal coordinate
and vertical coordinate are uniformly distributed on the open interval
$\left(0,1\right)$, what is the expected largest size of ...
- 31
3
votes
1
answer
376
views
The degrees in a random subgraph
Fix some positive integers $N$ and $d_k$, $k=1,2,\dots$ with $N=\sum_{k=1}^\infty d_k$.
Suppose you have a graph $G$ taken randomly uniformly among the set of all (unoriented) graphs with $N$ ...
3
votes
1
answer
162
views
Recurrence relation for the moments of the GOE
The Harer-Zagier formula provides a three term recurrence relation for the expected value of the single-trace operator $\mathrm {Tr}(X^k)$ where $X$ is a $N\times N$ matrix from the GUE. Is there an ...
