Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [probability]

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 (probability-theory) instead. For questions about specific probability distributions, please use (probability-distributions).

28
votes
0answers
724 views

Probability of completing a self-avoiding chessboard tour

Someone asked a question about self-avoiding random walks, and it made me think of the following: Consider a piece that starts at a corner of an ordinary $8 \times 8$ chessboard. At each turn, it ...
21
votes
0answers
504 views

Matching red to blue dots

I have two red points, $r_1$ and $r_2$, and two blue points, $b_1$ and $b_2$. They are all placed randomly and uniformly in $[0,1]^2$. Each dot points to the closest dot from another colour; closest ...
16
votes
0answers
370 views

Multiplicative version of Mcdiarmid's inequality?

Suppose you have $n$ i.i.d. random variables taking values in $\{0,1\}$, and $X$ represents their sum. Then you can use a Chernoff bound to control the deviation of $X$ from its expectation. The ...
14
votes
0answers
321 views

Random sum in coupon collection

I have a problem which involves the standard coupon collector's problem to find a probability density from the generating convolution. I start by defining the problem and a few basic statistics. Let ...
14
votes
0answers
344 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) = \sup\{\...
13
votes
0answers
636 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 ...
12
votes
0answers
416 views

Progressive Dice Game

You have a fair, regular 6-sided dice. The game is played for $n$ turns. Each turn you make a roll and gain that many points the rolled side is showing, then do one of the following: ...
12
votes
0answers
296 views

Picking points on a sphere at random

Suppose we pick up $N$ points uniformly at random on a sphere. The probability that these points lie within a 'fixed' hemisphere is easily calculated to be $1/2^N$. But what is the probability that ...
12
votes
0answers
459 views

What is the Probability of Transmission Between Two Nodes in a Neural Network?

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 ...
11
votes
0answers
8k views

Uniform distribution on the surface of unit sphere

It is known that given $X=(X_1, X_2, \ldots, X_n)$ iid $\sim N(0,1)$, then $X/\sqrt{X_1^2+\cdots+X_n^2}$ is uniformly distributed on the surface of unit sphere. Intuitively, I know that that's ...
11
votes
0answers
438 views

Is this question solvable? $2$ non-linear equations and the proof that the solution is unique

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

Expected number of operations on a vector until one of the coordinates becomes zero.

Let's say we have a vector $v = (x_1, ..., x_n) \in \mathbb{N}^n$ where $x_1 = x_2 = ... = x_n$. Next we choose an ordered pair of coordinates at random $(i, j)$ where $i, j \in \{1, ..., n\}$ and $i \...
10
votes
0answers
471 views

At what rate does the entropy of shuffled cards converge?

Consider a somewhat primitive method of shuffling a stack of $n$ cards: In every step, take the top card and insert it at a uniformly randomly selected one of the $n$ possible positions above, between ...
10
votes
0answers
749 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 present....
10
votes
0answers
366 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 ...
9
votes
0answers
261 views

Number of simultaneously solvable linear equations with nonnegative variables

Let $N$ variables $x_i \ge 0$ but not all of them be zero. One may fix $\sum_{i=1}^N x_i = 1$. There are $P$ equations which need to be solved, with coefficients $a^k_i$ indexed with superscripts $k =...
9
votes
0answers
128 views

Generating function for number of $r$-disjoint subsets each of size $k$

Fix $n, k$. Then $$ 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)!} $$ is the number of ways to form $r$ disjoint subsets each of ...
9
votes
0answers
555 views

Calculating growth rate of a population of Minecraft chickens

I have a rather strange question (for this Stack Exchange anyway). It felt too mathematical to ask elsewhere. If this is out of place here, please let me know. A chicken in Minecraft lays eggs; ...
9
votes
0answers
235 views

How to solve probability when sample space is infinite?

I came up with a random problem yesterday: Suppose that in a random trial, each point $(x,y)$ where $x,y \in \mathbb{R}$ and $0 \leq x,y \leq 1$ is assigned a value of $0$ with 50% chance and a ...
9
votes
0answers
109 views

Asymptotic value of card drawing game

A deck consisting of $r_0$ red cards and $b_0$ black cards is randomly shuffled. The host turns up the cards one at a time; if it is red, you get $\$1$; otherwise you pay the host $\$1$ (and you're ...
9
votes
0answers
2k views

Random graph connectivity, and the existence of isolated vertices

Here $G_{n,p}$ represents the Erdős-Rényi random graph model, where the graph has order $n$ and each edge is added independently with probability $p$. I am faced with proving the following claim: ...
9
votes
0answers
407 views

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

Background Informatiom I would appreciate help in identifying or explaining this operation: To calculate each of the $n$ values of $f(\Phi)$: Sample from the distribution of each of $i$ parameters, ...
8
votes
0answers
580 views

Probability that no team in a tournament wins all games or loses all games.

Five teams play a tournament in which every team plays every other team exactly once. No ties occur, and each team has a $1/2$ probability of winning any game it plays. Find the probability that no ...
8
votes
0answers
158 views

Distribution of $i$th largest entry in multinomial sample

I have a $k$-class multinomial distribution with vector of probabilities $(p_1, p_2, \ldots, p_k)$, from which I draw a size-$N$ sample $(c_1, c_2, \ldots, c_k), \sum\limits_{s=1}^k c_s = N$. Assume ...
8
votes
0answers
379 views

Implications of inequalities

For $i=1,2,3$, consider a random variable $Y_i$ taking value in $$ \mathcal{Y}:=\{(1,1), (1,0), (0,1), (0,0)\} $$ and a random closed set $S_i$ taking value in $\mathcal{S}$ that is the power set of $...
8
votes
0answers
196 views

What is the probability that the Golden State Warriors will break the NBA regular season record of wins?

There are $82$ games in a regular season, and the current record is held by the Chicago Bulls, at 72-10. As of yesterday (March 4th 2016), the GSW season performance stood at 55-5. Assuming they ...
8
votes
0answers
152 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: \...
8
votes
0answers
1k 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 ...
8
votes
0answers
440 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 ...
8
votes
0answers
629 views

How do Kolmogorov 0-1 law and CLT imply normalized sample mean doesn't converge in probability nor a.s.?

From WIkipedia the central limit theorem states that the sums Sn scaled by the factor $1/\sqrt{n}$ converge in distribution to a standard normal distribution. Combined with Kolmogorov's zero-...
8
votes
0answers
1k 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 that ...
7
votes
0answers
206 views

Question about random walk

Consider $X_1, X_2, X_3$ ... random variables i.i.d. such that $P(X_i=1)=p$ and $P(X_i=-1)=1-p$. Consider the random walk $(S_n)_{n\ge 0} $ with $S_0=0$ and for $n\ge 1 $, $S_n = \displaystyle\sum^{...
7
votes
0answers
72 views

The probability of rolling $N$ 10-sided dice and forming groups that add at least 10

I'm trying to answer this question for an RPG game. The player (or the GM) has to roll $N$ 10-sided dice and then she has to form groups that sum at least 10 (I'll call them Raises, using the game ...
7
votes
0answers
227 views

Ergodic process

Consider the lattice $\mathbb Z^2$ and take iid random variables $Y_e$ on all edges $e$ of the graph. We then define random variables $X_i:=\sum_{e \text{ adjacent to } i}Y_e.$ In other words: For ...
7
votes
0answers
123 views

Events A and B are independent such that $P(A)=6P(B)$

Events A and B are independent such that $P(A)=6P(B)$ and $P(A \cup B) =0.915.$ Find P(B). I know that $P(A \cup B)= P(A) + P(B) -P(A)P(B)$ Then $0.915=6P(B)+P(B)-6P(B)P(B) \\ \rightarrow 0.915=7P(...
7
votes
0answers
85 views

Master Probability course question

A point of the lattice $\mathbb{Z}^3$ in $\mathbb{R}^3$ is painted white if at least one of its coordinates is odd. An ant is moving in $\mathbb{R}^3$. At each integer time $t$ the ant is at a point ...
7
votes
0answers
139 views

Flies in a cube

Two flies sit in the corners $(1, 1, 1)$ and $(n, n, n)$ of a discrete cube $M^3$, where $M=\{1,\ldots, n\}$. After every unit of time both flies decide randomly and independently of each other ...
7
votes
0answers
364 views

Is Hoeffding's bound tight in any way?

The inequality: $$\Pr(\overline X - \mathrm{E}[\overline X] \geq t) \leq \exp \left( - \frac{2n^2t^2}{\sum_{i=1}^n (b_i - a_i)^2} \right) $$ Is this bound (or any other form of hoeffding) tight in ...
6
votes
0answers
71 views

Elementary proof that a binomial distribution with $p\ne \frac12$ is almost symmetric?

I am looking for an elementary explanation of why a loaded coin gets more and less than the expected number of heads approximately equiprobably, in other words, mean=median. Mathematically speaking, ...
6
votes
0answers
76 views

Reversal of an Autoregressive Cauchy Markov Chain

Let $\mu_0 (dx)$ be the standard one-dimensional Cauchy distribution, i.e. \begin{align} \mu_0 (dx) = \frac{1}{\pi} \frac{1}{1+x^2} dx. \end{align} Suppose I fix $\rho \in [0, 1]$, and form a Markov ...
6
votes
0answers
46 views

What applications did Laplace have in mind when he said (in 1812) that probability had become “the most important object of human knowledge”?

"It is remarkable that a science which began with the consideration of games of chance should have become the most important object of human knowledge." -- Laplace, Théorie Analytique des ...
6
votes
0answers
62 views

Expected area of a random $n$-gon

Choose $n$ points $\{z_1, \ldots, z_n\}$ from the unit circle $\partial \mathbb{D} = \{z \in \mathbb{C}: |z| = 1\}$ uniformly at random, and let $P_n$ be the convex hull of the $z_i$'s. Let $X_n = ...
6
votes
0answers
146 views

Upper Bound Lemma implies the Ergodic Theorem for Random Walks on Groups?

Cross posted on Mathoverflow Ergodic Theorem A random walk on a finite group $G$ driven by a probability $\nu\in M_p(G)$ is ergodic if $\operatorname{supp}(\nu)$ is not concentrated on a proper ...
6
votes
0answers
140 views

Supposing joint normality, is a pair of asymptotically uncorrelated sequences also asymptotically independent?

Let's say there are two sequences of random variables $(X_n, Y_n)$ and we know that For each $n$, $(X_n, Y_n)$ is normally distributed. $\mathrm{cov}(X_n, Y_n) \rightarrow 0$ as $n \rightarrow \infty$...
6
votes
0answers
79 views

$\small| U-\frac{m}{n}\small| \leq \frac{1}{n^3}$

Let $U$ be uniform distributed in $[0,1]$ . Show that with probability $1$ there's maximum a finite amount of $n \in \mathbb N$, so that the inequality $\small| U-\frac{m}{n}\small| \leq \frac{1}{n^3}...
6
votes
0answers
223 views

Poisson: Conditional Probability on Pizza order

I am not sure about my answer. In particular, part b of the following question. Pizza orders arrive according to a Poisson process of rate 20 per hour. Orders are independently for a vegetarian ...
6
votes
0answers
134 views

Probability that one part of a randomly cut equilateral triangle covers the other without flipping

At Probability that one part of a randomly cut equilateral triangle covers the other, the case with flipping allowed was quickly solved. The case without flipping seems more difficult and hasn't been ...
6
votes
0answers
130 views

Poisson Process: indepedent increment

Let $\{N(t): t\geq0\}$ be a Poisson process of rate $\lambda$, and let $S_n$ denote the time until the $n_{th}$ event occurs. compute $P(S_3>5|N(2)=1)$ Attempt: Notice that $P(S_3>5)=P(N(5)&...
6
votes
0answers
637 views

An unfair “fair game.”

This is problem 2.2.8 from Durrett's Probability Theory and Examples 4th edition, I am using the version of this book that can be found on his website. Let $p_k=\frac{1}{2^k k (k+1)}, \ k=1,2,\dots$...
6
votes
0answers
214 views

Probability of a minesweeper grid being solvable

Suppose we have an $m\times n$ minesweeper grid containing $k$ mines (for example the beginner grid is $8\times 8$ with $10$ mines). I have the following related questions: What is the probability of ...