All Questions
Tagged with pr.probability co.combinatorics
802 questions
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
0
votes
1
answer
148
views
A tiling of $\mathbb{Z}^2$ from M. Barlow's paper
In M. Barlow's paper: arxiv.org/pdf/math/0302004.pdf, P17- (2.7) formula.
Let $k\geq 10$, and consider a tiling of $\mathbb{Z}^2$ by disjoint squares
$$T(x):=\{y\in \mathbb{Z}^2: x_i\leq y_i< ...
- 288
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 ...
- 1
0
votes
1
answer
165
views
Bound for Large deviations of sums of independent (not identical) variables
I am working with a sum of variables $X_i$; they are all independent, but not identically distributed. For any $i$, I can show the bound $$\Lambda^*_{X_i}(t) := \sup_t \langle t, x \rangle - \Lambda_X(...
- 435
0
votes
1
answer
187
views
Proof of consistent of height function
I have a question about the consistent of height function defined on a domino tiling. I always see papers claims that height function is defined consistently. But I am confused with the consistent. ...
user102900
0
votes
1
answer
144
views
A problem related to the comparison of two integer-valued random variables
Consider an urn containing red, blue and green balls (the situation is the same illustrated in this post).
Let $X$ be the non-negative, integer-valued random variable defined as the number of trials (...
- 145
0
votes
1
answer
3k
views
How to compute the clustering coefficient of a random graph?
How is the clustering coefficient defined for random graphs? For example, a first definition could be calling clustering coefficient of a random graph the expected value of the clustering coefficient ...
- 23
0
votes
1
answer
414
views
Exact formula for computing n-step transition probability of random walks with self-transitions
Consider a semi-infinite random walks $X_n$, $n=0,1,2,\ldots$, whose state space is a set of consecutive integers and whose one-step transition probabilities are $P_{ij}=\mathrm{Pr}\{X_{n+1}=j|X_n=i\}$...
- 1
0
votes
2
answers
627
views
Generalized expression for balls and bins problem
$n$ number of balls are thrown randomly to $m$ number of bins, standing in a row. The balls are labeled as $1,2,3,....n$ and bins are also labeled as $1,2,3,...,m$. The probability of $i_{th}$ ball ...
- 25
0
votes
1
answer
71
views
Monotonicity of the gap of permutated sequence
Let $a$ be an arbitrary sequence and denote by $\mbox{gap}_k(a) = a_{(k)} - a_{(k+1)}$, where $a_{(k)}$ is the $k$th largest component of $a$. Of course, $k+1$ should be no larger than the length of $...
- 773
0
votes
1
answer
227
views
two correlated processes
I apologize if this question is not placed in the right place. But I am having a hard time to figure it out. It would be greatly appreciated if some one could help me out.
Assume that there are two ...
- 1
0
votes
1
answer
4k
views
Calculate the probability of winning for a selected tic-tac-toe player
I am not a mathematician, I am a programmer. Sorry, if formulation of the problem is inexact.
I want to calculate the probability of winning for a selected tic-tac-toe player.
I have a directed graph ...
0
votes
1
answer
145
views
Limiting probability question [closed]
Let $X$ denote an $m\times n$ matrix and suppose that each value $x_{ij}$ is an integer that is selected uniformly at random from ${1,\dots,n}$, independently of all other values. If we fix $m$ and ...
0
votes
1
answer
123
views
Enumeration of quadrangulations with a boundary and simple faces.
I wish to enumerate all quadrangulations of a $2p$ gon with $n$ internal vertices. Quadrangles are required to have simple faces. Simple face means all four vertices of each quadrangle are distinct.
...
- 141
0
votes
1
answer
292
views
Probability of preserving connectivity between pair of vertices in weighted graph
Let $G=(V,E)$ be an undirected graph and $p \colon E \mapsto (0,1]$ defines weights of its edges.
Let's fix two connected vertices $v_1, v_2 \in V$.
Random graph $G'=(V,E')$ is obtained from $G$ by ...
- 3
0
votes
2
answers
116
views
Upper bounds on quotients of binomial coefficients
Let $\gamma>1$ be a real number and let $n\in \mathbb{N}$.
Define $f\colon\mathbb{N}\to[0,1]$
$$
f(n_0) = \frac{\binom{n-n_0}{m}}{\binom{n}{m}},
$$
where
$$
m = \Big\lfloor{\frac{n}{\lceil\gamma ...
0
votes
0
answers
63
views
Arrangements of fixed $k$-polyplets in a $n\times n$ matrix
Recently, I asked a question about the number of arrangements of $k$ elements inside a $n\times n$ matrix with certain restrictions. The one I´m actually interested in for this question is in its 2. ...
- 47
0
votes
0
answers
55
views
Counting matrix paths for (n,m>2) matrices
Given a $n\times m$ matrix with $k$ elements inside it, I need to calculate the number of arrangements of those $k$ elements that form at least 1 path from the top to bottom matrix row composed of the ...
- 47
0
votes
0
answers
82
views
High probability bound on number of sparse solutions to Gaussian linear system
Suppose we have a random matrix $A \in \mathbb{R}^{m \times n}$ with all entries i.i.d. from the standard Normal distribution $\mathcal{N}(0, 1)$. Suppose $k$ divides $n$, and let $S \subseteq \mathbb{...
- 43
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
0
votes
0
answers
222
views
Convergence to normal distribution in total variation distance
Let $X_i$ be independent, identically distributed random variables with a uniform distribution on $\{M+1,...,2M\}$ (say), where $M$ is a positive integer. What would be a lower bound for how rapidly $...
- 20.2k
0
votes
0
answers
45
views
Lower bound for the gap in an interval randomly divided into $M$ pieces
Assume we randomly take $M$ integers $t_1 \le t_2 \le \dots \le t_M$ from the set of integers $\{ 1, 2, \dots, T \}$ such that $t_M = T$. We further denote $t_0 = 1$ for convention. For each $s \in [1,...
0
votes
0
answers
58
views
Impact of reducing the number of distinct elements in the Count distinct problem
I am dealing with the Count distinct problem and Space saving algorithm. The problem goes like that:
I have a stream of $N$ elements. The number of distinct elements is $D$. Space saving algorithm is ...
- 11
0
votes
0
answers
133
views
is there an example in planar graph that using probabilistic methods
The probabilistic method is a technique for proving the
existence of an object with certain properties by showing that
a random object chosen from an appropriate probability
distribution has the ...
- 1,851
0
votes
0
answers
45
views
On full rank submatrices of a construction
Take two matrices $T_1$ and $T_2$ in $\mathbb Z^{n\times n}$ with entries uniformly in $[-b,b]\cap\mathbb Z$ at some $b>0$. The matrices will be of rank $n$ each with probability at least $1-\frac1{...
- 1,826
0
votes
1
answer
260
views
Express inclusion-exclusion principle in terms of matrix operations
First of all i denote $\{1,2,3,...,m\}$ by $[m]$
Let there be a collection of sets $\alpha=\{A_{1},A_{2},...,A_{m}\}$ such $\bigcup_{i\in[m]}A_{i}\subseteq [n]$
Consider any function $f:\mathcal{P}([...
- 123
0
votes
0
answers
39
views
hypergraph product that preserve expansion properties
I am looking for a hypergraphs product of hypergraph H1,H2 that preserves some expansion properties of H1,H2.
The expansion property I am looking at is HD-random walk.
The product I am looking for is ...
- 340
0
votes
0
answers
62
views
Probability of detecting small bias in a die in the low confidence regime
We are given a biased $m$-sided die: one of the sides has probability $\frac{1}{m} + \gamma$ and all the rest have probability $\frac{1}{m} - \frac{\gamma}{m-1}$ each. The goal is to figure out which ...
- 211
0
votes
0
answers
119
views
the enumeration of 2 dimensional lattice walks with fixed number steps and largest distance from the end point ti the origin
There is actually an one dimensional version of this problem. For each step of the lattice walk, we can move either east for one unit or west for one unit. The problem is that given a fixed $n$ steps ...
- 167
0
votes
0
answers
72
views
Generating function for number of r-disjoint subsets each of size k
Fix $n, k$. Let
$$
C^{n,k}_r =\frac{1}{r!} \binom{n}{\underbrace{k, \ldots, k}_{\text{r times}}, n-rk} = \frac{n!}{r!(k!)^r(n - kr)!}
$$
be the number of ways to form $r$ disjoint subsets each of ...
- 101
0
votes
0
answers
72
views
A random variable standing for the size of connected component including a given node in a tree
Suppose we have a tree $T = (V,E)$, in which each nodes $v_i \in V$ has a probability $p_i$ to vanish. Let $v_0\in V$, we define random variable $\boldsymbol{X} = \boldsymbol{X}(T, v_0)$ stands for ...
- 1,551
0
votes
0
answers
82
views
The effect of channel error on the determinant of transmitted matrix
Assume the following matrix
$$
E:=\left(
\begin{array}{ccccc}
e_1 & e_2 & \cdots & e_{p-1} & e_{p}\\
e_{p+1} & e_{p+2} & \cdots & e_{2p-1} & e_{2p} \\
\...
- 313
0
votes
0
answers
87
views
Variation on stones in buckets
This is a spinoff, see Collecting stones in n buckets. Frankly speaking my only motivation is that I became curious: what happens if one redistributes the stones into the same buckets?
More ...
- 18.4k
0
votes
0
answers
86
views
Derandomizing AP existence in $A\subseteq \{1,\ldots,N\}$ for $\delta(A) \geq 1/k$
In the answer to the mathoverflow question here, it was established that if we let $p$ be the probability of including point $v$ in $A\subseteq \{1,\ldots,N\}$ and this is done independently for all ...
- 10.4k
0
votes
1
answer
81
views
An asymptotic set containment problem [closed]
Given a set of $n\in\Bbb N$ integers $\mathcal S$, suppose we choose two sets:
$$\mathcal S_{\mathsf{small}}\subseteq\mathcal S$$
$$\mathcal S_{\mathsf{big}}\subseteq\mathcal S$$ with cardinalities
...
user76479
0
votes
0
answers
216
views
Computation on Random Bipartite graphs
I'm looking at a random bipartite graph $K_{\omega(n)}*K_{\omega(n)}$ where $\mathrm{log}(n)\leq \omega(n) \leq n^{1/2}$, in which each of the $\omega(n)^{2}$ edges is placed randomly with probability ...
- 903
0
votes
0
answers
257
views
Sum over a product of binomial coefficients related to a collision problem
I am working on a certain collision problem. The probability of forming $j$ particles upon collision of $m$ and $n$ particles is given by the following equation:
$$R\left(n,m,j\right)=\sum_{k=0}^{n}...
- 1
0
votes
0
answers
347
views
An interesting version of the problem “balls into bins”
Consider n people, each has k identical balls. Each people choose k different bins from m bins, constrained by the condition that there are no two people choose exactly the same k bins. For instance, ...
- 1
0
votes
0
answers
91
views
Pruning copies of an element from a multiset via a uniform random selection process - does vigilance matter?
This is an extension of a previous question of mine (nicely answered by Douglas Zare): Filling a bin with one type of element when uniformly selecting from a set of two (with bias)
Say I fill a ...
- 43
0
votes
0
answers
102
views
Efficient algorithm for computing the mixed moments of sums of random variables
Let $X_1,\dots,X_m$ be dependent random variables. We are interested in efficient algorithms for computing the following quantity:
$$E\Big[\Big(\sum_{i=1}^m X_i\Big)^k\Big],$$
where $k\in\mathbb{N}$ ...
- 1
0
votes
1
answer
182
views
How to Rigorize an inequalities argument
Context
I'm working on a problem involving Lovasz Local Lemma, for proving that there exists a graph with a certain property.
What I need to prove:
There exists some constant $c$, and functions $p,...
- 3
0
votes
0
answers
127
views
A problem about partial sum of random number composition
Consider the strong random number composition,
$x_1 + x_2 + \cdots + x_n = m$, with $x_i > 0$ and all possible compositions have the same probability.
Let random variable $S_i = \sum_{j=1}^i x_j$...
- 177
0
votes
0
answers
319
views
Estimating a multinomial sum
I have the following sum
\begin{equation}
\sum_{r_1=q+1}^{\tau}\dots\sum_{r_\lambda=q+1}^{\tau}{\tau\choose r_1,\dots,r_\lambda,\tau-r_1-\dots -r_\lambda} (\Lambda-\lambda)^{\tau-r_1-\dots-r_\lambda}
\...
-1
votes
2
answers
217
views
Expected number of balls left out when choosing $n$ times from $n$ balls
I am given $n$ balls. For $n$ times, I pick one of them with uniform probability and put it back after picking it.
Let $U$ be the number of balls I have never picked, so $U\in \{0,\ldots,n-1\}$. We ...
- 48.9k
-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
-1
votes
1
answer
93
views
Variance of bins for N balls into M bins [closed]
If I throw N balls independently into M bins with uniform probability, the expected mean of the M bins is N/M balls.
What is the expected variance of the M bins?
I was thinking of what bin size I ...
-1
votes
1
answer
364
views
Basketball shots and stopping rule [closed]
Moved over from StackExchange.
You are taken to play a basketball game where you can shoot basketballs at n slots using a machine that is equally likely to shoot the balls into those n slots. You can ...
- 1
-1
votes
1
answer
76
views
Transforming random variables for having good property?
For arbitrary functions $A$ and $B$ and independent random variables $X$ and $Y$, assume that
\begin{align}
\Omega&\triangleq \{(x,y): A(x,y)=1\},\\
\Lambda&\triangleq \{x: B(x)=1\}.
\end{...
- 287
-1
votes
1
answer
428
views
Bins and colored balls
Consider $n$ color balls. We throw them as follows. For a given ball $i$, randomly choose $k$ bins; create $k$ 'copies' of the ball (i.e., of the same color of the ball $i$); throw a 'copy ball' into ...
- 367
-2
votes
2
answers
280
views
Balls into bins with random number of balls
In the classical balls into bins we throw $m$ balls into $n$ bins. We throw the balls independently of each other and the probability of choosing the bins is uniform. For $n=m$ it is known that the ...