# Questions tagged [probability-theory]

Questions about the branch of mathematics concerned with modelling and analysing random phenomena.

434 questions
Filter by
Sorted by
Tagged with
66 views

### Why does the distribution of pseudorandom numbers change when operating like this?

We were introduced to the standard C rand() function, and how to use it. At some point during the class we were asked how to roll a die. The simple answer was to ...
41 views

78 views

### Probabilistic analysis of finding 2nd largest value in vector

Given the following algorithm for finding the second largest element in a vector: ...
206 views

### Probability of k-connectedness for a random graph with given degree sequence

For a degree sequence $(d_1,\ldots, d_n)$ with $\min d_i \geq k$ pick a graph with that degree sequence uniformly at random. What's the probability that the graph is k-connected? I know that for ...
113 views

### Randomized BST height analysis : How $Z_{n,i}$ and $Y_{k-1}$ are independent?

I am referring to this video https://www.youtube.com/watch?v=vgELyZ9LXX4 at 1:08:39 . $n$ : number of nodes in the tree $Z_{n,k}$ : Indicator random variable that activates when rank of the root ...
395 views

### Equivalence of machine $M$ in $BPP$ and $EXP$

Ok, the proof is clear. But, if we prove that $BPP \subseteq EXP$ we should show that for every machin in $BPP$ there exists equivalent machine in $EXP$. I cannot see how the $EXP$-machine is ...
400 views

### Choosing a subset of binary variables to maximize the sum of the highest $K$

Consider the following problem: Input: integers $n > m > k$; $n$ numbers $0 \leq p_1, \ldots, p_n \leq 1$; $n$ numbers $r_1, \ldots, r_n$ where ($r_i \geq 0$). Let $X_1,\dots,X_n$ be $n$ ...
37 views

### Probability that the word is of language using N-Grams

Some programm should allow users to identify the word language probability. All i have is some statistics - the frequency of using bigrams and ...
2k views

### Does there exist any work on creating a Real Number/Probability Theory Framework in COQ?

COQ is an interactive theorem prover that uses the calculus of inductive constructions, i.e. it relies heavily on inductive types. Using those, discrete structures like natural numbers, rational ...
138 views

### Chernoff bound when we only have a lower bound of expecation

This question: Chernoff bound when we only have upper bound of expectation is similar, but for an upper bound of expectation. The standard Chernoff bound says that is $X$ is a sum of 0/1 random ...
206 views

### Probability that all indices divisible by 100 in a hash table with linear probing are occupied

I am trying to solve this question on Sedgewick's and Wayne's Algorithms book: Suppose that a linear-probing table of size 10^6 is half full, with occupied positions chosen at random. Estimate the ...
182 views

### Finding the expected total number of comparison for a Randomized Quick Sort

Let A = {2, 8, 11, 3, 12, 7, 10, 4, 15} Want to find $E_4$. Little unsure how to do this question. Would this be similar to finding the probability of the number of comparison 2/(j -i +1)?
133 views

### Limit on table size - perfect hashing

Let us define a "root universal family" as a family of hash function which for every two items $k_i,k_j$ the probability $P(h(k_i)=h(k_j)) \le \frac{1}{\sqrt m}$ where $m$ is the size of the table. ...
8k views

### Why is adding log probabilities faster than multiplying probabilities?

To frame the question, in computer science often we want to calculate the product of several probabilities: P(A,B,C) = P(A) * P(B) * P(C) The simplest approach ...
63 views

59 views

### Prove a language $A_{PTM}$ is not BPP-Complete

I am trying to prove that there are a language is not BPP-Complete. There are a couple of examples online, but they are not the best examples and are a bit complicated. I spoke with one of my computer ...
126 views

### Using amplification lemma to decrease error probability gives 0 as divisor

I am attempting to work through an example of how to select an error bound, and then determine the number of simulations necessary by the amplification lemma to obtain the desired error bound. I have ...
24 views

### Minimizing $E_{out}$ theoretically in linear regression

Related to linear regression with noise I've been given the following functional, depending on the function $h$: $$E_{out}(h) = \int \int (h(x)-y)^2 dx dy$$ I want to prove that the function that ...
307 views

### Calculate joint entropy of a Hamming Code over a Binary Symmetric Channel?

I have a normal (7,4,3) Hamming Code over GF(2) and a parity check matrix for it (not posted, because I don't think it's involved). I have a set X of 4 bit source vectors called x. They all have ...
2k views

### Sorting in a probabilistic order

Given a list of real numbers $p_1, \dots, p_n$, I am looking for a most efficient algorithm to sort this list in a "probabilistic ascending order", meaning that $p_i < p_j$ implies that it is ...
Suppose that $\Omega$ is a finite probability space,with measure $P$ (we can take $P$ uniform). Let $C \in \{\pm 1 \}$ be a random variable on $\Omega$, the classifier. Let H(C) = H(C, \Omega, P) = ...
I'm going to simulate an asynchronous distributed system. In a distributed system, when a node sends a message, after $\Delta t$ seconds the message reaches to its destination. My Question: What is ...