All Questions
Tagged with pr.probability co.combinatorics
802 questions
3
votes
1
answer
693
views
Sequence of p draws without replacement with biased probabilities
Hi
I have a problem which i find hard to modelize.
Suppose i have an urn with $N$ marbles. Among these marbles, one is white and all the other ones are black. I draw $P$ marbles without replacement. ...
- 133
24
votes
3
answers
4k
views
What upper bounds are known for the diameter of the minimum spanning tree of $n$ uniformly random points in $[0,1]^2$?
Let $P$ be a pointset consisting of $n$ uniformly random elements of $[0,1]^2$. It is known that the diameter (greatest number of edges in any shortest path between two points) of the Delaunay ...
- 4,922
2
votes
0
answers
351
views
Distribution of transformed multinomial variable?
Suppose we have a uniform multinomial distribution over $2^d$ outcomes. Multinomial coefficients give distribution of vector valued variable $v$ where $v$ is the vector of observed counts.
Is there a ...
- 2,252
2
votes
0
answers
530
views
About generalization of stirling numbers of the second kind
Hello,
The Stirling numbers of the second kind count how many ways can a set of $k$ elements be partitioned into $n$ non-empty classes, with $k=n,n+1,\dots$.
My question is: Is there a ...
18
votes
1
answer
2k
views
How big is the sum of smallest multinomial coefficients?
Given positive integers $n$ and $d$, let $S$ indicate the list of all $d$-tuples of non-negative integers $(c_1,\ldots,c_d)$ such that $c_1+\cdots+c_d=n$. Let $v_i$ be the value of the multinomial ...
- 2,252
18
votes
4
answers
1k
views
Pennies on a carpet problem
I recently read the following "open problem" titled "Pennies on a carpet" in "An Introduction To Probability and Random Processes" by Baclawski and Rota (page viii of book, page 10 of following pdf),...
- 4,952
20
votes
4
answers
870
views
Enumeration and random selection
In Peter J. Cameron's book "Permutation Groups" I found the following quote
It is a slogan of modern enumeration theory that the ability to count a set is closely related to the ability to pick a ...
- 85.6k
12
votes
3
answers
1k
views
Is there a simple inductive procedure for generating labeled trees uniformly at random, without direct recourse to Prüfer sequences?
Suppose you have a labeled tree $T$ on vertices $V=\lbrace 1,\ldots,n\rbrace$ that is drawn uniformly at random from the set of all $n^{n-2}$ such trees. I am seeking an $f$ satisfying the following ...
- 1,068
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
4
votes
2
answers
853
views
Can you explain the description of the Lovasz Local Lemma by Moser+Tardos?
The Lovász Local Lemma (or LLL) concerns itself with the probability of avoiding a collection of "bad" events A, given that the set of events is "nearly independent" (each bad event A &...
- 1,444
15
votes
2
answers
3k
views
Bounding sum of multinomial coefficients by highest entropy one
When does the following hold?
$$\sum_{(i_1,\ldots,i_k)\in E}
\frac{n!}{i_1! \ldots i_k!}
\le \exp(n H^*)$$
where $H^*=\max_{(i_1,\ldots,i_k)\in E} -(\frac{i_1}{n}\log \frac{i_1}{n}+\ldots +\frac{...
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
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
20
votes
2
answers
819
views
A probability question related to extremal combinatorics
$k$ people play the following game: person $i$ independently picks a subset $S_i$ of $\{ 1,2,\ldots,n \}$ according to some distribution $p$ on the $2^n$ subsets; each person uses the same ...
- 976
27
votes
2
answers
812
views
What is the right notion of self-dual (two-dimensional) percolation in R^4?
For a lattice in $\mathbb{R}^2$, if we include each edge independently with probability $p$ (i.e. bond percolation), it is well known that there is a critical probability $0 < p_c < 1$ depending ...
- 7,857
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 ...
11
votes
0
answers
426
views
Maximizing the volume in a family of subsets of a cube
Starting from a question in probability, I arrived to the following optimization problem.
Let $I:=[0, 1],$ and let $A$ be a Lebesgue measurable subset of the $n$-dimensional cube, $A\subset I^n.$ ...
- 60.5k
4
votes
1
answer
232
views
Negative Association of Component Size in Random Hypergraph
I have a $d$-uniform hypergraph on $n$ vertices with $k$ hyperedges, where $d << k$ and $n = 4k d^2$ or so.
The hyperedges are placed independently uniformly at random. I would like to have a ...
- 241
4
votes
3
answers
286
views
Medium-Sized Calculations and Organization
This is not a math question as much as a process question. For the first time in my (very short) career, I find myself doing one of those messy calculations, where each 'line' of the calculation can ...
- 63
5
votes
1
answer
1k
views
Concentration of Measure for Power Law
I have a power law distribution $X$ with exponent $c$: $$p(X=t) = \left\\{\begin{array}{cl}(c-1)/t^{c} & t \geq 1 \\\\ 0 & t < 1\end{array}\right.$$
From $X$ I take $n$ independent samples ...
- 241
6
votes
2
answers
1k
views
diameter of a graph with random edge weights
Given a weighted directed graph $G=(V,E, w)$, suppose we generate a new graph $G'=(V,E,w')$ with the same vertices and edges, but now letting the weight of edge $(i,j)$ be
an exponential random ...
- 976
9
votes
1
answer
1k
views
Vertex connectivity of random graphs?
Consider simple, undirected Erdős–Rényi graphs $G(n,p)$, where $n$ is the number of vertices and $p$ is the probability for each pair of vertices to form an edge. Many properties of these graphs are ...
- 383
14
votes
3
answers
8k
views
Analog of Chebyshev's inequality for higher moments
I have a positive random variable $X$ with $E[X] = 1$ and a small number $k$ more moments bounded by constants:
$$E[(X-1)^i] = O(1) \forall i \in \{2, ..., k\}.$$
I'd like to bound the average of $n$...
- 241
9
votes
1
answer
1k
views
Points on binary hemispheres of the n-sphere
Let $\mathbb{S}^{n-1}=${$ x\in \mathbb{R}^n| \sum_{k=1}^n x_k^2 =1 $} be the $n-1$ sphere and $n_i\in\mathbb{R}^n$ with components $n_{ij}\in${$-1,1$}$\ \forall\ j=1,2,\dots,n$. There are obviously $2^...
- 91
2
votes
1
answer
467
views
Distribution on permutations derived from probability of pairwise orderings
A followup question to Probability estimates for pairwise majority votes - I think it doesn't actually give an answer in any terribly precise sense, but it would give something I'd be happy to use in ...
- 1,331
25
votes
3
answers
2k
views
Some models for random graphs that I am curious about
G(n,p)
We are familiar with the standard notion of random graphs where you fixed the number n of vertices and choose every edge to belong to the graph with probability 1/2 (or p) independently. This ...
- 24.7k
1
vote
3
answers
312
views
Chance of something being fixed [closed]
I'm fixing a software defect that occurs 1 in n test runs. If I want to know that the probability of it being fixed is >= p for some 0 <= p < 1, how many times, m, do I need to run the test ...
- 43
4
votes
1
answer
938
views
Random projection and finite fields
Suppose we have, say, $n$ $2n$-dimensional linearly independent vectors over $\mathbb{F}_2$. We do a projection on a random $d$-dimensional subspace. We are interested in probability that images of ...
- 1,791
1
vote
0
answers
207
views
understanding some derivation in random XORSAT problem
This question is concerned about the paper "The 3-XORSAT threshold" by O. Dubois, J.Mandler. Here is the link: http://dx.doi.org/10.1016/S1631-073X(02)02563-3
Basically one would like to know when is ...
- 4,466
4
votes
2
answers
1k
views
expected values over binomial distributions
In some works of economics/risk analysis etc., I have seen situations where people take the expected value of a function (such as a utility function/cost function) over a binomial distribution:
$$F(n)...
- 7,320
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
18
votes
3
answers
8k
views
Number of invertible {0,1} real matrices?
This question is inspired from here, where it was asked what possible determinants an $n \times n$ matrix with entries in {0,1} can have over $\mathbb{R}$.
My question is: how many such matrices ...
- 32.1k
98
votes
17
answers
123k
views
Google question: In a country in which people only want boys [closed]
Hi all!
Google published recently questions that are asked to candidates on interviews. One of them caused very very hot debates in our company and we're unsure where the truth is. The question is:
...
- 1,107
20
votes
3
answers
1k
views
The probability for a sequence to have small partial sums
The question
Let $a_1,a_2,\dots,a_n$ be a sequence whose entries are +1 or -1. Let t be a parameter. My question is to give an estimate for the number of such sequences so that
$|a_1+a_2+\dots ...
- 24.7k
1
vote
1
answer
783
views
Probability of n k-sided dice showing exactly m different faces
I found the following closed form solution for the abovementioned problem:
$${1\over k^n}\cdot{k!\over (k-m)!}\cdot{\{{n\over m}\}}$$ with ${\{{n\over m}\}}$ being the Stirling Number of the second ...
- 5,935
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. ...
- 85.6k
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
28
votes
6
answers
2k
views
Random Alternating Permutations
An alternating permutation of {1, ..., n} is one were π(1) > π(2) < π(3) > π(4) < ... For example: (24153) is an alternating permutation of length 5.
If $E_n$ is the number of alternating ...
- 22.8k
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
4
votes
3
answers
579
views
Average distance between numbers of the form $2^{a}3^{b}$
I want to order all numbers of the form $2^a3^b$. I need to find the average distance between a random consecutive pair.
For example, in case of a random consecutive pair $2^{n'}$ and $2^{n'+1}$, the ...
- 431
8
votes
1
answer
519
views
devise a joint distribution of $\alpha$ and $\beta$
If we assume probability density distribution functions of random variables $\alpha$, $\beta$ and $\alpha/ \beta$, we would like to devise a joint distribution of $\alpha$ and $\beta$. Although ...
- 81
4
votes
6
answers
751
views
Reconstructing an ordering of a multiset from its consecutive submultisets
We have a multiset $S$ of size $t$ with $r$ distinct elements, where $t$ is much larger than $r$. We want to reconstruct an ordering $s_1, s_2, ... s_t$ of the elements of $S$ given the values of $t$ ...
- 599
75
votes
11
answers
28k
views
Does War have infinite expected length?
My question concerns the (completely deterministic) card game known as War, played by seven-year-olds everywhere, such as my son Horatio, and sometimes also by others, such as their fathers.
The ...
- 236k
-1
votes
1
answer
502
views
Name for probabilistic version of Pascal's identity and differentiation formula for binomial distribution
I'm trying to find a standard name or standard reference for two simple-to-prove relations involving binomial distributions.
Define:
$b(n,r,p) := \binom{n}{r}p^r(1 - p)^{n-r}$
i.e., it is the ...
- 7,320
16
votes
0
answers
1k
views
Optimal monotone families for the discrete isoperimetric inequality
Background: the discrete isoperimetric inequality
Start with a set $X=\{1,2,...,n\}$ of $n$ elements and the family $2^X$ of all subsets of $X$.
For a real number $p$ between zero and one, we consider ...
- 24.7k
39
votes
9
answers
3k
views
The shortest path in first passage percolation
Update (January 17): The problem has now been solved by Daniel Ahlberg and Christopher Hoffman. (Thanks to Matt Kahle for informing us.)
Consider a square planar grid. (The vertices are pair of ...
- 24.7k
7
votes
2
answers
627
views
Probability vertices are adjacent in a polygon
With regard to my original question:
A subset of k vertices is chosen from the vertices of a regular N-gon. What is the probability that two vertices are adjacent?
I suppose that the responses ...
- 73
4
votes
0
answers
497
views
A Local CLT with large variance
For n an even integer, $0 \leq i \leq$ ${n} \choose{j}$, $1 \leq j \leq n$ let $X_{i,j}$ be a
random variable taking values $\frac{n}{2}-j,0,j - \frac{n}{2}$ with equal probability. Let $S_{n}$ be ...
- 263
2
votes
1
answer
380
views
Parity, Balls and Boxes
Start with a distribution $\mu$ on [n], and drop m balls into these n+1 slots independently and according to the distribution &mu. That is, we have iid random variables x 1 through x m ...
- 263
19
votes
9
answers
3k
views
How can I generate random permutations of [n] with k cycles, where k is much larger than log n?
I've been thinking a lot lately about random permutations. It's well-known that the mean and variance of the number of cycles of a permutation chosen uniformly at random from Sn are both ...
- 14k