This tag is for basic questions about probability and for questions in which one wants to calculate a probability, expected value, variance, standard deviation, or similar quantity. For questions about the theoretical footing of probability (especially using measure theory), please ask under ...

learn more… | top users | synonyms (2)

10
votes
0answers
367 views

Cramér's Model - “The Prime Numbers and Their Distribution” - Part 1

I was reading "The Prime Numbers and Their Distribution" by Gérald Tenenbaum and Michel Mendès France, the section about Cramér's Model, and I couldn't prove a couple of results. I would like to start ...
9
votes
0answers
156 views

Variational formulations in group theory?

I apologise if this is a naïve question. Are there any known / widely applicable / important variational formulations in (finite) group theory? That is, a relationship of the form $$\alpha(G) = ...
9
votes
0answers
246 views

Does this random variable have a density?

I have a persistent problem, which I'm almost certain can be answered using elementary probabilistic arguments, but for some reason I've been stuck for some time. Here is the problem. Let $(B_s, s ...
8
votes
0answers
125 views

Algorithm to compute fastest method of collecting $k$ re-spawning items which spawn at $n$ specified points

Let $V = v_1, \dots, v_n$ be the locations the items can spawn at, and let $U = u_1, \dots, u_k$ be the current positions of the items. We will assume a new items spawns instantly every time we ...
8
votes
0answers
245 views

Extracting an (almost) independent large subset from a pairwise independent set of Bernoulli variables

Let $n>1$, and let $X_1,X_2, \ldots ,X_n$ be non-constant random variables with values in $\lbrace 0,1 \rbrace$. Let us say that a subset of variables $X_{i_1},X_{i_2}, \ldots,X_{i_d}$ is complete ...
7
votes
0answers
80 views

A matrix with a dense submatrix - application of Chernoff’s Inequality

I am trying to solve an exercise from this book, which I will post here for convenience. I have a bit of a problem understanding how the hint of using Chernoff's bound implies the claim. Specifically ...
7
votes
0answers
74 views

Probability on entering direction of a simple random walk

Let $X(n)$ be a simple random walk on $\Bbb{Z}^2$. Also we define $S_{R} = \inf\{n > 0 : X(n) \notin [-R, R]^2 \} $ : the exit time of the square $[-R, R]^2$, $T_{v} = \inf\{n > 0 : X(n) = ...
7
votes
0answers
257 views

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 ...
7
votes
0answers
675 views

Azuma's inequality to McDiarmid's inequality?

I was going through some notes on concentration inequalities when I noticed that there are two commonly-cited forms of McDiarmid's inequality. Long story short: I know how to prove the weaker one from ...
7
votes
0answers
324 views

Is this question solvable? $2$ non-linear equations and the proof that the solution is unique (with asymmetric bounty option)

As mentioned in the title I want to show the uniqueness of the solution to $2$ non-linear equations. However, it seems that I can not solve this question with my current mathematical knowledge. More ...
7
votes
0answers
311 views

Does this calculation have a name, or a generic formulation?

Background I would appreciate help in identifying / explaining this operation: To calculate each of the $n$ values of $f(\Phi)$: sample from the distribution of each of $i$ parameters, $\phi_i$ ...
6
votes
0answers
95 views

Upper and Lower Bounds on $Var(Var(X\mid Y))$

Are there any particular properties that \begin{align*} Var(Var(X\mid Y)) \end{align*} satisfies so that we can derive any upper and lower bounds on it. For example, if we replace $Var$ with ...
6
votes
0answers
185 views

Does the set of $m \in Max(ord_n(k))$ for every $n$ without primitive roots contain a pair of primes $p_1+p_2=n$?

I have made the following observation: for those n even numbers that do not have primitive roots modulo n ,$Pr(n)$, the set $M(n)$ of those $k$ having a maximum multiplicative order $ord_n(k)$ ...
6
votes
0answers
103 views

Normalizing factor for product of Gaussian densities - interpretation with Bayes theorem

The normalizing factor for the product of two multivariate Gaussian densities, $f(x)$ and $g(x)$ with mean vectors $a$ and $b$ respectively, and covariance matrices $A$ and $B$ respectively, is itself ...
6
votes
0answers
267 views

The Expectation of a function of independent random variables

Assume we have for some index $i>n$ ($n \in \mathbb{N} $) the following ${\it Independent \ Random \ Variables}$ $$h_i \sim \text {i.i.d }\ \ \mathcal{CN}(0,1) \ \ \text{ Complex Gaussian}$$ ...
6
votes
0answers
233 views

Combinatorics: Number of possible 10-card hands from superdeck (10 times 52 cards)

I have the following problem from book "Introduction to Probability", p.32 A certain casino uses 10 standard decks of cards mixed together into one big deck, which we will call a superdeck. ...
6
votes
0answers
97 views

Finding an upper bound for $\frac{d}{d\theta}\beta^*(\theta)|_{\theta=\theta_0}$

Suppose that a random variable X has a distribution depending on a parameter $\theta$, $\theta \in \Theta$, and consider a test of hypothesis $H_0: \theta = \theta_0$ versus the alternative $H_1: ...
6
votes
0answers
512 views

How does the answer to Feynman's Restaurant Problem change if $M$ is not restricted to a single value?

First, the background: Feynman's restaurant problem asks how we can maximise the total rating of the meals we eat at a restaurant with $N$ items on the menu, given that we know up-front that we are ...
6
votes
0answers
214 views

Question on Conditional expectation

Let $X_1$ and $X_2$ be two random variables on $(\Omega,\mathcal{B},P)$. Suppose there is a function $g:\mathcal{B}\times\mathbb{R}\rightarrow[0,1]$ such that for any $x$, $g(\cdot,x)$ is a ...
6
votes
0answers
367 views

Calculating probability of some event using geometric considerations

I want to estimate exponentially the following probability: Let $\bf{U}\in\mathbb{R}^n$ be a random vector uniformly distributed on the $n$-dimensional hypersphere, centered at the origin with radius ...
6
votes
0answers
316 views

An application of the Optional Sampling Theorem

let $S(k), k\geq 0$ a discrete random process. Suppose $S(N)$ is with probability one either 100 or 0 and that $S(0)=50$. Suppose further there is at least a sixty percent probability that the price ...
5
votes
0answers
38 views

Conditional expectation involving some complications around exponential random variables

Here is my problem. Consider four independent exponential distributions $X^A_1$, $X^B_1$, $X^A_2$, $X^B_2$ where $X^A_1$ and $X^B_1$ are $exp(\lambda_1)$ and $X^A_2$ and $X^B_2$ are $exp(\lambda_2)$. ...
5
votes
0answers
41 views

Equivalent definitions of Poisson process

Define a Poisson process with parameter $\lambda$ is a counting process $(N(t))_{t\ge 0}$ such that: (i) $N(0)=0$; (ii) It has independent increment property; (iii) $N(t+h)-N(t)$ has Poisson ...
5
votes
0answers
62 views

$\sigma$-algebra $\mathcal{G} \subset \mathcal{F}$ is countably generated iff there is a random variable $X$ such that $\mathcal{G} = \sigma(X)$.

Where can I find a reference to the proof of the fact that a $\sigma$-algebra $\mathcal{G} \subset \mathcal{F}$ is countably generated if and only if there is a random variable $X$ such that ...
5
votes
0answers
110 views

Probability that a five is seen before any of the even numbers are seen

A fair die is repeatedly tossed. What is the probability that a five is seen before any of the even numbers are seen? I have my own solution below and just want someone to verify it. According ...
5
votes
0answers
63 views

Probability of winning at Solitaire

Using a standard deck of playing cards, how many ways of assembling (shuffling) them will result in a competent player always "going out" in a standard (seven initial columns, every remaining third ...
5
votes
0answers
257 views

Probability that at least one of four hands missing at least one suit

Deal each of four players a 13-card hand at random. What is the probability that at least one of the four hands is missing at least one suit? Let $A_i$ mean that player $i$ is missing at least one ...
5
votes
0answers
149 views

Probability of transmission between two nodes in a neural network at exactly d timesteps

I have a network which is an Erdős–Rényi graph. It is a simple neural network with degree 0.7N where N is the number of nodes. Each weight between neurons is 1/N, meaning that if node n has fired the ...
5
votes
0answers
72 views

Standard deviation of a quantum walk?

The standard deviation of a classical random walk with $n$ steps is $\sqrt n$ - Standard deviation of a random walk. I have read in many places that the standard deviation of a quantum walk $n$ with a ...
5
votes
0answers
61 views

Renyi entropy of prime gaps

Denote with $p_n$ the $n$-th prime number and let $$ h_N(d) = |\{ n : p_{n+1} < N, p_{n+1} - p_n = d \}| $$ be the number of times that prime gap $d$ happens for primes less than $N$. Let $H = ...
5
votes
0answers
75 views

How much larger is the $\sigma$-algebra than the algebra in Caratheodory extension?

Given a 'measure' $\lambda$ on an algebra $\mathcal{A}$ of sets, Caratheodory gives a way to extend this $\lambda$ to a $\sigma$-algebra. The idea is we define an outer measure (on all subsets) ...
5
votes
0answers
299 views

Inequality between incomplete beta and gamma functions

Let the regularized incomplete beta and gamma functions be defined as usual: \begin{equation} I_p(z,w) = \frac a {B(z,w)} \int_0^p t^{z-1} (1-t)^{w-1} \,\mathrm dt, \end{equation} \begin{equation} ...
5
votes
0answers
192 views

Central Limit Theorem on the Circle

I am interested in a circular equivalent to the classical CLT. Is there a necessary and sufficient condition telling when a normalized sum of circular distributed random variables converges to a ...
5
votes
0answers
212 views

I need help about some compactness arguments

I need help to find some compact sets for my engineering problem. Through this page I learned quite much about it however since I have neither read a book yet nor have an experience I am not able to ...
5
votes
0answers
175 views

Need advice: what should be my next step?

I am dealing with a quite algebraic question and I arrived at some good point. I had $2$ equations with $2$ unknowns and I was able to eleminate one of the variables. My final equation still seems ...
5
votes
0answers
91 views

Does Multiplicative Version of Azuma's Inequality Hold?

We know that there are multiplicative version concentration inequalities for sums of independent random variables. For example, the following multiplicative version Chernoff bound. Chernoff bound: ...
5
votes
0answers
146 views

Bayes analysis as used in a Presidential Election - with calculations shown

Can you show all the steps needed for a Bayesian probability progression as new information is received. As an example, initial estimate for Obama to win (popular vote) is 55%. In state-A, Democrats ...
5
votes
0answers
127 views

Probability distribution for finding two values in stages

Fix two arbitrary distinct values from $\{1,\dots,n\}$. Say for concreteness we choose the values $1$ and $2$. We sample uniformly with replacement from $\{1,\dots,n\}$ in a number of stages. Each ...
5
votes
0answers
782 views

1D Random Walk, with different step sizes in each direction.

A walker starts at a defined position greater than $0$, say $A$, and then makes a "decision" to walk either "$b$ steps to the right" or walk "$c$ steps to the left." He will choose the first option ...
5
votes
0answers
165 views

Bounding function involving Beta functions

Given $\frac{a}{x-1} \leq \frac{b}{y-1} \leq \frac{c}{z-1}$ with $a,b,c > 0$ and $x,y,z > 1$, I want to show that $$\frac{(\frac{a}{a+b})^{x-1}(\frac{b}{a+b})^{y-1}}{B(x,y)\cdot (x+y-1)} + ...
4
votes
0answers
60 views

Simplifying Chain of Conditional Variances given a Markov Chain

$\newcommand{\Var}{\operatorname{Var}}$Suppose $X,Y,W$ form a Markov chain $X \to Y \to W$. Can we simplify the following expression? \begin{align*} E [ \Var ( \Var (X\mid Y) \mid W)] \end{align*} ...
4
votes
0answers
47 views

Brownian motion and associated martingales

Under the Wiener measure $\Bbb{W}$ the process $x(t)$ is a brownian motion. This means that $\Bbb{E}[{x(t)-x(s)\mid \mathcal{F}_s}]=0$. Let $P$ be a measure in $C([0,\infty),\Bbb{R}^d)$ such that ...
4
votes
0answers
40 views

What are the odds that the pattern, win lose lose, will happen 23 times in a row (69 rounds)?

In a game of 50/50 (this example could be a coin flip). Before any flips, What are the odds that the pattern win lose lose (heads tails tails if your choice was heads each time.) will happen 23 times ...
4
votes
0answers
50 views

Discrete Time Two sided Gaussian Random Walk : Hitting Time Distribution

I am looking at the hitting time of a two sided Gaussian random walk i.e. $S_{n}=\sum_{i=1}^{n}X_{i}$ where $X_{i}$ are i.i.d normally distributed random variables. The hitting time is ...
4
votes
0answers
53 views

How many possible shuffles can be won perfectly?

It is known that the possible shuffles of a deck of cards is $52!$, or ~$80658175170943878571660636856403766975289505440883277824000000000000$ different combinations. I have become aware of a game ...
4
votes
0answers
37 views

Computing MMSE and conditional expectation

Suppose we have three independent, zero mean, finite variance random variables $V,W,Z$ and where $W,Z$ are Gaussian random variables. These random variables form a new random variable $Y$ ...
4
votes
0answers
86 views

Hitting time for a random walk on the grid

Consider the grid on $n^2$ nodes composed of points $x$ and $y$ with coordinates in the set $\{1, \ldots, n\}$, and consider the discrete-time Markov chain which transitions to a random neighbor at ...
4
votes
0answers
34 views

Analysis of sorting Algorithm with probably wrong comparator?

It is an interesting question from an Interview, I failed it. An array has n different elements [A1 .. A2 .... An](random order). We have a comparator C, but it has a probability p to return correct ...
4
votes
0answers
159 views

Probability of turning a 3x3 Rubik's Cube 50 random turns and solving

So I am working with my secondary Algebra II class on permutations, combinations, and probability and had an idea for an interesting problem that I hope can work for their skill level. We have been ...
4
votes
0answers
40 views

Combinatorics and Probability- where am I wrong?

Let there be a cube with $n$ sides denoted $1,...,n$ each. The cube is tossed $n+1$ times. For $1\le k\le n$, what is the probability that exactly $k$ first tosses give different number (i.e, the ...