Questions tagged [probability-theory]
Questions about the branch of mathematics concerned with modelling and analysing random phenomena.
352
questions
0
votes
1answer
36 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
37 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 ...
-2
votes
0answers
12 views
probability of error for a Bayesian classifier with P(x | c 1 ) = P(x | c 2 ) and P(c 1 ) = P(c 2 )
What is the probability of error for a Bayesian classifier with P(x | c 1 ) = P(x | c 2 ) and P(c 1 ) = P(c 2 )? Why? Does this make sense? if so, can anyone explain this clearly?
1
vote
0answers
41 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
36 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
10 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
12 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. ...
-2
votes
0answers
45 views
Expected Length of string
Consider a string of length N which contains up to K distinct characters. The compression algorithm works as follows: Replace each maximal contiguous substring containing only one distinct character (...
-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
35 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
40 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
36 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
28 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
35 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
142 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
54 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
429 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
111 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
25 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
26 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
45 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
51 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
54 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
63 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
44 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
33 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
143 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
79 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
35 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
23 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
15 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 ...
3
votes
1answer
78 views
Efficient algorithm to simulate dealing cards from a large deck of cards?
In shedding-type card games, the dealer starts by dealing a shuffled deck of cards to the players (if there are N players, card i...
0
votes
1answer
55 views
information theory, find entropy given Markov chain
There is an information source on the information source alphabet $A = \{a, b, c\}$ represented by the state transition diagram below:
a) The random variable representing the $i$-th output from this ...
4
votes
0answers
61 views
Peculiar MCMC sampling problem
I have two random variables, X and Y, and Y is a positive real number. I can sample from $p(y|x)$, but I need to sample from $p(x)$, which I know to be proportional to $\frac 1 {E[y|x]}$. I could ...
2
votes
2answers
114 views
Randomly built binary search trees
In Introduction to Algorithms (CLRS) 3rd Edition, page 299, the section attempts to prove:
The expected height of a randomly built binary search tree on $n$ distinct keys is $O(\lg n)$.
We define "...
2
votes
1answer
94 views
Introduction to Algorithms (CLRS) Ex 5.2-5 solution
The following is Ex 5.2-5 from Introduction to Algorithms (CLRS), 2nd Edition.
Let $A[1...n]$ be an array of n distinct numbers. If $i<j$ and $A[i]>A[j]$, then the pair $(i, j)$ is called an ...
1
vote
1answer
80 views
Calculate probabilty to escape the maze
I am trying to solve the problem to calculate probability to escape the maze and stuck at one use case. Here is the problem statement
The Frog is in an two-dimensional maze represented as a table.
...
2
votes
0answers
27 views
Correctness of Karger's min-cut Algorithm
tl;dr in the analysis for Karger's min-cut, the probability of an edge being in the min-cut in the $j$th iteration, $\frac{k}{0.5k(n-j)}$, neglects the fact that all the edges between the two ...
0
votes
0answers
33 views
Construction of hash function with a given distribution
Two questions about the construction of a hash function:
Let $U = \{u_1,...,u_n\}$ be a set of size $n$, and suppose that one is interested in a function $h\colon U \rightarrow [0,1]$ such that $h$ "...
1
vote
2answers
63 views
Quicksort where element comparison outcome is random. Probability of element being in a certain position
So we have this block of pseudocode:
Monsters = [M1,M2,M3,M4,M5,M6,M7,M8];
qsort(Monsters,rand_compare);
qsort() sorts the ...
4
votes
1answer
44 views
How to approach analysis of randomized algorithm
Let us suppose we have a sequence of values $C(i)$ that represent some counter for a given $i$ for $i \in \lbrace 1, \cdots, n \rbrace$. Let us assume some uniform distribution $U$ where selecting any ...
0
votes
0answers
26 views
Interpretation of statement over probability distributions and functions
Consider the following paragraph from this research paper:
To learn the generator’s distribution $p_g$ over data $x$, we define a prior on input noise variables $p_z(z)$, then represent a mapping ...
1
vote
1answer
32 views
Prior probability in HMM
This is the HMM model considered in the question
And this is the emission probabilities for the respective states. There are two emission values, bringing an umbrella and not bringing an umbrella.
...
4
votes
1answer
58 views
Using Chebyshev to derive an upper bound for Coupon Collecter's Problem
I'm TA'ing a course and have trouble solving an exercise.
Let $X$ be a RV defined to be the number of trials required to collect at least one of each type of coupon (of which there are $n$). Then $E[...
2
votes
1answer
32 views
Data points as outcomes of a random experiment
It is well known that
Random variable is a function from sample space of a random experiment to $\mathbb{R}$.
Consider the following sentences from deep learning book
Let $\{x^{(1)}, \cdots , x^{...
4
votes
1answer
68 views
Prove the probability of which a hash function is collision-free
Suppose $H = \{h_1, ..., h_T\}$ be a family of pairwise independent hash functions mapping $\{0, 1\}^n$ to $\{0, 1\}^{n/2}$. Let $M = \frac{2^{n/4}}{10}$ and let $x_1, ..., x_M$ be any M distinct ...
1
vote
1answer
77 views
Constructing hitting sets for randomized algorithms
Suppose A($\cdot$,$\cdot$) is an efficient randomized algorithm and L is a language such that
$\text{If }x \in L, \text{Pr}_r[(A(x,r) = 1)] = 1$ and if $x \notin L, \text{Pr}_r[A(x, r) = 0] \ge \...
