Questions tagged [probability-theory]
Questions about the branch of mathematics concerned with modelling and analysing random phenomena.
320
questions
5
votes
0answers
74 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
20 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
10 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
71 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
46 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
58 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
31 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
43 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
52 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
18 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
30 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
44 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
41 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
27 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.
...
3
votes
1answer
52 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
62 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
63 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
37 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
60 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
112 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
63 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
72 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
28 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
52 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
55 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
30 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
41 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
69 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
28 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 ...
2
votes
0answers
47 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
36 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 ...
2
votes
1answer
34 views
HyperLogLog leading zeros distribution
I'm reading this article.
In particular I'm having some trouble trying to replicate the results of the first image in that article.
For x=9, the graph says that the probability is 0.20 aprox. But ...
1
vote
1answer
22 views
Expectation of $\langle s,x \rangle^2$
I'm studying dimensionality reduction (SVD in particular), and I saw the following question:
Assume we have a vector $x \in \mathbb R^d$, and consider $F(x)=s^t x$ , where
$s$ is a $d$-...
0
votes
2answers
94 views
probability of collision
my data's range is from 1 to 9 and I have two subsets of integers from this range.
the hash function takes each of this subsets and calculate product of these three integers and maps this set to the ...
1
vote
1answer
9 views
Is there a term for the distribution of numbers-of-digits of a bounded uniform distribution
Let $X$ be an integer sampled uniformly from the (integer) range $\{ 0...2^k - 1 \}$ .
Now, consider the distribution of
$\#\text{bits}(X) = \begin{cases} 1 & X = 0 \\\\ 1 + \lfloor \log_2(X) \...
1
vote
1answer
42 views
How can I minimize floating point error when multiplying normal distribution PDFs?
If you multiply two normal distribution PDFs with means $\mu_1$ and $\mu_2$ and variances $v_1$ and $v_2$, then according to this page, the new mean is
$$\mu = \frac{\mu_1 v_2 + \mu_2 v_1}{v_1 + v_2}$...
1
vote
1answer
16 views
Confusion About Min-Cut Probabilities
Currently going through a video on Counting Minimum Cuts by Tim Roughgarden.
$(A_{i},B_{i}) = \big((A_{1},B_{1}), ..., (A_{t},B_{t})\big) \forall i \in \Bbb{R}$
$P\big((A_{i},B_{i})\big) \geq \frac{1}{...
3
votes
1answer
205 views
expected pairwise square euclidean distance between points
How can I show that the expected pairwise square euclidean distance between points in $X$ is $Θ(d)$?
Where $X$ is a $(x_1,...x_n)$ of points generated uniformly at random in the unit, d is d-...
1
vote
1answer
16 views
How many prefix code we can find for a given distribution of probability?
A source emits 5 signals s1, s2, s3, s4 and s5 whose probabilities are as follows: 1/3, 1/3, 1/9, 1/9, 1/9, 1/9. How many prefix codes we can construct on A={a, b, c}? And how many are there with the ...
1
vote
1answer
100 views
Is the bitwise-xor of a Uniform bit string and a non_uniform bit string Uniform?
Having two bit strings $x,y \in \left\{0,1\right\}^n$, where $x$ is selected following a uniform distribution but $y$ is not.
Is $z = x \oplus y$ uniform?
3
votes
1answer
17 views
Variance of MAXSAT clause satisfiability
For a given MAXSAT problem, it is trivially easy to compute the mean number of clauses satisfied for all assignments, or equivalently the expected number of clauses satisfied by a random assignment.
...
0
votes
1answer
21 views
What is the relation between the quantity of information of $A_i$ and $A$, where $A=\bigcup_iA_i$?
Let $A$ be an event divided into 4 events $A_i$ with the same probability. Why does the quantity of information of $A_i$ satisfy
$$ I(A_i) = I(A) + \log (4)?$$
