Questions tagged [probability-theory]
Questions about the branch of mathematics concerned with modelling and analysing random phenomena.
2
votes
1answer
26 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
24 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
31 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
53 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
25 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
39 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
27 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
68 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
23 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
115 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
12 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
44 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
13 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
19 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
86 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
109 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
84 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
113 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
119 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
38 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
58 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
44 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
33 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
31 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
39 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
47 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
18 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
44 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
41 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
13 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
110 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$.
...
1
vote
1answer
18 views
Upper bound derivation of expected time for finding a large cut
Given an undirected graph $G$ with $n$ vertices and $m$ edges, we build a cut as following. Initially sets (of vertices) $A$ and $B$ are empty. For each vertex $v$ we flip a fair coin and according to ...
2
votes
1answer
89 views
Average-case analysis of linear search given that the desired element appears $k$ times
The problem below is adapted from CLRS Problem 5-2 "Searching an unsorted array":
Consider a deterministic linear search algorithm which searches an array $A$ for $x$ in order, say $A[1], A[2], \...
0
votes
1answer
27 views
Markov Model to compute the probaility on the $n^{th}$ day
This is a question about Markov Models. Let's say we have the following situation
Let's say that we want to find the probability that $2$ rainy days follow a nice day. You'd simply have $0.25 \cdot ...
2
votes
1answer
54 views
Avoiding correlated values and reduced collision resistance in multiple hash states
I need to design a hash function that fits this criteria:
Limited to 32-bit integer operations (for compatibility with JavaScript bitwise operations, my target system)
Produces an n-bit hash digest, ...
0
votes
1answer
18 views
Relation between size of hashtable and number of values to keep expected number of collisions below/equal to 1
This is an exam question from my algorithms and data structures course.
You imagine an hash function with h: U->{0,..m} (this is from the original question, but i think m-1 would be correct) and n ...
2
votes
2answers
52 views
Why does the distribution of pseudorandom numbers change when operating like this?
We were introduced to the standard C rand() function, and how to use it.
At some point during the class we were asked how to roll a die. The simple answer was to ...
0
votes
0answers
14 views
Presentation topic for computational solutions to problems involving probability
I'm looking for interesting applications of computing science for finding the probability of otherwise difficult problems. This is for an undergraduate level presentation in a probability course of ...
-1
votes
1answer
165 views
Applying a Chernoff bound with Only an Upper Bound of the Expectation
First, I am aware at least one or two similar questions have already been asked on stack exchange, but I've gone through the answers they got and didn't find one that was satisfactory for my case.
The ...
0
votes
1answer
196 views
ALOHA - Throughput and probabilities
I have a few questions regarding slotted-ALOHA. Assume a network have 25 users and transmission request probability = 0.25.
1) What is the throughput and what is the probability that a user will ...
5
votes
1answer
541 views
Reservoir sampling algorithm probability
I'm reading about the reservoir sampling technique called Algorithm R.
The idea is we can take a sample of size $n$ from a population of size $N$ even when $N$ is unknown/too expensive to retrieve in ...
