Questions about the branch of mathematics concerned with modelling and analysing random phenomena.
1
vote
1answer
13 views
Proof that probability that hashing with open addressing needs more than $k$ attempts is $2^{-k}$ at most
There are $n$ elements in a hash table of size $m \geq 2n$ which uses open addressing to avoid collisions.
The hash function was chosen randomly among a set of uniform functions. A set $H$ of ...
5
votes
0answers
80 views
Estimating the time until we obtain five-in-a-row?
Consider the following random process. We have a $10\times 10$ grid. At each time step, we pick a random empty grid cell (selected uniformly at random from among all empty cells) and place a marker ...
2
votes
1answer
55 views
Expected number of times heapify will be called
I need to analyze the time complexity of an algorithm to keep track of minimum $K$ numbers from a stream of $R$ numbers . The algorithm is
...
0
votes
1answer
51 views
Post-selection and complexity theory [closed]
I read about post-selection and didn't understand the meaning behind this thing. I didn't understand the Wikipedia article well, so what is a simple but understandable explanation of post-selection ...
0
votes
0answers
46 views
Which component sizes do we observe while randomly deconstructing a tree?
Suppose I have a connected graph with $n$ vertices and $n−1$ edges, that is in form of a tree. Now, I will add the number of vertices in the tree and uniformly randomly select a vertex. I break the ...
3
votes
2answers
54 views
Probability that a uniformly random sequence is already sorted
Now I tried tackling this question from different perspectives (and already asked a couple of questions here and there), but perhaps only now can I formulate it well and ask you (since I have no good ...
2
votes
1answer
27 views
Sort algorithm input probabilities
Suppose that there is an algorithm which sorts a sequence of $n$ elements
$$a_1, a_2, ..., a_n$$
Each of the $a_i$ is chosen with probability $1/k$ from a set of $k$ distinct integer numbers.
Is ...
0
votes
0answers
10 views
Why variance in probability is taken as E[(X−E[X])2]? [migrated]
Why is the Variance of a random variable X defined as E[(X−E[X])2] instead of E[|X−E[x]|], where E(X) is the Expected Value of X?.
Let's suppose that all values of X are positive, then E[X] must be ...
0
votes
2answers
51 views
Bayesian Network - Inference
I have the following Bayesian Network and need help with answering the following query.
EDITED:
Here are my solutions to questions a and b:
a)
...
-1
votes
1answer
120 views
Little's law and average time on a system with a switch
We have a switch with $2$ lines of input and $2$ output. Each line is $10 Mbps$. The size of packets is fixed and is $1KB$. The $1^{st}$ line of input is active (transferring packets) $40\%$ of the ...
4
votes
2answers
157 views
Recommended readings for Probability theory applied to algorithms
Currently, I'm delving into Analysis of Algorithms and I've discovered that I would need to improve my knowledge of Probability Theory. Any recommendation? Where do I start?
Thanks in advance!
2
votes
2answers
85 views
Measures and probability in formal language theory
I am looking for references for the following problem:
I have a very special class of regular languages and my aim is to express (and to justify my conjecture) that this class itself is very small in ...
1
vote
1answer
102 views
Average number of slots needed in slotted-Aloha
Consider 2 stations that share the same bus. Both stations are perfect synchronized each other and when they have packets to transmit, they are starting the transmission in the beginning of a same ...
2
votes
1answer
52 views
Interpretation of “expected cost” of an algorithm
I'm studying randomized algorithms and I sometimes come across results like
(1) The algorithm has an expected $O(f(n))$ cost.
and
(2) With constant probability, the cost is bounded by ...
3
votes
1answer
55 views
How to compute a level set $A=\left\{ \theta:f\left(\theta\right)\geq a\right\} $
I have a real function $f:\mathbb{{R}}^{d}\mapsto\mathbb{R}$, where
$d>1$. The question is how to compute the level set $A=\left\{ \theta:f\left(\theta\right)\geq a\right\} $.
I am a statistician ...
1
vote
2answers
128 views
Generate random numbers from an interval with holes
Given a set $S$ of $k$ numbers in $[0, N)$.
The task is to randomly generate numbers in the range $[0, N)$ such that none belongs to $S$.
Edit - Also given an API to generate random numbers between ...
5
votes
3answers
129 views
Computer science problems related to music?
Are there any CS problems, preferably open, that are related to music or musical theory somehow? I would think of problem with musical notation but also probabilities when randomizing according to a ...
6
votes
1answer
82 views
Can expected “depth” of an element and expected “height” differ significantly?
When analysing treaps (or, equivalently, BSTs or Quicksort), it is not too hard to show that
$\qquad\displaystyle \mathbb{E}[d(k)] \in O(\log n)$
where $d(k)$ is the depth of the element with rank ...
3
votes
0answers
19 views
Should Expectation Maximization take into account the Naive Bayes' independence assumption?
Should the independence assumption on which the Naive Bayes (NB) classifier is based, be taken into account when applying Expectation Maximization(EM) to infer missing values?
The Naive Bayes ...
2
votes
1answer
111 views
Understanding an example of coin toss expectation maximization [duplicate]
I've been trying to get my head around Expectation maximization algorithms, and I thought I'd start simple. I found this 3-coin example here: http://cs.dartmouth.edu/~cs104/CS104_11.04.22.pdf I ...
0
votes
2answers
58 views
distance between histograms
I have 2 histograms that represent the height of characters in 2 images.
example:
1 **
2 ****
3 ****
.
.
.
100 ******
For these 2 histograms I compute the peaks. And To check if these 2 images ...
2
votes
0answers
34 views
Exact Inference in Bayesian Networks
I'm doing some exam study and came across a question I'm not really sure on. Consider the Bayesian network below:
Let's denote "Disease" with $D$ and "Symptom" with $S$.
I want to find $P(D \mid ...
3
votes
2answers
61 views
Randomized Algorithms Probability
I'm taking a grad level randomized algorithms course in the fall. The professor is known for being very detail oriented and mathematically rigorous, so I will be required to have an in-depth ...
3
votes
0answers
54 views
Conditional Probabilities as Tensors?
Is it proper to view conditional probabilities, such as the forms:
P(a|c)
P(a|c,d)
P(a, b|c, d)
...and so forth, as being tensors?
If so, does anyone know of a decent introductory text (online ...
1
vote
1answer
92 views
What is the purpose of Bayesian networks?
I have seen a lot of explanations of what Bayesian networks are, but I simply cannot wrap my head around their use in code. So here is my three part question.
Am I right in my definition of bayes ...
1
vote
1answer
75 views
What makes Bayesian Networks decomposable into joint trees?
Given a Bayesian Network $N$, one can build a junction/joint tree $JT$ over $N$ by applying series of steps (namely, moralisation,triangulation..etc). Then we can use $JT$ to answer queries over $N$.
...
0
votes
1answer
40 views
Compare two methods of random permutations
I want to compare in a practical sense two methods of random permutations -- one theoretically perfect, namely that of Fisher and Yates, and another ad hoc, let's
call it X. A way of comparison I ...
2
votes
1answer
87 views
How to distinguish whether a sample is from distribution $\chi_1$ or $\chi_2$?
I am given an oracle $A$ that takes input samples from two distributions $\chi_1$ and $\chi_2$.
Suppose we have $Pr_{x \sim \chi_1}[A(x) = 1] = p_1$ and $Pr_{x \sim \chi_2}[A(x) = 1] = p_2$, where ...
3
votes
1answer
35 views
Chazelle's discrepancy book: greedy method
In Bernard Chazelle's book The Discrepancy Method, which is available free as a PDF from the author's website, the very first statement requiring thought by the reader (on page 3, just before Theorem ...
1
vote
1answer
73 views
What does the posterior probability of a variable mean in the Bayes' rule?
I have been studying Artificial Intelligence and I have noticed that the Bayes' rule allows us to infer the posterior probability if a variable. But, my question is, what does the word, or phrase, ...
1
vote
1answer
59 views
Null Hypothesis in Analysis and Testing
I have my end of year exams next Thursday. I'm generally doing fine but I am having some major issues with this strand of my course, this has to be the biggest issue I have. So, here is the question ...
2
votes
1answer
41 views
The notion of density of distribution
I have difficulties in understanding the notion of density for distribution.
Notion of density for distribution. A distribution $H$ over $\{0,1\}^n$ has density $\sigma$ if for every $x \in ...
4
votes
1answer
109 views
Negligible Function in Cryptography
In the field of Cryptography and Computation Complexity there is a notion of negligible function.
I have some difficulties in understanding intuition behind this notion. The following are some ...
4
votes
1answer
76 views
Shannon Entropy to Min-Entropy
In many papers I've read that it is well known that the Shannon entropy of a random variable can be converted to min-entropy (up to small statistical distance) by taking independent copies of the ...
8
votes
1answer
708 views
Applying Expectation Maximization to coin toss examples
I've been self-studying the Expectation Maximization lately, and grabbed myself some simple examples in the process:
From here: There are three coins $c_0$, $c_1$ and $c_2$ with $p_0$, $p_1$ and ...
2
votes
1answer
69 views
Mutual information and moment generating functions
I went to listen to a workshop and someone from the audience asked the presenter how the moments can improve the mutual information. I am learning about MI (Mutual Information) so didn't have enough ...
3
votes
1answer
115 views
Pointwise mutual information vs. Mutual information?
I am learning about information theory and mutual information. However, I am quite confused with MI(Mutual information) vs. PMI(Pointwise mutual information) especially signs of MI and PMI values. ...
3
votes
3answers
64 views
Unbiasing of sequences
There is the well-known method of unbiasing of bit sequences due to von Neumann. Are there similar schemes applicable to other sequences, e.g. the result of throwing a normal die?
0
votes
1answer
44 views
Smoothing frequencies without count data
I have frequency data for different events under two conditions, resulting in sets of frequencies F1 and F2. I would like to normalize the frequencies of events under condition 1 by their frequencies ...
1
vote
3answers
124 views
Random graph model
When we say that in random graph we add an edge with a certain fixed probability, what do we actually mean?
For example if probability is 0.5, does that mean that we can just add two edges in a graph ...
8
votes
2answers
278 views
Discrepancy between heads and tails
Consider a sequence of $n$ flips of an unbiased coin. Let $H_i$ denote the absolute value of the excess of the number of heads over tails seen in the first $i$ flips. Define $H=\text{max}_i H_i$. Show ...
6
votes
1answer
127 views
Mental poker: proving dealt hand is fair
I have just read mental poker, described in this fascinating paper(PDF) by cryptographic greats Adi Shamir, Ron Rivest, and Leonard Adleman.
Assuming I have a website, (TTP) how can I prove to the ...
2
votes
2answers
60 views
Condition in Shamir Secret Sharing Scheme
For Shamir's secret sharing scheme (doi 10.1145/359168.359176), one obtains a random polynomial $q$ of degree at most $n-1$ (over $\mathbb{Z}_p[x]$). The constant coefficient of this polynomial is ...
5
votes
0answers
104 views
Building probability distribution functions from observation
There are N players and M objects, each of the objects has a value. Each player has a strategy in choosing an object. Each round a player will choose an object, many players can choose the same ...
3
votes
1answer
145 views
How many random walks to start from each node?
Assume that we are given a real life graph, DBLP network in my case, where degree distribution of nodes follows a power law (many nodes have 1, 2 neighbors, and only a few nodes have hundreds of ...
2
votes
1answer
77 views
probability wheel, redistribution of probabilities
I have a contiguous ordered data structure (0 based index):
x= [1/3, 1/3, 1/3]
Let's say I selected index 1 and increased the probability by 1/3. Rest of the ...
0
votes
0answers
104 views
How to calculate the blocking probability of processes with gamma-distributed service times using the Erlang formula?
I have seen numerous examples of using the Erlang formula to calculate the blocking probability for processes with exponentially distributed service times. However, I am not quite sure how to do that ...
22
votes
2answers
305 views
How asymptotically bad is naive shuffling?
It's well-known that this 'naive' algorithm for shuffling an array by swapping each item with another randomly-chosen one doesn't work correctly:
...
3
votes
2answers
133 views
Construction of binary random variable
We throw two coins in a row and thus get the event space $\{ZZ, WW, ZW, WZ\}$.
Each of the 4 elementary events has a probability $1/4$.
how can I construct 3 binary random variable $x_1$, $x_2$, ...
5
votes
1answer
61 views
Maximal derangements
When one shuffles playing cards, the goal is evidently to achieve a possibly big derangement
of a given deck. For manual shuffling there are terms like inshuffle, outshuffle etc. I like
to know ...
