All Questions
Tagged with pr.probability co.combinatorics
802 questions
2
votes
1
answer
118
views
Calculate the discrete probability of x number of good outcomes occurring before y number of bad outcomes
I have a grid of 16 tiles face down. Half are good outcomes and half are bad outcomes. How would I calculate the probability of picking x number of Good outcomes before y number of bad outcomes are ...
- 842
21
votes
1
answer
32k
views
How to compute KL-divergence when PMF contains 0s?
From the Wikipedia page on Kullback-Leibler divergence, the way to compute this metric is to utilize the following formula:
The way I understand this is to compute the PMFs of two given sample sets ...
1
vote
0
answers
85
views
Winning criterion for a combinatorial game
Given $n$,
let $\mathcal{R}$ be a set of pairs $(\rho,A)$
where $A\subseteq n, \rho\in 2^A$.
Consider the following game between A and B.
At each round $t$, A enumerates an $m\in n$ (that has not been ...
- 1
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
0
votes
1
answer
158
views
Finding k items in a binary tree
Let us be given a binary tree of height $n$ (and $2^n$ leaves) among which we search $k$ items, where $k < < 2^n$. Suppose we have a test that shows if in the children and childrens-children ...
CommunityBot
- 1
23
votes
4
answers
978
views
What nodes of a graph should be vaccinated first?
Consider a graph, choose some "p: 0<p<1" (probability to infect the neighbor node).
Choose some random number "K" of nodes which are "infected" initially.
So we ...
- 1,054
6
votes
1
answer
235
views
A combinatorics problem and the probability interpretation
For a gaussian vector variable $w\sim N(0,I_{n\times n})$, the moments of square norm are $\mathbb{E} \|w\|^{2 r} = \prod_{t=0}^{r-1} (n + 2 t)$.
Based on Isserlis' theorem, $\mathbb{E} \|w\|^{2 r}$ ...
- 50.8k
1
vote
2
answers
163
views
Coupling a binomial - parity conditioning
If I have a binomial $X \sim B(n,p)$, and another binomial $X' \sim B(n,p)$ conditioned on $X'$ being of even parity. Is it true that there always exists a coupling for $(X,X')$ with $|X-X'| \le 1$? (...
- 128k
5
votes
0
answers
130
views
Random process on a sequence of rolls of an $n$-sided die
Let $\ X:=X_{k\,n}\ $ be a random variable of a $n$-sided die where $\Pr(X=i)=\frac{1}{n}$ for each $i\in\{1,2,\ldots,n\},\ $ where $\ k\in\{1, 2, \ldots,n\}\ $ and $\ n\ $ are fixed. Let $t$ be a ...
- 83
2
votes
0
answers
164
views
Finding an optimal strategy for a combinatorial sequential game
We are given a set $\{p_1, p_2, \ldots, p_n\}$ of players and a set of $\{\ell_1, \ell_2, \ldots, \ell_n\}$ of locations, where $n\in\mathbb{N}$. Each location can be either free or occupied, and each ...
- 83
1
vote
3
answers
339
views
Coupon collector targeting a collection among many
I am interested in the following problem:
We are given a universe $U$ of $n$ coupons, partitioned into $k$ collections, $C_1,\dots C_k$.
At each time step $t$, a coupon $X_t$ is selected uniformly at ...
- 4,361
2
votes
1
answer
404
views
Euclidean distance bound with geometric constraints
Let $S_n$ be a set of $n$ points belonging to $\mathcal{B}_d:=\{\mathbf{x}\in\mathbb{R}^d:\|\mathbf{x}\|_2\le 1\}$, where $d\ll \log(n)$.
Let $s_n$ and $\ell_n$ be respectively defined as follows:
$$...
- 1,677
23
votes
3
answers
2k
views
Zeroes of the random Fibonacci sequence
Let $X_n$ be the "random Fibonacci sequence," defined as follows:
$X_0 = 0, X_1 = 1$;
$X_n = \pm X_{n-1} \pm X_{n-2}$, where the signs are chosen by independent 50/50 coinflips.
It is known ...
- 52.3k
6
votes
1
answer
424
views
Probability of intersecting a rectangle with random straight lines
We are given a rectangle $R$ with sides lengths $r_1$ and $r_2$, contained in a square $S$, with sides lengths $s_1=s_2\ge r_1$ and $s_2=s_1\ge r_2$. $R$ and $S$ are axis-aligned in a cartesian plane $...
- 1,677
2
votes
1
answer
218
views
Probability 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$ three i.i.d. random variables with distribution $\mathcal{D}$, and $T$ a random variable uniformly distributed in $[...
- 1,677
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
2
votes
2
answers
279
views
Combinatorial optimization problem with interdependent constraints on points in $[0,1]$
We are given a set $S$ of $n$ real numbers in $[0,1]$, with $0,1\in S$, and a value $\alpha\in(0,1/2)$. For each ordered triplet $(i,j,k)$ of values contained in $S$ (with $i\le j \le k$), we define ...
- 1,677
18
votes
4
answers
3k
views
Markov chain on groups
Let $G$ be a permutation group on the finite set $\Omega$. Consider the Markov chain where you start with an element $\alpha \in \Omega$ chosen from some arbitrary starting probability distribution. ...
- 63.9k
12
votes
1
answer
525
views
An inequality about unit vector orthogonal to $(1,1,...,1)$
Does there exist a constant $\alpha>0$ such that the following holds?
$$\liminf_{n\to\infty}\inf_{x\in\mathbb{R}^n, \sum_{i=1}^nx_i^2=1, \sum_{i=1}^nx_i=0}\frac{\sum_{i<j, |i-j|\leq\frac{n}{4}}(...
- 128k
5
votes
0
answers
287
views
Infinite tridiagonal matrices and a special class of totally positive sequences
Let $\Bbb{y} = \big(y_1, y_2, y_3, \dots \big)$ be an infinite sequence of positive real numbers such that following $\Bbb{N} \times \Bbb{N}$ tridiagonal matrix
\begin{equation}
T(\Bbb{y}) := \,
\...
- 2,137
1
vote
1
answer
338
views
Polynomial form/Fourier transform of rational function over finite affine space
I am certainly going to make a mess of any serious algebraic terminology, so bear with me as I present my problem arising from a probability problem.
Consider the space of sequences of $n$ zero-one ...
- 3,946
2
votes
2
answers
379
views
Probabilistic combinatorial optimization problem on the distances between pairs of points in $[0,1]$
Let $S$ be a set of $n \gg 1$ points lying on the interval $[0,1]$. Given a point $p\in[0,1]$, let $S_p\subseteq S\times S$ be the set formed by all pairs of points $(x,y)$ with $x,y\in S$, such that ...
- 111
0
votes
1
answer
340
views
Expectation of the ratio of two discrete random variables with combinatorial constraints
We are given a set $S=\{1, 2, \ldots, n\}$ where $n\gg 1$, and for all indices $1\le i \le n$, $i$ is associated with a real value $\alpha_i\!\cdot\! v_i$, where $\alpha_i\in[0,1]$ and $v_i\in(0,1]$.
...
- 1,677
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
10
votes
2
answers
270
views
Maximal in-degree in directed voting graph
Real-life motivation. Our team has $n$ members. For the next in-team presentation session, everyone had 1 talk prepared that he or she would be able to present. Now everyone could cast $1$ vote about ...
- 61.9k
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
0
votes
1
answer
201
views
What is the most likely sequence? [closed]
I have a jar containing n numbered marbles, where 1...x marbles are red and marbles x+1...n ...
- 156k
7
votes
0
answers
297
views
Is there a practically useful or concrete representation theory/Fourier analysis on finite groupoids?
Fourier analysis on finite groups is well known to be useful for probability theory and combinatorics — consider for example the Fourier analysis on $(\mathbb Z/2\mathbb Z)^n$ which can be used to get ...
- 526
9
votes
0
answers
467
views
Measuring the randomness of texts
The question concerns statistic properties of random words in a finite alphabet $A$.
By $A^{<\omega}$ we denote the set of all words in the alphabet $A$, i.e. finite sequences of elements of $A$.
...
- 41.9k
2
votes
0
answers
65
views
Are stable matchings (noise-)stable?
Suppose a group of computer scientists have entrusted their dating lives to a computer. Specifically, there are $n$ men and $n$ women, all of whom are cis-het. Being educated people, they of course ...
- 526
2
votes
0
answers
90
views
Motivation for proof of local lemma/construction version
I am interested in finding intuition to the bounds and proof of the asymmetric local lemma.
I think the $k$-SAT is fairly intuitive, but I would like to understand the general version.
One good ...
- 12.9k
1
vote
0
answers
177
views
Probability of satisfying the congruent mod equation
I'm wondering about the probability of picking three different numbers $x,y,z$ out of the set $[50]=\left\{ 1,2,3,...,50\right\}$ satisfying the equation: $$xyz\equiv \gcd(x,y,z)\mod 7$$ I started out ...
- 39.7k
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. ...
CommunityBot
- 1
1
vote
1
answer
264
views
Probability a near universal hash function $ax \bmod p \bmod m$ produces an output from inputs equal modulo $m$
For one of the near universal hash functions $f(x) = ax \bmod p \bmod m$ where $p$ is prime and $m < p, m>1$ and $x$ ranges over $1 \dots p-1$ , what is the probability that given $x_r \in \{ x |...
- 7,217
0
votes
1
answer
305
views
Number of duplicate pairs in multiple samplings
My universe has M different items. I run m=10 independent samplings over M. In each sampling, n elements are picked without replacement (n<<M). What is the expected number of pair duplicates we ...
- 128k
6
votes
2
answers
2k
views
How to understand the combinatorial Laplacian $\Delta$ which is defined on the graph?
I have a question about the combinatorial Laplacian $\Delta$ which is defined by
$$\Delta(u,v)=c(u)1_{u=v}-c(u,v)$$
where $u, v$ are some vertices in the graph $G=(V, E)$, and $c(u,v)$ is a ...
- 4,432
2
votes
0
answers
165
views
Ask for some reference about isoperimetric constant on Voronoi diagrams?
Given a Poisson point process $\mathcal{P}$ in $\mathbb{R}^2$, the $\textbf{Voronoi cells}$ of a point $p\in \mathcal{P}$ is defined by
$$V(x):=\{y\in \mathbb{R}^2: \|x-y\|=\min_{x'\in \mathcal{P}}\|x'...
- 288
3
votes
1
answer
145
views
The size of monochromatic submatrix
We say a matrix $(a_{ij})$ is 0-1 matrix if $a_{ij}\in \{0,1\}$ for all $i,j$. We say a matrix $(a_{ij})$ is monochromatic if for some $a$, $a_{ij} = a$ for all $i,j$.
Question: Let $c\geq 1/2$ be a ...
- 109k
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
2
votes
3
answers
290
views
Geometric probabilistic problem on triangles on a plane
We are given a triangle $T$ on a plane $P$, with sidelengths $a$, $b$ and $c$, where $c \ge b \ge a > 0$. A straight line $L$ on $P$ is selected uniformly at random from the set of all the ...
- 61.9k
11
votes
1
answer
370
views
Graph with path of length $\geq n$ along grid diagonals - a known result in graph theory?
Is the following lemma a well known result in graph theory?
I am studying a basic existence result that appears to be simple yet powerful. I have not seen it stated as an important result in graph ...
- 290
0
votes
1
answer
57
views
Expected size of binomial coefficient with Poisson arrivals?
I have a Poisson process where new elements arrive to a set with Poisson intensity $\lambda$. Initially, there are $N_0$ elements in the set. The probability that there are $N_0 + M$ elements in the ...
- 128k
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 ...
- 63.9k
1
vote
1
answer
158
views
Bound for multinomial expansion involving Poisson random variables
Let $x_i, i=1, \ldots n$ be Poisson random variables with parameters $\lambda_i$ correspondingly with condition that $\sum_{i=1}^nx_i=T$. Due to linearity of the expectation one can write:
$$
E\left(\...
- 2,101
8
votes
3
answers
411
views
Identifying a subset with as few tests as possible
Informal description: You are given a set of $n$ blood samples, each having probability $p$ of being infected with a disease. Your goal is to determine the set $P$ of infected samples with as few ...
- 10.4k
0
votes
1
answer
78
views
Estimate an expression about probability about Bernoulli random variables
Given $v_{ij} \in \{0,1\}$, $i \in \{1,2\}$, $j \in \{1,2,\ldots,n\}$. Let $X_1, X_2, \ldots, X_n$ be random variables, $P[X_i=1]=P[X_i=0]=1/2$, $i \in \{1,\ldots, n\}$. By checking many examples, I ...
- 128k
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
1
vote
0
answers
100
views
Balls and bins, with cardinality constraints
Suppose I have $n$ sets of $k$ balls each, with each one of the $nk$ balls distributed uniformly at random among $m$ bins. Further suppose that I have a probability vector $p=(p_1,\dots,p_m)$. I am ...
- 4,049
10
votes
1
answer
846
views
A Johnson-Lindenstrauss lemma for finite fields?
Given $m$ points in $\mathbb{R}^N$, the Johnson-Lindenstrauss lemma guarantees the existence of a linear operator $\mathbb{R}^N\rightarrow\mathbb{R}^n$ that nearly preserves pairwise distances between ...
- 123
7
votes
1
answer
463
views
Boundedness of total current in electrical network
Consider the following symmetric matrix (adjacency matrix):
$$A=(a_{ij})_{1\leq i,j\leq n}$$
such that $a_{ij}=a_{ji}, a_{ii}=0$ and $a_{ij}=0$ for $|i-j|\geq k$ where $k\geq3$. We also have $1\leq a_{...
- 1,495