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 (1)

14
votes
0answers
310 views

Distribution of roots of complex polynomials

I generated random quadratic and cubic polynomials with coefficients in $\mathbb{C}$ uniformly distributed in the unit disk $|z| \le 1$. The distribution of the roots of 10000 of these polynomials are ...
9
votes
0answers
258 views

Expected value of the distance square

Given two points $X,Y$ on two sides of square $[0,1]\times [0,1]$ ($X:(0,1/2),Y:(1,1/2)$ (PS: My original question is $X,Y$ on opposite of a square, but I think that's not the real case) )and $n$ ...
8
votes
0answers
188 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
207 views

How do you compute numerically the Earth mover's distance (EMD)?

I was trying to compute numerically (write a program) that calculated the EMD for two probability distribution $p_X$ and $q_X$. However, I had a hard time finding an outline of how to exactly compute ...
7
votes
0answers
201 views

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

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

Find the probability that a matrix is diagonalizable

The original question is as follows, Let $p$ be an odd prime number. The entries of a $2\times2$ matrix $A\in M_2(\mathbb Z_p)$ are selected at random. (a) Find the possibility that $f_A(x)$ splits ...
6
votes
0answers
167 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 ...
6
votes
0answers
123 views

Recurrence of a certain class of $2$-$d$ random walks

As is well known, a symmetric random walk on $\mathbb{Z}^d$ (the lattice of $d$ dimensional vectors with integer components) is recurrent if and only if $d=1,2$. In particular it is transient for ...
6
votes
0answers
353 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 ...
6
votes
0answers
276 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 ...
6
votes
0answers
358 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
303 views

A problem about strong law of large numbers of Shiryaev's Probability

This is a problem after the section "Strong Law of Large Numbers" of Shiryaev's Probability: Let $\xi_1,\xi_2,...$ denote independent and identically distributed random variables such thatt ...
6
votes
0answers
341 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 ...
5
votes
0answers
68 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
129 views

Coding Theory Problem to save Humanity

For starters, this problem doesn't originate from me, it's a friend's coding theory problem and I got interested, thinking about it, but I can't think of any as I only have very basic coding theory ...
5
votes
0answers
75 views

Spectral gap of mixture of Markov chains

Context Let $P$ be the transition matrix of an irreducible, aperiodic, discrete-time Markov chain. The spectral gap is given by $$\xi = 1 - \lambda_\max$$ where $\lambda_\max = \max\{\lambda_2, ...
5
votes
0answers
74 views

Random point distribtion

How to generate numerically a set of random points $(x_1,y_1), (x_2,y_2),\cdots, (x_N,y_N)$ such that the pair-wise distances $d = \sqrt { (x_i-x_j)^2 + (y_i-y_j)^2}$, for all $ 0<i\le N, ...
5
votes
0answers
121 views

Probability of Multiple Collisions in the Birthday Problem

I need help with an approximation concerning the birthday problem. In a recent MAA Monthly (August-September 2013) article "Simple Approximation Formulas for the Birthday Problem" by Matthias Arnold ...
5
votes
0answers
114 views

A tight lower bound for the entropy of the XOR of two random variables

Let $U$ be the uniform random variable over $n$-bit binary strings, and let $X$ be another random variable that is dependent on $U$ and ranges over $n$-bit binary strings. Assuming $I(X;U) \le ...
5
votes
0answers
206 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
147 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
124 views

Conditional expectation as a random variable

We have three random variables $x,y,z$. Is the condition "$y$ and $z$ are independent" enough to guarantee that "$\mathbb{E}(x\,|\,y)$ and $z$ are independent"? Would anyone give me a brief proof or ...
5
votes
0answers
192 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
148 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
160 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 ...
5
votes
0answers
129 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
112 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
517 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
147 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
57 views

Why if we use independence and factorization, we cannot represent every joint distribution? (rigorous argument needed)

I was reading Koller's Probabilistic Graphical models book and it says something like this: Let $P(x_i) = \theta_i$. Define: $$P(x_1, \ldots , x_n) = \prod_{i=0}^n \theta_i$$ This ...
4
votes
0answers
47 views

Would you please take a look if my substantiation is correct?

The four numbers 4, 5, 6, 7 are randomly inserted into 7 .3 .4 . 6 . 48 The result is a ten-digit number - for example, 7 4 3 5 4 6 6 7 48 How high is the chance, that the number created is ...
4
votes
0answers
64 views

Uniform integrability of the maximum of a random walk with negative drift

Given $S_k^{(n)} = X_1^{(n)} + ... + X_k^{(n)}$ for all $k,n\in\mathbb{N}$, where the $X_i^{(n)}$'s are iid with mean $-\gamma$ for some $\gamma > 0$ and unit variance. Let ...
4
votes
0answers
48 views

A question on CLT from Durrett.

I have a question from Durrett which I don't quite get the solution. The question is and the solution is I think I understand up to when $|S_n - n| \leq n^{2/3}$ is an event w.p.1, this is ...
4
votes
0answers
74 views

Is this a correct Monte-Carlo expression for $\pi$?

I have a bicycle with one of those O-locks on it and too often when I park the bike and I want to lock it, the lock hits one of the spokes of the rim. This can be frustrating and surprises me that it ...
4
votes
0answers
48 views

$\pi$ Monte-Carlo - Probability that O-Lock hit a Spoke?

(Edit: can someone please help me migrate this to physics stack? I think they would be more interested in helping me out with this problem. Thanks.) I have a bicycle with one of those O-locks on it ...
4
votes
0answers
77 views

Dividing a deck of cards using only imagination

The idea came up from a discussion I had with my friends. Suppose we want to play a game using a deck of cards, and we can't use any physical materials. If we are intelligent enough, we can remember ...
4
votes
0answers
108 views

Card game probability

Suppose the following solitaire with a standard deck. I turn four cards visible on the board and on each turn, I remove those suits that appears more than once in the board. Then I fill the board such ...
4
votes
0answers
41 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) ...
4
votes
0answers
90 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 ...
4
votes
0answers
152 views

Puzzle - zero knowledge proof

I am solving the following problem : I have edge-matching puzzles, where all pieces are squares and the grid has $n$*$n$ format. There is no global image to guide a puzzle solver. Despite the puzzles ...
4
votes
0answers
66 views

A Continuous-Time Markov Process Taking All Possible Values

Let $\mathbb{N}$ be the set of positive integers. For each $n \in \mathbb{N}$, let $X^{(n)}=\{ X^{(n)}(t): t \geq 0 \}$ be a Markov chain with state-space the two point set $\{0,1\}$ and $Q$-matrix ...
4
votes
0answers
78 views

Probability of a submatrix with all 1s

I'm not an expert and while reading an article on grid coloring these two questions came to my mind: Given a $n \times n$ matrix randomly filled with values in $\{0,1\}$ ( $P(a_{ij} = 1) = 1/2$), ...
4
votes
0answers
235 views

Different Perspectives of Multinomial Theorem & Partitions

There are 2 important interpretations of the multinomial theorem and coefficients. 1: Determining the number of ordered strings that can be formed using a set of letters. For example, with 1 m, 4 ...
4
votes
0answers
215 views

How do factor graph and sum-product algorithm work?

I'm reading a tutorial on factor graph and its sum-product algorithm. The tutorial is at http://www.isiweb.ee.ethz.ch/papers/arch/aloe-2004-spmagffg.pdf. What I don't understand is the example on page ...
4
votes
0answers
146 views

Using Bernoulli distribution approximate the $q$-th moment

Let $x$ be vector in $R^n$. Let $\pi(⋅)$ be a permutation on the set $\{1,\ldots,n\}$ with a uniform distribution. Let $|m|\leq n, m \in Z$. Using Bernoulli (or maybe some other) distribution ...
4
votes
0answers
195 views

Disintegration of Measures

I was thinking about this exercise and I can't see how to end it. I'm sorry about the long post and thank you for the attention. Before asking the question, I need some background. Let $(\Omega, ...
4
votes
0answers
82 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: ...
4
votes
0answers
82 views

Modeling concurrent internet users

I'm feeling generous in the new year and want to open my Wifi connection to the public. I want to estimate the effect that $N$ additional users on my router would have on download times. In other ...
4
votes
0answers
169 views

estimation of transition probabilities from aggregate data

Please, O mathematicians, help me understand the approach to the problem of estimating transition probabilities given only aggregate data in Kalbfleisch & Lawless' 1984 paper "Least-Squares ...