All Questions
Tagged with pr.probability co.combinatorics
802 questions
3
votes
1
answer
366
views
Random generation of subsets using conditional probabilities
Edit: Rewritten with motivation, and hopefully more clarity.
I'm building a site for a card game called dominion. In it, people build 'decks' of 10 distinct cards from a set of (currently) ...
- 203
2
votes
3
answers
335
views
Choosing $n$ times from $n$ objects
I am given $n$ objects and for $n$ times, I pick one of them with uniform probability and put it back after picking it.
For $k\in\{1,\ldots,n\}$ let $f_k$ denote the number of times that I have ...
- 48.9k
2
votes
1
answer
224
views
Approximate size of the image of functions $f:[n]\to[n]$ [closed]
The following is inspired from the most recent riddle of the week of the German news magazine Der Spiegel.
For any positive integer $n\in\mathbb{N}$, let $[n]$ denote the set $\{1,\ldots,n\}$. Let $...
- 48.9k
2
votes
4
answers
512
views
Statistical computation in matrix. Rows before columns? riddle..
First I'll phrase the question as a riddle, and than as a general math problem.
We have 12 lettered vases $(A,B,...,L)$, in each vase there are 30 numbered balls (1-30). In each ball there is some ...
- 23
2
votes
2
answers
351
views
Discrete probability algorithms
I have a probability problem, which I need to simulate in a reasonable amount of time. In its simplified form, I have 30 unfair coins each with a different known probability of being heads. I then ...
- 41
2
votes
2
answers
1k
views
expected number of cycles in a "random" bipartite directed graph
Consider a "random" bipartite directed graph where (1) on each side, the set of vertices has cardinality n and (2) for each vertex i, we add one (and only one) directed edge i->j at random (drawn ...
- 65
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 ...
- 2,618
2
votes
2
answers
304
views
Uniformly random planar map
Is there a way to sample a planar map uniformly at random? I am aware of the Cori-Vauquelin-Schaeffer bijection that can be used to sample and study uniformly random quadrangulations. There are other ...
- 1,989
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 ...
- 41
2
votes
2
answers
286
views
Finding an easy example applying the general Lovász local lemma
Is there any easy application for the general local lemma as follows? If someone knows, please tell me the references or just post an example here. Thanks.
General Lovász local lemma: Consider a set $...
- 1,190
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 ...
- 1,677
2
votes
2
answers
698
views
Expected Number of edges for a graph to have a Triangle?
i want to compute the (Approximated) expected number of edges for a graph to have some triangles (loop with length 3)
i just solved a similar simpler problem:
Generate a random graph on $n$ vertices ...
- 550
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,648
2
votes
1
answer
106
views
How to efficiently sample uniformly from the set of $p$-equipartitions of an $n$-set?
I have a question related to this one. For $n,p \in \mathbb{N}_+$ such that $p\mid n$, let $\mathcal{P}^{\rm eq}$ be the set of all equipartitions of $n$ in $p$ sets; i.e., in sets of equal size $\...
- 1,372
2
votes
2
answers
220
views
Removing subtrees
Let $T$ be a complete infinite rooted binary tree. Is it possible to remove (infinitely many) subtrees of $T$ and get a subgraph $G$ such that:
$G$ has no complete subtrees (the graph below any ...
- 11.3k
2
votes
1
answer
305
views
Distribution of area of randomly placed circles
I've searched the web now for ages to try and find a paper on the asymptotic distribution of the area of the union of randomly placed discs on the plane. Ideally, I would be looking for the discs to ...
- 903
2
votes
2
answers
710
views
Runs in coin flips
Let $P(j,k,n)$ be the probability of getting $j$ uniform runs of length $k$ from $n$ fair coin flips. What's the best way to compute $P$? I have no idea how difficult it might be; if it's a very ...
- 1,769
2
votes
1
answer
835
views
An optimization problem, non complete bipartite graph and hungarian algorithm
I have two tables at my disposal, one work dataset and one reference dataset. Each dataset has got two columns, lets say these are fields A and B. I would like the rows in reference dataset with the ...
- 123
2
votes
1
answer
2k
views
The expected minimum Hamming distance within a set of randomly selected binary strings
If I randomly sample with replacement $P$ times from a set of all possible binary strings of length $L$, what is a good lowerbound on the expected minimum Hamming distance between any two of my $P$ ...
- 67
2
votes
1
answer
267
views
Expected number of identical vertex pairs with the same Euclidean distance on a randomly colored rectangular lattice
Imagine I have an $N$ by $M$ rectangular lattice where I randomly assign one of $k$ colors to every vertex in the lattice. I then write down a list of the ${N*M}\choose{2}$ possible unordered pairs ...
- 23
2
votes
1
answer
262
views
Randomly fixing elements and transcendence degree
Given $f_1,\ldots,f_n \in \mathbb{F}_q[x_1,\ldots,x_m]$ such that $\deg(f_i) \leq d < q$. Suppose we have for some $1 \leq j \leq m$
$$ \operatorname{trdeg}_{\mathbb{F}(x_1,\ldots,x_j)}\{f_1,\ldots,...
- 341
2
votes
1
answer
199
views
Average cluster size of a n-size vector
Given a vector of $n$ cells and $k$ elements in it, we can define a cluster of elements as a contiguous sequence of elements inside the vector.
My goal is to calculate the average cluster size for all ...
- 47
2
votes
1
answer
118
views
Probability that at least one of the first $k$ right-to-left maxima of $\{1, ..., n+m\}$ contains a number from $\{n+1, ..., n+m\}$
Given a permutation $\sigma$ on $[n]=\{1, ..., n\}$, we say an element $i$ is a right-to-left maximum if $\sigma(i)=\max(\sigma(1), ..., \sigma(i))$.
Suppose we sample a random permutation from $\{1, ....
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?
- 2,630
2
votes
1
answer
142
views
The expectation of partition times needed separate two elements in a set
I met a problem which can be formulated as set partition.
Given a set $S=\{s_1,s_2,...,s_n\}$ having $n$ elements, I want to separate two elements, say $s_1,s_2$, in $S$ by repeatedly using set ...
- 23
2
votes
2
answers
243
views
Birthday problem extension to unequal probabilities and multiple collisions
Let $p_1, ... ,p_k$ denote the probabilities of drawing bin $1, .. ,k$, where $\sum_{i = 1}^{k} p_i= 1$. My question is if we draw $n$ times, how can I show that the probability that all bins are ...
- 31
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$ ...
user123818
2
votes
2
answers
1k
views
Generalization on Coupon Collector's Problem
Player extracts card from the deck (which has infinite number of size) to obtain one of $k$ colors of cards. The possibility that the player pick a card with $i$th color is given by $p_i>0$. Of ...
- 121
2
votes
2
answers
2k
views
Hitting times for an N-dimensional random walk on a lattice with (strictly positive) random integer steps
Please consider a random walk on a finite N-dimensional lattice with vectors $(x_1, ..., x_N)$. We define the origin to be $(0, ..., 0)$ and the target to be at the point in the lattice furthest away ...
- 599
2
votes
1
answer
208
views
Proving an exponential sum inequality for symmetric Hamming distance sequences in binary vectors
Background: Let $X = \{0,1\}^k$ represent the set of all binary vectors of length $k$. For two binary vectors $x, y \in X$, the Hamming distance $d_H(x, y)$ is defined as the number of positions where ...
- 359
2
votes
1
answer
259
views
The probability that iid draws from a mean zero random variable sum to zero
Suppose we have a probability distribution $p(\cdot)$ supported on the integers between $-m$ and $m$ for some positive integer $m$, with $\sum_k kp(k) = 0$. Suppose furthermore that all $p(k)$ are ...
- 19.7k
2
votes
1
answer
201
views
Dispersion of a "random" subset of $[-1,1]^2$
Let $C$ be the square $[-1,1]^2$. Let $a_1,\dots,a_m$ be points chosen independently and uniformly at random from $C$. Let $d_m$ (dispersion) be the random variable $\max_{x \in C}{\min_{j \in [m]}{\|...
- 261
2
votes
1
answer
383
views
Lower bound and limit of a sum with binomial coefficients
Let
$$A_k = \sum_{i=1}^k i {3k-2i-1 \choose i-1} {2i-2 \choose k-i}$$
$$B_k = \sum_{i=1}^k i {3k-2i-2 \choose i-1} {2i-1 \choose k-i}$$
$$C_k = \sum_{i=1}^k (3k-2i-2) {3k-2i-3 \choose i-1} {2i\...
- 155
2
votes
1
answer
151
views
Given an input point in $\mathbb{R}^n$, select (one of) the closest point(s) from a fixed large set of points given in advance
We are given a set $S$ of $m\gg 1$ points in $\mathbb{R}^n$.
In the problem I am trying to solve, in a sequential fashion, we obtain a new point $p_r\not\in S$ at each round $r\ge 1$ and the goal is ...
- 1,677
2
votes
2
answers
280
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
2
votes
1
answer
179
views
How to uniformly sample a square (0,1)-matrix whose trace is 0 and whose row sums and column sums are the same?
Happy New Year!
Suppose I would like to sample a $n \times n$ (0,1)-matrix whose trace is 0, and whose row sums and column sums are all $m$ with $1 \le m \le n-1.$ How can I sample this matrix ...
- 131
2
votes
3
answers
192
views
Asymptotic behaviour of binomial term
Is it true that that ${{n}\choose{k}} p^k (1-p)^{n-k}$ is dominated by $\frac{1}{n}$, at least for $k$ sufficiently big?
EDIT: I saw that the question was absolutely not stated as I intended. The ...
- 23
2
votes
1
answer
300
views
Number of subsets that sum to $0$
Suppose you choose $n$ distinct random numbers from a contiguous subset of cardinality $f({\beta, n})$ with at least $f({\alpha_+, n})$ positive and at least $f({\alpha_-, n})$ negative values from a ...
user76479
2
votes
1
answer
186
views
Probability of covering a set
Suppose we have a set of $N$ numbers. At any given trial we can randomly choose $N^{1-a}$ of the numbers where $a\in(0,1)$. We replace the numbers back.
How many trials does it take in average case ...
- 13.9k
2
votes
2
answers
291
views
How many boxes so that there is $k$ of same of color from $n$ different colors?
Say you have $m$ boxes each of which is colored with one of $n$ colors. What should $m$ be so that the probability that there is atleast $k$ boxes with one same color is strictly greater than $\frac{1}...
- 13.9k
2
votes
2
answers
391
views
linear ordering of color balls
Suppose that $n+m$ balls of which $n$ are red and $m$ are blue, are arranged in a linear order, we know there are $(n+m)!$ possible orderings. If all red balls are alike and all blue ball are alike, ...
- 123
2
votes
1
answer
158
views
"Shape"/"norm" of a uniformly random set partition
Let $\mathcal{A}=\{A_1, A_2, \ldots, A_m\}$ be a uniformly random set partition of $[n]$.
What can we say about $||\mathcal{A}||_2 = \sqrt{\sum_{i=1}^m |A_i|^2}$? It is clearly upper bounded by $n$, ...
- 526
2
votes
1
answer
426
views
Random subgraph properties
Consider a graph $G$ of $N$ vertices and $M$ edges, and assume $G$ has typical complex network properties: it is not necessarily connected, but it has a high clustering coefficient and a giant ...
- 129
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
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 ...
- 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
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, $\...
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 ...
- 435
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 ...
- 909
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 ...
- 121