0
votes
0answers
26 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
24 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
56 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 ...
1
vote
1answer
47 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
21 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
43 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
72 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 ...
8
votes
2answers
164 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 ...
3
votes
0answers
71 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
34 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 ...
10
votes
1answer
68 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
46 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 = ...
24
votes
3answers
478 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
39 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
50 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
163 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
113 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) = ...
1
vote
1answer
52 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
440 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
65 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
182 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
34 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
40 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
94 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
269 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
109 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
76 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
46 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
42 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
335 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
125 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
283 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
77 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
118 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
124 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
241 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 ...
2
votes
1answer
97 views

Proof $\frac{1}{(\frac{n}{3})!}=2^{-\Omega(n \log n)}$

I saw this in Wegener(2003), Methods for the Analysis of Evolutionary Algorithms as a upper bound on the probability. After applying Stirling approximation to $(\frac{n}{3})!$ I still keep getting ...
3
votes
1answer
105 views

Asymptotics of a mixture

Let $x_1, x_2 \cdots x_M$ be a sequence of iid random variables taking values over the integers, with $E(x_i)=0$. In particular, I'm interested in a shifted Poisson: $X=P-1$, where $P$ is Poisson with ...
3
votes
4answers
151 views

Equality of outcomes in two Poisson events

I have a Poisson process with a fixed (large) $\lambda$. If I run the process twice, what is the probability that the two runs have the same outcome? That is, how can I approximate ...
7
votes
1answer
238 views

Stochastic assignment problem

Given an $n \times n$ real matrix $C$, we can try to maximize $$\Phi(C, \pi) = \frac{1}{n} \sum_{i} C_{i,\pi(i)} $$ over $\pi \in S_n$, the set of all permutations on $n$ objects. What can one say ...
0
votes
2answers
154 views

Asymptotic probability: boys and girls in a line

We have $n$ people: $\alpha n$ are boys and $(1-\alpha)n$ are girls. They are standing in a line in a random order. We pick up one boy also at random. What can one say about the probability that ...
6
votes
1answer
155 views

Inequality on balls/bins with nested logs

Let $k = \lceil \frac{3 \ln n}{\ln \ln n}\rceil$. How does one show that $$ \left(\frac{e}{k}\right)^k \frac{1}{1-\frac{e}{k}} \le n^{-2} ? $$ This is from p. 44 of Motwani and Raghavan, Randomized ...
7
votes
3answers
174 views

Asymptotic behavior of the first step in a best strategy

Consider the game described here, but for a sequence $X_1,\ldots,X_n$ of i.i.d. uniform rv's on $\lbrace 1,\ldots,n \rbrace$ (in the original game $n=6$). Using the original notation, let $a_n$ denote ...