Questions tagged [probability-theory]
Questions about the branch of mathematics concerned with modelling and analysing random phenomena.
0
votes
0answers
16 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
42 views
How do we prove the time complexity of this simple problem in probabilistic inference on a Bayesian network?
Perhaps a rather trivial question, but I'm trying to refresh on proof methods in CS...
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,...
0
votes
0answers
42 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
76 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
86 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
20 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
34 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
57 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
17 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
36 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
37 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
28 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
33 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
59 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
27 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
43 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
28 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
29 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
30 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
21 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
76 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) \...
0
votes
1answer
29 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
13 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
138 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
13 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
54 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
14 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
20 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)?$$
3
votes
2answers
94 views
Uniform sampling over non-standard simplex
Uniform sampling over a $n$-dimensional standard simplex is described here: Uniform sampling from a simplex
I want to sample one point from a non-standard simplex with vertices at:
$s_{i}\vec{e_{i}}$...
1
vote
1answer
113 views
Given a rng that outputs 0 or 1 with an equal probability, make a rng that generates 1 with a probability p
So this was an interview question I had a few weeks back that I just haven't been able to think of how to solve...
Given a random number generator that returns 0 or 1 with a 50% chance of either, ...
1
vote
1answer
39 views
Maximizing entropy under constraint
How do I prove that entropy is maximal for $P(A_2) = \cdots = P(A_n) = (1-a) /(n-1)$ while $P(A_1) = a$ (a fixed number) and $A_1,…, A_n$ is a partition of the sample space?
4
votes
1answer
42 views
Probability of randomly designated subsets cover the universe
Let $U=\{1,2,\ldots,n\}$ and $S \subseteq \mathscr{P}(U)$. Let $T$ be a subset of $S$, randomly constructed selecting independently each element of $S$ with probability $p$.
Is there a polynomial ...
1
vote
2answers
88 views
challenge: Closing hash, linear probing, probe length 1
The challenge says that there is a hash algorithm with a bug, the bug is given if it reaches the end of the array and did not find space to save the element,
it discards it directly (that is, it does ...
5
votes
1answer
126 views
Is it possible to simulate a fair coin with a finite number of tossing of a biased one?
It is a classic problem to simulate a fair coin with a biased one.
According to Fair Coin (wiki),
John von Neumann gave the following procedure:
Toss the coin twice.
If the results ...
1
vote
2answers
144 views
How to determine seed collision probability in a PRNG?
I want to use a PRNG to generate random patterns. I would provide the PRNG with a hash value as a seed. Ideally, the seed size would be 64-bit or 128-bit and I would expect no collisions if the seeds ...
1
vote
2answers
41 views
Probability that a random graph will remain planar after adding an edge
According to this answer, a random graph on $n$ vertices is a graph which has each of the $n\choose2$ edges independently with probability $1/2$ each. The probability of at most $3n-6$ edges (which is ...
4
votes
2answers
63 views
Fast sampling from discrete space
Assume we are given a set $X = \{x_1,...,x_n \}$ of size $n$, and a probability distribution $P$ over $X$. I am interested in an algorithm $A$ which can sample from $X$ according to $P$, i.e. $\Pr(A=...
1
vote
1answer
45 views
number of random sets needed to generate subset
Let $A\subseteq \{1\ldots n\}$ with $|A|=\alpha n, 0<\alpha\leq1$. Now we start generating random sets $B_i \subseteq \{1\ldots n\}$ with $|B_i|=\beta n$ where $0<\beta\leq\alpha$.
How many $...
1
vote
0answers
36 views
distinguishing two biased coins
I had a simple probability question: suppose we have two coins, coin 1 is heads with probability $= 10\epsilon$ and coin 2 is heads with probability $=\epsilon/10$. Given an unknown coin, how many ...
2
votes
1answer
32 views
What is the average size of a jump in a binary tree?
Assume that a full binary tree is layed out in memory recursively in the following way.
First the Root followed by Tree representation of left subtree followed by tree representation of right subtree. ...
1
vote
1answer
48 views
Question on word probability for hierarchical softmax used in natural language processing
I am reading the following paper: https://papers.nips.cc/paper/5021-distributed-representations-of-words-and-phrases-and-their-compositionality.pdf
On page 4 of the paper they describe the ...
1
vote
1answer
51 views
Connection between probabilistic algorithm and distributional algorithm
A basic question about the connection between two notions. I am sure these are known notions in CS but I struggle with the basics:
First Definition:
A probabilistic algorithm $A(n)$ decides $L$ if for ...
1
vote
1answer
22 views
Probabilisitc timed automaton
I am kind of new to timed automaton domain. I am trying to understand in which way they are different to Markov Decision Process. First I know there objectives is to solve the non-determinism of a MDP....
0
votes
0answers
19 views
Conditional probability in Bayesian network
I have the following Bayesian network:
I want to state that P(S|B) = 1 - P(!S|B)
In the solution they use "P(S|B) = P(S|B,F) + P(S|B,!F)", which I understand but I don't understand why can't I use ...
0
votes
0answers
47 views
Optimality of Bayes Classifier
I know this question has been asked a few times but I find it hard to understand the solutions. Say, here (For example, I don't understand why the true error is defined in that answer the way it is.) ...
1
vote
1answer
44 views
Uniform sampling with constraints
Suppose one wants to uniformly sample a string $w$ of a given length over a finite alphabet, such $w$ satisfies a set of structural constraints (such as - "the third character has to be equal to the ...
0
votes
0answers
16 views
Relevance of Pure ALOHA for small network load G?
The theoretic performance of Pure ALOHA networks is a vastly studied topic and references can easily be found , e.g. on https://en.wikipedia.org/wiki/ALOHAnet#cite_note-tann-14
Using a Poisson ...
2
votes
1answer
23 views
Random award question
I'm assisting with the design of an algorithm over the next week to fit the following use case:
A person walking in a store has a tablet and approaches possible customers to notify them of a ...
0
votes
0answers
141 views
Proving a hash function family is weakly universal
$H$ is a family of weakly universal hash functions if for two elements $x,y$:
$$ P(h(x) = h(y)) \le \frac1m, $$
where $m$ is the size of the domain, and $h$ is chosen at random from $H$.
...
