Questions about the branch of mathematics concerned with modelling and analysing random phenomena.
1
vote
2answers
35 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
46 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=...
0
votes
1answer
35 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
29 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
24 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
21 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
42 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
15 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
17 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
33 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
5 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
22 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
23 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
47 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
25 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
46 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
15 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
30 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
83 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
332 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 ...
0
votes
1answer
46 views
Trying to understand CLRS bucket sort analysis
I'm trying to understand the analysis of bucket sort in CLRS. Specifically, equation 8.2 that states:
$$ E[{n_i^2}] = 2 - \frac{1}{n} $$
To prove, CLRS:
Random variable denoting number of elements ...
0
votes
1answer
66 views
Expected number of vertices with degree 2
A simple graph with $n$ vertices is constructed by randomly and independently placing an edge between every two vertices with probability $p$. What is the expected number of nodes with degree two?
I ...
2
votes
1answer
47 views
Viterbi Algorithm: initial state with ONE probability
The Viterbi Algorithm can be used to calculate the most likely path, based on observations in a Hidden Markov Model.
Using the same notations as Wikipedia, "each element ...
1
vote
1answer
126 views
Probability of k-clique in a random graph
I need to find the order of the minimum k = k(n) such that the probability of having at least 1 k-clique in a random graph $G(n, \frac{1}{2}$) is $\mathcal{O}(\frac{1}{n})$.
$X_k$ is the random ...
2
votes
2answers
207 views
how to bound the probability that quicksort takes greater than n lg n time?
I am working on exercise 12.4-5 of CLRS (Cormen et al, Intro to Algorithms 3rd ed)
Consider RANDOMIZED-QUICKSORT operating on a sequence of n distinct input numbers. Prove that for any constant k > ...
2
votes
1answer
110 views
How to estimate how many assignments satisfy a given DNF formula using Monte Carlo?
Admittedly, homework.
For the purpose of this question: $\phi$ is a DNF formula similar to this one: $(x_1 \wedge \neg x_3 \wedge x_4) \vee (\neg x_1 \wedge x_2)$ Also $C_i$ is a clause in this ...
6
votes
1answer
2k views
Why are forks in the Blockchain eventually resolved?
I'm reading Wattenhofer's The Science of the Blockchain. On page 87, he states the following thoerem:
Theorem 7.22. Forks are eventually resolved and all nodes eventually agree on which is the ...
3
votes
1answer
26 views
Polynomial Computation of the probability of a number of independent events
Suppose to have $n$ independent events $E_1, E_2,..., E_n$, where the probability of occurrence of event $E_i$ is $p_i$ (i.e., each event has its own probability of occurrence). We can easily define ...
2
votes
0answers
36 views
How do I do a biased shuffling of a deck of cards?
I currently have a deck of cards (in fact this deck is an array of sorted elements in descending order as indicated by the picture above), that I want to shuffle. However, the caveat is that I want ...
0
votes
0answers
33 views
Pathological input for a completely random hash function
I have a hash function $h$ (assume it's completely random, an element of a Universal family) which maps integers into one of $k=10$ groups.
Now I'm looking for an input sequence of length $m$ for $h$ ...
0
votes
0answers
47 views
Average solutions in infinite search tree
I have the following problem:
Consider a balanced infinite search tree with branching number $κ$. Consider a
search problem with solutions which may be located at any node of the tree.
The ...
0
votes
0answers
22 views
How are Probability and Non Determinism Related ? Alternatives to handle Non determinism?
I have been thinking about Non-determinism in any kind of state machine. Since I work on machine learning, I tend to think that probability is a means of handling non-determinism. Instead of ...
2
votes
0answers
28 views
Why can optimality be preserved when inserting a new conjunct into an optimally ordered conjunction of conditions? [duplicate]
In a programming language with short-circuiting, a conjunction of N independent conditions has the following expected cost:
where:
...
2
votes
2answers
114 views
The optimal way to reverse engineer a binary classification problem
I am not sure if this question is more suitable for CS, theoretical CS or math so feel free to improve the description and migrate it.
In a scenario very similar to popular binary classification ...
1
vote
0answers
147 views
How to choose value of additive smoothing in naive Bayes and why a higher value gives bad accuracy?
In Naive Bayes we often do additive smoothing as a fail safe. Consider the following expression:
Lets say
$$P(X_i) = \frac{count(X_i) + \alpha}{\sum_i^n count(X_i) + \alpha*total\_size}$$
How to tune ...
1
vote
0answers
30 views
Game with Random Digits (Markov Chain / Coupling)
I've been self-studying Markov Chains and came across a problem online here: http://websites.math.leidenuniv.nl/probability/lecturenotes/CouplingLectures.pdf
I'm not asking for anything too formal (I'...
2
votes
1answer
70 views
Confuse on using bucket number to replace hashing multiple times in hyperloglog explanation
In this blog the author states that the following
So we now have a rather poor estimate of the number of values in the
dataset based on bit patterns. How can we improve on it? One
...
0
votes
0answers
80 views
Probability in Dynamic frame aloha
If I've RFID Collision Arbitration System that is based on multi-frame dynamic frame ALOHA. How can compute the probability of the average tag resolution $L_n$? ,$P_s$ is probability for packet ...
3
votes
2answers
53 views
Are typical sets larger, when information is messier?
Let $0\le q<p\le \frac{1}{2}$, and let $P,Q$ be two Bernoulli Random Variables such that:
$$Pr[P=1]=p ; Pr[P=0]=1-p$$ and $$Pr[Q=1]=q ; Pr[Q=0]=1-q$$
My question: Does it follow that, for any $\...
3
votes
1answer
68 views
Probability of k-connectedness for a random graph with given degree sequence
For a degree sequence $(d_1,\ldots, d_n)$ with $\min d_i \geq k$ pick a graph with that degree sequence uniformly at random. What's the probability that the graph is k-connected?
I know that for ...
1
vote
1answer
35 views
Probabilistic analysis of finding 2nd largest value in vector
Given the following algorithm for finding the second largest element in a vector:
...
0
votes
0answers
23 views
$BPP$ class and theorem
Let $L \in BPP$ be decided by a poly-time $TM M (x, u)$ using certificates of
poly-length $p(n)$.
Then for every $n \in \mathbb{N}$ there exists a certificate $u_n$ s.t. for all $x$ with $|x| = n$:
$...
0
votes
1answer
83 views
Equivalence of machine $M$ in $BPP$ and $EXP$
Ok, the proof is clear. But, if we prove that $BPP \subseteq EXP$ we should show that for every machin in $BPP$ there exists equivalent machine in $EXP$. I cannot see how the $EXP$-machine is ...
3
votes
1answer
39 views
Randomized BST height analysis : How $Z_{n,i}$ and $Y_{k-1}$ are independent?
I am referring to this video https://www.youtube.com/watch?v=vgELyZ9LXX4 at 1:08:39 .
$n$ : number of nodes in the tree
$Z_{n,k}$ : Indicator random variable that activates when rank of the root ...
0
votes
0answers
18 views
Probability that the word is of language using N-Grams
Some programm should allow users to identify the word language probability. All i have is some statistics - the frequency of using bigrams and ...
1
vote
0answers
41 views
Bound covariance of two discrete random variables
Let $X,Y$ be two random variables over a discrete probability space, such that $X \in [0,1]$ and $Y \in [0,1]$. I want to prove that $$ |\text{Cov}[X,Y]| \leq \sqrt{0.5 \; I[X,Y]}$$ where $I[]$ is ...
