# Questions tagged [probability-theory]

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

343 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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 ...
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 ...
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 > ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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: ...
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 ...
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 ...
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'...
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 ...
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 ...
56 views

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 ...
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$...
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 ...
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 ...