Questions tagged [probability-theory]
Questions about the branch of mathematics concerned with modelling and analysing random phenomena.
365
questions
1
vote
0answers
30 views
How to estimate the number of elements inserted to a Bloom filter
A Bloom filter is a probabilistic data structure that allows encoding sets with false positives.
Parameterized by the number of bits $m$ in the array $A$ (initialized to zeros), and number of hash ...
1
vote
0answers
53 views
Variance of chain length in hashtable
I have a hashtable with length $m$. Initially it's empty. Next, $n/2$ unique random numbers $\in [0, n]$ are added to it.
What would be variance of chain length when such $n/2$ numbers are being ...
1
vote
0answers
198 views
Channel coding and Error probability. Where are these probabilities from?
From where are the following probabilities?
We consider BSCε with ε = 0,1 and block code C = {c1, c2} with the code words c1 = 010 and c2 = 101. On the received word y we use the decoder D = {D1,D2} ...
0
votes
0answers
9 views
How Joint Probability Distributions are used to solve the problem of missing inputs in Classification
With n input variables, we can now obtain all 2^n different classification functions needed for each possible set of missing inputs, but the computer program needs to learn only a single function ...
1
vote
1answer
31 views
Is there an efficient algorithm for determining the probability a large randomly chosen integer is not divisible by any integer of some set?
Given a set of 10 integers $A = a_1, a_2, \cdots a_{10}$, is there an efficient algorithm which can tell me what's the probability a randomly chosen integer between $1$ and $10^{10}$ is NOT divisible ...
0
votes
0answers
23 views
Fundamentals of sampling without replacement
I would like to ask a question about fundamentals that are used intuitively in
solving a simple probabilistic task about sampling with replacement. However, when I start to think about underlying ...
0
votes
1answer
121 views
Average number of inspections
Consider a set of n elements whose key values are $$0, 1, ..., n−1.$$ Let $p(i) (0 ≤ i ≤ n−1) $ be the probability that the element with key i is searched. Assume the following distribution of $p(i)’s$...
0
votes
1answer
19 views
How do I calculate the probability of a PCFG rule in a parser?
I'm quite struggling with calculating the probability of a rule for a PCFG.
I've been looking for examples online and more information, but I am none the wiser.
Here is an image of the slides. I ...
1
vote
1answer
96 views
Analyzing a randomized algorithm for finding an approximate median of an array
I'm given an array $A$ = ($a_1, a_2, \cdots a_n$), where n is uneven. For an element $a_i$ we denote its position in the array with $p(a_i)$. This element would be an $ε$-approximate median of the ...
2
votes
1answer
12 views
How to implement random sampling with continuous variables?
How functions like rnorm in R (and similar functions) create a random sample ? If I want to implement one algorithm to simulate this procedure what can I do? When you have the pdf or pmf of a ...
0
votes
1answer
26 views
Probability of data loss for mirrored,3 disk system
I am reading the book Database Systems the Complete Book 2nd Edition.
A slightly modified Question 13.4.5 states:
Suppose we use three disks as a mirrored group; i.e., all three hold
identical ...
1
vote
2answers
170 views
Probability that two elements are compared in randomized quicksort
I am having an issue in a specific part of the randomized quick-sort analysis.
As per the randomized quick-sort algorithm the pivot is chosen from the given subset on which it is called from a random ...
1
vote
1answer
29 views
Worst-case expected running time for Randomized Permutation Algorithm
I have an algorithm which, when given a positive integer N, generates a permutation of the first N integers (from 1 to N) using a method called randInt(x,y). The method randInt(x,y) will generate a ...
1
vote
1answer
59 views
Amount of expected loop iterations when searching an array by random index
Lets say we have an array A of size n. It has 1 as its first index and n as its last index. It contains a value x, with x occurring k times in A where 1<=k<=n
If we have a search algorithm like ...
0
votes
1answer
26 views
An algorithm to determine probability of one string appearing earlier than another string in an evenly distributed binary sequence
Given two binary strings of length $n$ and $m$, determine in polynomial time the probability of the first appearance of one string being earlier than the first appearance of the other one in an evenly ...
3
votes
1answer
57 views
generalizing ball-bin problem to k-universal family
I am trying to solve a question in the book on Probability and Computing by Michael Mitzenmacher, Eli Upfal. The question asks to generalize ball-bin problem for 2-universal hashing to $k$-universal ...
4
votes
2answers
934 views
Generating random words by grammar
A bit of context
I was writing a parser for a grammar, and for testing purposes I come up with idea to generate some random inputs. The grammar I was dealing with was much more complicated, in this ...
0
votes
0answers
36 views
how many parameters do we need to estimate for a general probabilistic model
Its a question from a test in machine learning.
I have 3 binary variables x1,x2 and x3 (which means that each one of them can be either 1 or 0), each one of them has a binary output y (can be 0 or 1).
...
0
votes
1answer
43 views
Expected number of coins
Alice and bob play a game.
Bob has a well-shuffled deck of $M=4999$ white cards and $N=4999$ green cards. Each permutation of cards in the deck is equally likely. Alice has set some rules for Bob.
...
1
vote
0answers
43 views
Calculate probability in graphical model
I have the following graphical model, in which I wish to compute $p(Intelligence = 1|Letter = 1, SAT = 1)$
But I'm not sure how to rewrite $p(Intelligence = 1|Letter = 1, SAT = 1)$? I was told to ...
1
vote
0answers
42 views
Decomposition of Mutual Information
I came across a book where the author uses the following property of mutual information:
Let $X$,$Y$,$Z$ be arbitrary discrete random variables and let $W$ be an indicator random variable.
$$
(1)\ \ ...
0
votes
1answer
37 views
Reservoir Sampling vs Round Robin
You are given a List of numbers (length unknown).
Let's say the length is 10.
GetRandom(List) is called once. If implemented correctly, each number has 1/10 probability of being returned.
GetRandom(...
1
vote
1answer
13 views
Why there is no polynomially large sequence of polynomial large weights that derandomize the isolation lemma?
I was studying the paper Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size by Arvind and Mukhopadhyay and came across the following claim (Observation 1.2 on page 3):
"More ...
1
vote
1answer
13 views
Probability of selecting a particular set, by sampling without replacement from a categorical distribution
Suppose I have a categorical distribution on items $1,\dots,n$, that assigns probability $p_i$ to item $i$. I now repeatedly sample from this distribution, until I have obtained $k$ unique objects. ...
-1
votes
1answer
31 views
From a randomized algorithm with expected time $O(n)$ to a reliable with determined running time
Let $A$ be a randomised algorithm and $F$ be a function such that $A$ returns $F(x)$ on any input $x$. Furthermore suppose that, for input $x$ of size $n$, the $\textbf{expected}$ running time of $A$ ...
3
votes
0answers
40 views
Node depth in randomly built binary search tree
It can be proved that randomly built binary search trees of size $n$ are of depth $O(\log n)$ and it is clear that level $k$ has at most $2^{k}$ nodes (root's level is 0).
I have an algorithm that ...
2
votes
1answer
44 views
Probability of terminating in a state in a probabilistic algorithm
Suppose i have a circular array of $n$ elements.
At time $t=0$ i am in position 0 of the array. The algorithm moves left or right with probability $p=1/2$ (since the array is circular when it moves ...
1
vote
1answer
42 views
What kind of bigram probability smoothing is this?
I hope it isn't off topic but I need to understand this example. Given the corpus 12 1 13 12 15 234 2526 and smoothing factor of ...
2
votes
1answer
30 views
Demonstrating that probability for every possible result is uniform at the end of an algorithm
I have memory of $k$ elements that you can imagine being represented by an array. One by one, the array receives a value corresponding to the time index, for example at $t=1$ the value will be $1$.
At ...
2
votes
1answer
37 views
If I walk through list and delete every out-of-order element I come across, on average how many elements will be left?
I have a uniformly randomly permuted list of length $n$. I walk through the list element-by-element, and delete an element if it's out-of-order (compared to the previous in-order elements of the list)....
6
votes
0answers
146 views
Correctness of a greedy Algorithm on Knockout Tournaments
You are given a function $\operatorname{rk}:\{1\dots 2^k\}\rightarrow \mathbb{N^+}$ representing the ranks of the players $1\dots2^k$ in a participating in a tournament. The tournament evolves in a ...
0
votes
0answers
11 views
Synthesis of the crisp programs from the Bayesian (probabilistic) programs?
https://arxiv.org/abs/2001.00805 is the article which is pointing towards the direction that the optimal policy of the reinforcement learning can be expressed as the Bayesian/probabilistic program (...
0
votes
0answers
55 views
apply the method of conditional expectations
For a Randomized vertex cover problem
Why there is not much hope of deriving an efficient, deterministic
version using the method of conditional expectation?
I can assume the problem is not ...
3
votes
1answer
507 views
Expected length of a random walk on a line
I am given the following randomized algorithm for SAT,
Input: A satisfiable CNF-formula $\varphi$.
Output: An assignment $\rho$, such that $\rho \models \varphi$.
The algorithm works as follow:
...
8
votes
0answers
117 views
Compute the expected size of an approximation of vertex cover
Consider the following randomized approximation algorithm of vertex cover:
Input: A graph G = (V, E).
Output: A set $C_G \subseteq V$ a vertex cover of $G$.
The algorithm:
Set $C_G := \emptyset$.
...
0
votes
0answers
39 views
Expected number of retransmissions for a packet
In a communication link out of p packets one packet will be lost. If stop and wait protocol is used then expected number of retransmissions for a packet?
(A) P/(1-P)
(B) P
(C) 1/(1-P)
(D) 1/P
...
3
votes
1answer
33 views
Given an unsorted list of $n$ items, how many random comparisons are needed on average to be able to sort the list?
There is an unsorted list of $n$ items $x_1, \ldots, x_n$. Until you can sort the list, you are given one of the ${n \choose 2}$ possible binary comparisons uniformly at random (with replacement).
On ...
0
votes
1answer
53 views
Probability of detecting errors in codewords
I have been struggling with the below question for quite some time, and I don't have a pointer to move forward.
A certain Error Control Coding scheme using block codes takes an input block (...
3
votes
0answers
52 views
Probability of colisson for classes of hash functions
I am going through some old exams in one of my courses, and I don't have access to solutions. I've found a problem which I am not sure how to tackle. I am not looking for the answer but some help/...
0
votes
0answers
8 views
Contingency Table Confusion NLP
Hello for the contingency table: [true positive, false negative, false positive, true negative]. I am having a hard time remembering the difference between these terms because all the terms are ...
3
votes
2answers
78 views
In information theory, why is the entropy measured in units of bits?
In information theory, we have the quantity "information".
Suppose we have some discrete random variable $X$, that can take values $\{{a,b,c\}}$ with corresponding probability distribution $\{{\frac{...
1
vote
2answers
69 views
Bayes theorem probaility doesn't make sense
I try to use Bayes Theorem to calculate the probability of $P(A|B)$. I have $P(A)$ in column1, $P(B|A)$ in colmn2, $P(B)$ in column 3. I get the following:
my calculations were:
$$P(B/A) = 0.8\times ...
0
votes
0answers
28 views
Is FOL representation of probabilistic assignment statement correct?
For instance, $x = x + 1[0.3]x+2$ sets $x$ to $x + 1$ with probability $0.3$ and to $x+2$ with probability $0.7$.
If I use notation used in the paper "An Analysis of First-Order Logics of Probability"...
4
votes
0answers
47 views
Understanding simulated annealing information theoretically
So I recently rediscovered simulated annealing though a path that others seem to be well aware of. I was aware of Metropolis-Hastings as a sampling algorithm that creates a Markov-Chain who's ...
1
vote
0answers
50 views
Probability of string misidentified in Bloom filter
I'm attempting a question related to Bloom filters:
Our Bloom filter uses $3$ different independent hash functions $H_1, H_2, H_3$ that each take any string as input and each return an index into a ...
2
votes
1answer
165 views
Calculating probability of reaching state in DTMC
Consider a highly-connected graph of states & transitions where each transition is marked with a weight (representing probability of occurring) and the graph satisfies the Discrete Time Markov ...
2
votes
1answer
81 views
Does this shuffle have non-zero probability for all permutations?
I was trying to do some code golf, when I created the following algorithm to shuffle a string:
...
2
votes
1answer
44 views
What is the density of a regular language $L$ over an alphabet $\Sigma$ in $\Sigma^n$?
In other words, what is the likelihood that a recognizer of a given regular language will accept a
random string of length $n$?
If there is only a single non-terminal $A$, then there are only ...
2
votes
0answers
28 views
The No-Free-Lunch Theorem and K-NN consistency
In computational learning, The NFL theorem states that there is no universal learner. For every learning algorithm , there is a distribution that causes the learner to output a hypotesis with a large ...
0
votes
0answers
17 views
Algorithmic question: distribute balls, optimise for balancing (i) weights (ii) probabilities of picking balls
I have an algorithmic problem that requires some lengthy explanation, which follows below.
tl;dr: distribute balls with weights among bags, optimise for balancing both (i) the weights between the ...
