0
votes
1answer
34 views

Show that $Pr[X \gg Y]\approx 1$

Can one show (and how) that $$Pr[X \gg Y]\approx 1$$ for $$X:=\sum_{i=1}^k Bin\left(n\left(\frac{1}{2}\right)^i,i\right)$$ and $$Y:=\sum_{i=k+1}^{\infty} ...
0
votes
0answers
36 views

Prove $Pr[X + Y \geq x] \sim Pr[X \geq x]$

We have two independent random variables $X$ and $Y$, where $X=\sum_{i} X_i$ and $Y=\sum_j Y_j$, where $X_i$,$Y_j$ are (non-identically) Bernoulli distributed and independent. Under the assumption ...
1
vote
2answers
33 views

Does $E[X]\gg E[Y]$ for independent RV imply that $Pr[X+Y \geq x] \sim Pr[ X \geq x]$?

We have two independent random variables $X$ and $Y$, where we know that $E[X]\gg E[Y]$, thus $\frac{E[Y]}{E[X]}\rightarrow 0$. I am now interested in $Pr[X+Y \geq x]$ and would like to show that ...
1
vote
1answer
38 views

Poisson approximation of $X$ by $Poisson(E[X])$

I've tried to find something, but couldn't find anything about the following question. Is it possible to approximate any random variable $X$ with $E[X]=o(1)$ by a Poisson random variable ...
2
votes
0answers
97 views
+150

Entropy of matrix vector product

Consider a random $n$ by $n$ circulant matrix $M$ whose entries are chosen independently and uniformly from $\{0,1\}$. Let $M'$ be the $m$ by $n$ matrix which is formed by taking the first $m$ rows of ...
22
votes
1answer
385 views

Zombie outbreak on a $k$-regular graph

Suppose we have a zombie outbreak on a connected $k$-regular graph of order $n$. There are $n_0$ initially infected zombie nodes, and each turn, each zombie infects its neighbors with probability ...
7
votes
2answers
66 views

Asymptotically, how many random students do I have to mark before I've marked two consecutive students

Background The motivtion for this question comes from observations made by a colleague while he was marking homework and recording the marks this year. His procedure for recording the marks is as ...
1
vote
1answer
92 views

Asymptotics of sum of Binomial Coefficients (Binomial distribution) - Poisson approximation?

Let $$f(n):=\sum_{i=k}^n {n \choose i } p^i (1-p)^{n-i}$$ where $k\geq 2$ is a fixed Parameter and $p=p(n) \in (0,1]$ depends on $n$ where $np\leq 1$. We consider $n \rightarrow \infty$. I've found ...
0
votes
0answers
35 views

Stochastic big O notation

Let $||.||$ indicate the Euclidean norm. Let $\theta_0$ be a specific value of the parameter $\theta \in \Theta\subseteq \mathbb{R}^d$ and $G_n$ be a random vector-valued function $$ G_n : \Theta ...
0
votes
0answers
34 views

Relations between stochastic Big O-Notation, limsup and lim?

I have to solve a list of exercises on probability theory but I'm having several problems in understanding the following questions; could you help me? Thank you! Let $||.||$ indicate the Euclidean ...
0
votes
1answer
57 views

$\frac{1}{n} \sum_{k=1}^{n-s} X_{k+s}X_{k}$ the same as $\frac{1}{n} \sum_{k=1}^{n} X_{k+s}X_{k}$ for $n \rightarrow \infty$?

I need to show that $$ \frac{1}{n} \sum_{k=1}^{n-s} X_{k+s}X_{k}$$ for some number $s$ is essentially the same (asymptotically negligible) as $$ \frac{1}{n} \sum_{k=1}^{n} X_{k+s}X_{k}$$ as $n ...
2
votes
1answer
76 views

Asymptotic Relative Efficiency: Poisson

I'm trying to find the asymptotic relative efficiency of a Poisson process: $$\frac{\lambda^t \exp(-\lambda)}{t!} = P(X=t).$$ When $X = t = 0$, the best unbiased estimator of $e^{-\lambda}$ is ...
0
votes
0answers
24 views

Little O Bound, Combinatorics

I am reading a book on combinatorics. I tried deriving the result in the following sentence, but could not get it. Can someone show me the algebra? Theorem 1.2.1: If $\dbinom{n}{k} {(1- ...
1
vote
2answers
53 views

Asymptotic probability of difference of two positive random variables

Assume I have two positive, iid random variables, $X$ and $Y$. I need to compute $P\{X-Y > u\}$. I was thinking of doing $P\{X > Y + u \} = P\{X > v\}$, where $v = Y+u$. (Reason: Since $Y$ ...
2
votes
1answer
81 views

Asymptotics of the classical occupancy problem

Classical Occupancy Problem. There are $n$ distinct labeled balls in an urn. $k$ of them of uniformly selected with replacement. What is the probability that the sample contains at least one ball ...
9
votes
2answers
180 views

An extrasensory perception strategy :-)

Inspired by classical Joseph Banks Rhine experiments demonstrating an extrasensory perception (see, for instance, the beginning of the respective chapter of Jeffrey Mishlove book “The Roots of ...
4
votes
0answers
89 views

How many edges does an Erdős-Rényi graph have to have, to almost surely have a component with multiple cycles?

An Erdős-Rényi graph is a random graph, selected according to the distribution obtained one where we have some number $n$ of nodes, and some probability $p$ of each potential edge being ...
0
votes
0answers
36 views

On convergence in distribution

Let $\delta$ and $\theta$ be two estimators of the scaler parameters $\delta_0$ and $\theta_0$, respectively. Suppose that conditions are satisfied such that as the sample size $n \to \infty$, then ...
11
votes
1answer
93 views

Expected values of some properties of the convex hull of a random set of points

$N$ points are selected in a uniformly distributed random way in a disk of the unit radius. Let $P(N)$ and $A(N)$ denote the expected perimeter and the expected area of their convex hull. For what ...
0
votes
0answers
59 views

Asymptotic distribution/properties of ratio of sample mean and (biased) sample variance

Define: $$Q = \frac{2\overline{x}}{\left(s_x^*\right)^2} +1 $$ where: $\overline{x} = \frac{1}{T} \sum_{t=1}^T x_t$ $\left(s_x^*\right)^2 = \left(\frac{T-1}{T}\right)s_x^2$ where $s_x^2 = ...
25
votes
3answers
496 views

Expected length of the shortest polygonal path connecting random points

$N$ points are selected in a uniformly distributed random way in a disk of a unit radius. Let $L(N)$ denote the expected length of the shortest polygonal path that visits each of the points at least ...
0
votes
0answers
47 views

Number of Singleton Blocks in Set Partition

I'm interested in some general information on the following question: Consider the collection of partitions of an $n$-set into $m$ blocks as a uniform probability space. Let $X$ be the random ...
1
vote
1answer
51 views

Repeated Bernoulli Trials, Wins-Losses

Consider $$X(t)=\mbox{Number of wins} - \mbox{Number of losses}$$ for $t$ Bernoulli($\theta$) trials. I calculated that $$P(X(t) = x) = {t \choose (t-x)/2} \theta^{\frac{t+x}{2}} (1- ...
0
votes
2answers
170 views

Probability in ball coloring

You have exactly $n^2$ balls each one of which can be colored in one of $n^2$ ways. That is total colors is $n^2$ but I am not saying all the $n^{2}$ balls are distinctly colored. However assume each ...
1
vote
2answers
121 views

When can we exchange expectation and maximum for asymptotic results?

Motivated in the analysis of algorithms, consider the following setup. Assume we have discrete random variables $X^{(n)}_1, \dots, X^{(n)}_n$ which we can not assume to be identical or independent. ...
4
votes
1answer
96 views

How can I approximate $\sum\limits_{k=4}^{\infty}\Pr(X=k)[{\Pr(X\le k)}^6 - {\Pr(X\le k-4)}^6]$ for $\lambda \to +\infty$?

$X$ is a Poisson random variable and the probability mass function is given by: $$\Pr(X = k) = e^{-\lambda}\frac{{\lambda}^k}{k!}$$ I’ve got a probability function $f(\lambda)$ $$f(\lambda) = ...
0
votes
1answer
61 views

Joint distribution of sample quantiles

Suppose we have iid sample of size n from the distribution function of $F$ which has a continuous density $f$. How can I get the large sample joint distribution of p and q sample quantiles ? Thanks ...
8
votes
3answers
447 views

the following inequality is true, but I can't prove it

The inequality $$\sum_{k=1}^{2d}\left(1-\frac{1}{2d+2-k}\right)\frac{d^k}{k!}>e^d\left(1-\frac{1}{d}\right)$$ holds for all integer $d\geq 1$. I use computer to verify it for $d\leq 50$, and find ...
1
vote
1answer
66 views

Estimate the scale of the power series with Poisson pdf-like terms

Sorry to bother you, but I guess that this question is not appropriate for MO, so I repost it here hoping that someone could give me a clue. I would like to have an estimate for the series $$P(t) = ...
1
vote
1answer
209 views

Showing uniform convergence in probability

Suppose you want to show $sup_{x\in D}|f_n(x)|\to_p 0$, for $n\to \infty$, where $D\subset \mathbb R$ is a compact interval, $f$ is continuous depending on one or more random variables, and $\to_p$ ...
1
vote
0answers
36 views

expected value tree structure

I'm trying to do a run-time analysis of an algorithm. The idea is a tree structure is created where any node can have two children. At each iteration of the algorithm there's a 50% chance that a node ...
1
vote
0answers
41 views

Conditioned probability in certain matrices with entries 0,1,$-1$

Consider $2\times n$-matrices with entries 0, 1 or $-1$, such that the number of zeroes in both rows is the same. Let $P_n$ be the probability that the first non negative element of both rows is a ...
2
votes
1answer
100 views

Large Deviations Problem

Let $\left(X_n\right)_{n\geq 1}$ be i.i.d random variables on $\left(\Omega,\mathcal A, \mathbb P\right)$, $X_1$ with mean $\mu$, and $$ L(\lambda) = \begin{cases} \log\mathbb E\left(e^{\lambda ...
1
vote
1answer
52 views

When does $\mathbb{E}(X \log_2{X}) = \Theta(\mathbb{E}(X) \log_2(\mathbb{E}(X))$?

For discrete random variable $X$ taking values from the range $\{1,\dots,n\}$, when does $\mathbb{E}(X \log_2{X}) = \Theta(\mathbb{E}(X) \log_2(\mathbb{E}(X))$? By Jensen's inequality I think ...
4
votes
2answers
271 views

Asymptotics of system of linear equations

I have a system of linear equations as follows. $$M(p) = 1+\frac{n-p-1}{n}M(n-1) + \frac{2}{n} N(p-1) + \frac{p-1}{n}M(p-1)$$ $$N(p) = 1+\frac{n-p-1}{n}M(n-1) + \frac{p}{n}N(p-1)$$ $$M(1) = ...
3
votes
3answers
111 views

Result of Bernoulli trials being twice the expectancy?

Given a probability $0 < p < 0.5$ for success per trial with $n$ Bernoulli trials, what are the odds for having succeeded in at least $2np$ experiments?
1
vote
1answer
83 views

Approximation of binomial distribution with normal distribution

The Central Limit Theorem implies that near the center of mass we can approximate the binomial distribution with the normal distribution: $$ P(B(n,p) \geq i) \approx P(Z \geq \frac{i - n p}{\sqrt{n p ...
2
votes
0answers
49 views

Is this kind of approximation correct?

I was trying approximate the variance of a ratio of two random variables. I used to approximate it through Taylor's expansion: Assume $\sqrt{n}\big(X-E(X)\big)=O_p(1)$, ...
2
votes
0answers
72 views

Bound the probability of unlikely escape through one end of a thin rectangle

Consider the following elliptic PDE boundary value problem, \begin{eqnarray} & a u_x + b u_y + \frac{\alpha}{2} u_{xx} + \beta u_{xy} + \frac{\gamma}{2} u_{yy} = 0 \;, \quad {\rm ~for~} ...
3
votes
1answer
43 views

Bounds on integral for computing expectation

I have a discrete random variable $X$ with $P(X \geq x) = c^x$ and I would like to bound $E(\log{X})$. I can write this as follows I think $$E(\log{X}) = \sum_{x=1}^{\infty} c^x \log{x}.$$ We know ...
2
votes
0answers
91 views

Growth of number of distinct elements

Let $A_k$ be a random variable which represents the number of distinct integers seen after sampling $k$ independently and uniformly at random from the range $1, \dots, n$. Let $B_k$ be a random ...
0
votes
0answers
43 views

understanding of 1-unconditionality

Let $X=(X, \|\cdot\|_X)$ be normed space with $x_1, \ldots, x_m\in X$. Assume, $\int_{[-1,1]^m}\|\sum_{i=1}^ma_ix_i\|_Xd\mu(a)=1$, where $\mu$ is the Lebesgue measure on $[-1,1]^m$, $a \in [-1,1]^m$. ...
3
votes
0answers
386 views

Asymptotics for the expected length of the longest streak of heads.

As Introduction to Algorithms (CLRS) describes, the problem is Suppose you flip a fair coin $n$ times. What is the longest streak of consecutive heads that you expect to see? The book claims ...
4
votes
1answer
126 views

With probability $o(1)$

I am not sure how to read little/big O expressions in probability theory: What does a statement like "with probability $1-o(1)$" mean? Does it mean with high probability?
1
vote
2answers
303 views

How to interpret the little-$o$ notation in this definition of the Poisson process?

In the book Probability and Random Processes by Grimmett and Stirzaker, a Poisson process is defined to be any process $(N(t))_{t\in[0,\infty)}$ with values in $\mathbb{N}_0$ satisfying following ...
1
vote
1answer
80 views

Asymptotic equivalent of the law of lotto minimal value

This question is inspired by this one, where the law of the minimum $X$ of $m$ elements sampled without replacement from $\{1, \dots, n\}$ was investigated. In this question we wrote that the number ...
2
votes
1answer
120 views

What does it mean to select $O(k \log k / \epsilon^2)$ indices?

I'm reading [1] where some columns and rows of a matrix $A$ are selected by their leverage scores aiming to have CUR decomposition of $A$. In the paper $c$ is a value determining how many indices we ...
1
vote
1answer
131 views

Why is this true for large enough n?

$$ \begin{align*} \Pr[\text{bin } i \text{ has at least } k \text{ balls}] &\leqslant \left( \frac{e}{k} \right)^k = \left( \frac{e \ln \ln n}{3 \ln n} \right)^{\frac{3 \ln n}{\ln \ln n}} ...
7
votes
1answer
244 views

Mixing two different biased coins

My problem is as follows: I have two biased coins with probabilities $p_1$ and $p_2$ of landing heads. I start with coin 1 and toss it until it lands heads. Then I swap to coin 2 and toss until it ...
3
votes
2answers
2k views

Central Limit Theorem and sum of squared random variables

This is a two-part question. Suppose I am drawing random variables $X_i\sim A$, $1\leq i \leq n$ where $A$ is a zero-mean, finite variance $\sigma_A^2$, symmetric probability distribution having ...