Questions tagged [probability-theory]

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

Filter by
Sorted by
Tagged with
5
votes
1answer
1k views

Reservoir sampling algorithm probability

I'm reading about the reservoir sampling technique called Algorithm R. The idea is we can take a sample of size $n$ from a population of size $N$ even when $N$ is unknown/too expensive to retrieve in ...
0
votes
1answer
140 views

Trying to understand CLRS bucket sort analysis

I'm trying to understand the analysis of bucket sort in CLRS. Specifically, equation 8.2 that states: $$ E[{n_i^2}] = 2 - \frac{1}{n} $$ To prove, CLRS: Random variable denoting number of elements ...
0
votes
1answer
156 views

Expected number of vertices with degree 2

A simple graph with $n$ vertices is constructed by randomly and independently placing an edge between every two vertices with probability $p$. What is the expected number of nodes with degree two? I ...
2
votes
1answer
260 views

Viterbi Algorithm: initial state with ONE probability

The Viterbi Algorithm can be used to calculate the most likely path, based on observations in a Hidden Markov Model. Using the same notations as Wikipedia, "each element ...
2
votes
1answer
375 views

Probability of k-clique in a random graph

I need to find the order of the minimum k = k(n) such that the probability of having at least 1 k-clique in a random graph $G(n, \frac{1}{2}$) is $\mathcal{O}(\frac{1}{n})$. $X_k$ is the random ...
3
votes
2answers
553 views

how to bound the probability that quicksort takes greater than n lg n time?

I am working on exercise 12.4-5 of CLRS (Cormen et al, Intro to Algorithms 3rd ed) Consider RANDOMIZED-QUICKSORT operating on a sequence of n distinct input numbers. Prove that for any constant k > ...
3
votes
1answer
313 views

How to estimate how many assignments satisfy a given DNF formula using Monte Carlo?

Admittedly, homework. For the purpose of this question: $\phi$ is a DNF formula similar to this one: $(x_1 \wedge \neg x_3 \wedge x_4) \vee (\neg x_1 \wedge x_2)$ Also $C_i$ is a clause in this ...
6
votes
1answer
2k views

Why are forks in the Blockchain eventually resolved?

I'm reading Wattenhofer's The Science of the Blockchain. On page 87, he states the following thoerem: Theorem 7.22. Forks are eventually resolved and all nodes eventually agree on which is the ...
3
votes
1answer
33 views

Polynomial Computation of the probability of a number of independent events

Suppose to have $n$ independent events $E_1, E_2,..., E_n$, where the probability of occurrence of event $E_i$ is $p_i$ (i.e., each event has its own probability of occurrence). We can easily define ...
2
votes
0answers
180 views

How do I do a biased shuffling of a deck of cards?

I currently have a deck of cards (in fact this deck is an array of sorted elements in descending order as indicated by the picture above), that I want to shuffle. However, the caveat is that I want ...
0
votes
0answers
84 views

Average solutions in infinite search tree

I have the following problem: Consider a balanced infinite search tree with branching number $κ$. Consider a search problem with solutions which may be located at any node of the tree. The ...
0
votes
0answers
52 views

How are Probability and Non Determinism Related ? Alternatives to handle Non determinism?

I have been thinking about Non-determinism in any kind of state machine. Since I work on machine learning, I tend to think that probability is a means of handling non-determinism. Instead of ...
2
votes
0answers
30 views

Why can optimality be preserved when inserting a new conjunct into an optimally ordered conjunction of conditions? [duplicate]

In a programming language with short-circuiting, a conjunction of N independent conditions has the following expected cost: where: ...
2
votes
2answers
154 views

The optimal way to reverse engineer a binary classification problem

I am not sure if this question is more suitable for CS, theoretical CS or math so feel free to improve the description and migrate it. In a scenario very similar to popular binary classification ...
1
vote
0answers
376 views

How to choose value of additive smoothing in naive Bayes and why a higher value gives bad accuracy?

In Naive Bayes we often do additive smoothing as a fail safe. Consider the following expression: Lets say $$P(X_i) = \frac{count(X_i) + \alpha}{\sum_i^n count(X_i) + \alpha*total\_size}$$ How to tune ...
1
vote
0answers
59 views

Game with Random Digits (Markov Chain / Coupling)

I've been self-studying Markov Chains and came across a problem online here: http://websites.math.leidenuniv.nl/probability/lecturenotes/CouplingLectures.pdf I'm not asking for anything too formal (I'...
2
votes
1answer
108 views

Confuse on using bucket number to replace hashing multiple times in hyperloglog explanation

In this blog the author states that the following So we now have a rather poor estimate of the number of values in the dataset based on bit patterns. How can we improve on it? One ...
0
votes
0answers
123 views

Probability in Dynamic frame aloha

If I've RFID Collision Arbitration System that is based on multi-frame dynamic frame ALOHA. How can compute the probability of the average tag resolution $L_n$? ,$P_s$ is probability for packet ...
3
votes
2answers
56 views

Are typical sets larger, when information is messier?

Let $0\le q<p\le \frac{1}{2}$, and let $P,Q$ be two Bernoulli Random Variables such that: $$Pr[P=1]=p ; Pr[P=0]=1-p$$ and $$Pr[Q=1]=q ; Pr[Q=0]=1-q$$ My question: Does it follow that, for any $\...
3
votes
1answer
153 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 ...
1
vote
1answer
50 views

Probabilistic analysis of finding 2nd largest value in vector

Given the following algorithm for finding the second largest element in a vector: ...
0
votes
1answer
282 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 ...
2
votes
1answer
71 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 ...
0
votes
0answers
30 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 ...
2
votes
1answer
52 views

Bound covariance of two discrete random variables

Let $X,Y$ be two random variables over a discrete probability space, such that $X \in [0,1]$ and $Y \in [0,1]$. I want to prove that $$ |\text{Cov}[X,Y]| \leq \sqrt{0.5 \; I[X,Y]}$$ where $I[]$ is ...
4
votes
1answer
88 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 ...
1
vote
1answer
154 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 ...
0
votes
0answers
127 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)?
0
votes
1answer
103 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. ...
21
votes
2answers
5k 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 ...
1
vote
1answer
59 views

Estimating probability from generative model

Assume that we have access to a generative model $G$, that takes as input a state-action pair $(s,a)$ and outputs a sample consisting of a successor state-observation pair $(s',o)$, that is, $(s',o)\...
2
votes
0answers
111 views

What would be the probabilty of a randomly generated tree to be a Red-Black Tree

The question is not related to the homework I was working on a homework, and the specification was to generate a random tree with n elements(n being in the thousands for the assignment) and asked me ...
1
vote
1answer
220 views

Vertical sticks challenge explanation

This is a question based on this one I've also tried this problem but I can't seem to understand Henry's solution to it. Why is the average distance between the sticks $(n+1) / (k+1)$ and not $n/ k$...
1
vote
1answer
64 views

Can we recognize the difference of two strings of $2^n$ length using polynomial size strings?

Is it possible to transform binary strings of length $2^n$ to $n^c$ binary strings of sized $n^d$ such that $$\forall s_1,s_2 \; \exists i \in \{1,\cdots,n^c\} \; f_i(s_1)\neq f_i(s_2),$$ Where two ...
1
vote
0answers
111 views

Probability of finding the maximum element in a heap

You are given a minimum heap, with probability going to left is 50% and going to right is 50%. What is the probability that You will land up on a maximum element in the heap? For this scenario since ...
1
vote
1answer
172 views

Higher order empirical entropy is not the entropy of the empirical distribution?

Basically, the problem is that I always thought that the (unnormalized) $k$th order empirical entropy $n\cdot H_k(x)$ (see "Backround" at the end of this post for more information) for a given string $...
0
votes
1answer
45 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 ...
1
vote
1answer
54 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 ...
1
vote
0answers
23 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 ...
0
votes
1answer
226 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 ...
0
votes
0answers
47 views

What is the probability distribution of arrival times in a distributed system?

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 ...
2
votes
2answers
914 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 ...
3
votes
1answer
107 views

Finding the dichotomy that maximizes information gain for a classifier?

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) = ...
1
vote
1answer
54 views

Expected Number of Trials

I have an algorithm problem that I want to share with you and I want to get some idea how can I solve it. Problem statement: You have to reach th Nth floor of a building by using a particular ...
3
votes
1answer
54 views

Hidden Markov Model initial probability reestimate: Why $\pi^*_i = \gamma_i(1)$ instead of $\pi^*_i = \frac{\gamma_i(1)}{\sum_{j = 1}^N \gamma_j(1)}$

In the sources I consulted it states that in the Baum Welch algorithm the reestimate of the initial probability of state $i$ of the HMM is $\pi^*_i = \gamma_i(1)$. But $\gamma_i(t)$ is the probability ...
1
vote
1answer
60 views

Most probable value of randomized procedure output

Let $n, m \in \mathbb{N}^{+}$. Let $\mathsf{rand}$ be a procedure which returns some random $x \in \{0, 1, \ldots, m - 1\}$ with a flat probability distribution. I have the following procedure: ...
-1
votes
1answer
179 views

Help in understanding calculation of hash collision from a document

UPDATE In an earlier question of mine asked here : https://math.stackexchange.com/questions/2206095/beginner-level-understanding-concept-on-how-to-derive-probability-of-hash-collis , I got the answer ...
2
votes
3answers
175 views

Confusion about the definition of the average-case running time of algorithms

In this lecture note, The average-case running time is defined by the expected value, over all inputs $X$ of a certain size, of the algorithm's running time for $X$: $$T_{\text{average-case}}(n) ...
0
votes
1answer
156 views

Reachability queries on uncertain graphs

We have an uncertain graph $G$ where each edge $(u,v)$ exists with a probability $p_{(u,v)} \in (0, 1]$. We want to assign a score in $[0, 1]$ to each pair of vertices $u$ and $v$ which represents the ...
1
vote
0answers
22 views

How to derive an algorithms that generates check sums [closed]

Column S contains the check sums of the values given in columns R and Xc. Does anyone here have an idea about how to find the corresponding algorithm to calculate the check sums? Thanks in advance <...