Questions tagged [probability-theory]
Questions about the branch of mathematics concerned with modelling and analysing random phenomena.
331
questions
0
votes
1answer
38 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 (...
2
votes
0answers
26 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
6 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
41 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
58 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
24 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
40 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
24 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
121 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
72 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
33 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 ...
5
votes
0answers
78 views
Is resampling random variables to maximize value NP-hard?
Setup Let $S = {X_1, ..., X_n}$ be a set of independent binary random variable, i.e. $X_i \in \{0, 1\}$, each with prior $P(X_i = 1) = p_i$. The $X_i$ are not iid, so $p_i, p_j$ need not be equal if $...
2
votes
0answers
22 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
13 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
77 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
48 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
60 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
63 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
86 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
67 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
25 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
59 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
42 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
25 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
29 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
55 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
64 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
70 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 \...
0
votes
1answer
17 views
Assumption of a generation of the dataset by a probability distribution
Consider the following paragraph from the deeplearningbook
The training and test data are generated by a probability distribution
over datasets called the data-generating process. We typically ...
3
votes
1answer
50 views
The expectation of the total number of pairs of keys in a hash table that collide using universal hashing
I am reading CLRS relating to perfect hashing. When computing the
$$
\mathbb{E}[\sum_{j=0}^{m-1}{n_j\choose{2}}]
$$
where $m$ is the number of slots in the hash table, and $n_j$ is the number of keys ...
0
votes
0answers
30 views
Question on preventing k from reducing too quickly during KMV intersection
This question considers KMV, an algorithm that is able to estimate the cardinality (unique item) from a stream of data.
The way it does it is to first map the stream of data to a space that almost ...
2
votes
1answer
61 views
How do we prove the time complexity of this simple problem in probabilistic inference on a Bayesian network?
Suppose we have a simple Bayesian network with two rows of nodes: $x_1, x_2, \ldots, x_n$ and $y_1, y_2, \ldots, y_n$. Each node $x_k$ takes a state of either 0 or 1 with equal probability. Each ...
0
votes
0answers
44 views
Derive the expected # of steps that are taken to perform all the operations (n operations) [duplicate]
Consider a datatype whose objects will be sequences of elements that has the following two methods
prepend($x, T$) which will insert an element to x to the beginning of the sequence T
search($T, i$) ...
1
vote
1answer
122 views
Deriving the expected number of steps that is taken to perform the k'th operation
Consider a datatype whose objects will be sequences of elements that has the following two methods
prepend($x, T$) which will insert an element to x to the beginning of the sequence T
search($T, i$) ...
2
votes
2answers
95 views
expected length of linked list
Consider a datatype whose objects will be sequences of elements that has the following two methods
prepend($x, T$) which will insert an element to x to the beginning of the sequence T
search($T, i$) ...
2
votes
1answer
21 views
How do you marginalize in graphical model elimination?
I'm reading Michael I. Jordan's book on probabilistic graphical models, and I don't understand the elimination algorithm presented in chapter 3. To narrow the question down, consider page 6. In ...
0
votes
1answer
102 views
Hitting probability of random walk within given number of steps
Given m,n dimensions of a 2D matrix; (i,j) initial co-ordinates; (x,y) final co-ordinates.
What is the probability of being at (x,y) after at most k steps if we start from (i,j) initially?
We can ...
2
votes
1answer
79 views
Network throughput with random delay selected from uniform distribution
Background:
I am working with IoT devices which broadcast status messages over a wireless channel periodically and at a rather high rate (500-5000 Hz). Receiving every message is not crucial but the ...
0
votes
0answers
34 views
Probability in 1-universal hash function
I am trying to prepare for an exam and I am not sure how to solve this task:
Given is a hash function with m buckets, which uses a 1-universal hash function h: U -> H and handles collisions with ...
3
votes
1answer
57 views
Sampling numbers from a weighted set that sum to constant value
So I have a multi-set of positive integers $S = \{n_1, n_2, \dots\}$ with associated weights $W = \{w_1, w_2, \dots\}$. I want to sample some numbers, without replacement, from $S$ according to ...
2
votes
1answer
66 views
Bertrand's ballot theorem
I want to understand the dynamic programming equation of https://en.wikipedia.org/wiki/Bertrand%27s_ballot_theorem theorem.
it is this
If i number of people voted for A and j number of people voted ...
2
votes
1answer
32 views
Complexity/Hardness of a generalization of an Inclusion/Exclusion problem
I would appreciate some help in determining the complexity/hardness of an inclusion/exclusion problem described in Wikipedia: https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle#...
1
vote
0answers
44 views
How to generate a random number in a given range with uniform probability [closed]
I have used programming languages which generate a random number in a given range.
Let's say we have a range of 1 to 10 each number has the probability of 1/10 to get selected. What is the criteria ...
1
vote
1answer
89 views
Proof of an Infinite Binary Sequence
I have a problem where given an infinite binary sequence S ∈ {0, 1}∞ to be "prefix-repetitive" if there are infinitely many strings w ∈ {0, 1}*
such that ww is a prefix of S.
I need to prove that if ...
1
vote
0answers
31 views
Probability lower bound on a double cycle on two vertices in random cuckoo graph
I have read Chater 17. Balanced Allocations and
Cuckoo Hashing in Mitzenmacher. Upfal. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis and got ...
3
votes
0answers
52 views
Probability of a double cycle in cuckoo graph
I have read Chater 17. Balanced Allocations and
Cuckoo Hashing in Mitzenmacher. Upfal. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis and got ...
1
vote
1answer
37 views
Expectation for the number of leaf nodes in a randomized tree construction
Consider this procedure for building a tree from $v_1, v_2, ..., v_n$:
insert $v_1$
insert $v_2$ and connect it to $v_1$ via a directional edge from $v_2$ to $v_1$
insert $v_3$ and with a uniform ...
1
vote
1answer
30 views
Expectation of $u'^t v$ = $u^t v$
I have another question with dimensionality reduction.
I have a matrix $S \in R^{k \times d}$ and S is in {$- \frac{1}{\sqrt k}, \frac{1}{\sqrt k}$} and i have two vector $u,v \in R^d $.
I need to ...
