Questions about the branch of mathematics concerned with modelling and analysing random phenomena.

learn more… | top users | synonyms

0
votes
0answers
4 views

How to make logical inference from simulated data

I have data collected from a computer simulation of football games which seem to have recurring patterns of the following form. if madrid plays arsernal and the match ends under 3 goal, then on ...
0
votes
1answer
6 views

Estimating the $\beta$th moment of a uniform random variable

Let $n$ be a positive integer, $\beta > 1$, and let $X$ be a random variable uniformly distributed over $\{0, \ldots , n -1\}$. Show that $\mathbb{E}[X^\beta] \leq n^\beta / (\beta + 1)$. I don't ...
1
vote
0answers
13 views

Intelligent Agents-Probability and Beliefs

I am reading about probability and beliefs in artificial intelligent agents, and came across the following passage: ...
1
vote
0answers
24 views

Using “incremental algorithms” to find the $k^{th}$ smallest number

This is what I vaguely understand of what an "incremental algorithm" is - say one such for calculating the $k^{th}$ smallest number for a given sequence of elements $x_1, x_2,...,x_n$ then after the ...
2
votes
2answers
40 views

About sorting numbers in linear time

If one is given $n$ numbers picked uniformly at random from the interval $[0,1]$ then is it possible to sort them in linear time? It seems to me that some such method exists which uses binary ...
1
vote
0answers
25 views

How to find number of occurences of specific distances in binary (search) trees?

I want to calculate the amount of tree structures that have a given maximal distance between two nodes given an amount n of nodes (or keys). E.g. with ...
4
votes
1answer
43 views

Mutual information intuition

I was creating an example for a casual talk on mutual information. I considered a system of two coins, which with probability 1/2 are copies of each other, and with probability 1/2 are independent. ...
-2
votes
1answer
23 views

Find the approximate number of messages (n) that need to be tried

Find the approximate number of messages (n) that need to be tried before finding two that had the same message digest (size k) with probability 0.8. You need to find n as a function of k . What is n ...
12
votes
4answers
187 views

Simulate a fair die with a biased die

Given a biased $N$-sided die, how can a random number in the range $[1,N]$ be generated uniformly? The probability distribution of the die faces is not known, all that is known is that each face has a ...
-3
votes
1answer
91 views

Probabilty that quicksort partition creates an imbalanced partition

I have come across this question: Let 0<α<.5 be some constant (independent of the input array length n). Recall the Partition subroutine employed by the QuickSort algorithm, as explained in ...
11
votes
7answers
2k views

How to simulate a die given a fair coin

Suppose that you're given a fair coin and you would like to simulate the probability distribution of repeatedly flipping a fair (six-sided) die. My initial idea is that we need to choose appropriate ...
2
votes
1answer
87 views

Arrangement of numbers in a grid

I have a $n \times m$ matrix $M$ and a permutation of sequence $P$ of numbers from $1$ to $n$. I have to fill the matrix using numbers $1$ to $n \times m$ in such a way that for each row $i$, the ...
3
votes
2answers
326 views

Returning a random subset with length k of N strings while only storing at most k of them

Here's the problem. I've written a program that reads strings from stdin, and returns a random subset of those strings. The only other argument provided to the program is the length of the subset, ...
1
vote
1answer
51 views

In an M/M/1 Queue, what does exponential distribution of service time mean?

I was reading about the M/M/1 Queue and that we assume new customers arrive according to a Poisson distribution, and each customer takes an amount of time to ...
-4
votes
1answer
44 views

m-element random sample being equally likely …(CLRS 5.3-7)? [closed]

I am trying to understand the following solution to CLRS 5.3-7: http://clrs.skanev.com/05/03/07.html Question description is on the page. I understood the part where m-element subset is constructed ...
7
votes
1answer
98 views

Which one of these two sequences is random, and which one is not?

We let $\alpha = \alpha_1\alpha_2\alpha_3\ldots$ be an infinite random sequence (under the uniform measure) where $\alpha_i$ may be $1$ or $0$, and then define the boolean function $B_k$: $$ ...
8
votes
1answer
96 views

Probability Distributions and Computational Complexity

This question is about the intersection of probability theory and computational complexity. One key observation is that some distributions are easier to generate than others. For example, the problem ...
2
votes
0answers
81 views

What is the average-case running time of Fun-sort?

I read this paper: http://www.sciencedirect.com/science/article/pii/S0166218X04001131?np=y (you can check the PDF online for free), and I translated section 4's Fun-sort algorithm (correct me if I'm ...
6
votes
1answer
56 views

Expected number of maximal cliques in $G(n,p)$

The $G(n,p)$ random graph model creates graphs with $n$ vertices and each possible edge exists independently with probability $p\in (0,1)$. Much is known about the (expected) size of a largest ...
2
votes
1answer
46 views

Understanding Expected Running Time of Randomized Algorithms

I want to understand the expected running time and the worse-case expected running time. I got confused when I saw this figure (source), where $I$ is the input and $S$ is the sequence of random ...
1
vote
1answer
105 views

Understanding Monte Carlo Probabilities

I am trying to get a good grasp on Monte Carlo (MC) algorithms, but I feel I am missing something fundamental. What I don't understand is how MC improves its confidence of giving the correct solution ...
1
vote
0answers
27 views

What is linear relaxation in the context of bayesian networks? [closed]

To add onto the question, how are elliptical differential equations applicable in this context? I was listening to a talk about Bayesian networks and someone asked if they were using differential ...
-3
votes
2answers
111 views

Perceptron learning rule for classification

That's the problem $$y=(x,w,\rho) = \begin{cases} 1 & \sum_{i=1}^3 w_ix_i >\rho\\ 0 & \text{otherwise} \end{cases},$$ where $x=\{x_1,x_2,x_3\}$ are inputs, $w=\{w_1,w_2,w_3\}$ are ...
1
vote
1answer
56 views

Min-entropy of a random pre-image of a random function

I am facing hard time understanding min-entropy. Fix $v \in \{0,1\}^{n/2}$, let $F\colon \{0,1\}^n \to \{0,1\}^{n/2}$ be chosen randomly, and let $X_v$ be a string chosen uniformly at random among ...
4
votes
1answer
364 views

Is this method really uniformly random?

I have a list and want to select a random item from the list. An algorithm which is said to be random: When you see the first item in the list, you set it as the selected item. When you see ...
2
votes
2answers
82 views

Soft Margin Loss and Conditional Probabilities

Consider the following soft margin loss function: $\max(0, 1-yf(x))$. I have the problem of needing to compute the conditional probability $p(y|x)$ corresponding to this function and am having ...
5
votes
1answer
84 views

Possible to construct a probabilistic halting problem solver?

I'm a CS undergrad so my math/CS knowledge is not that deep so please correct me if my premise is flawed or I have made some incorrect assumptions. So I was thinking, much in the way that some ...
0
votes
1answer
55 views

In Probabilistic Graphical Models, are Cliques and Clusters the same?

I am learning Probabilistic Graphical Models with the help of the videos on Coursera. I am in week 4 and I see cliques being mentioned often. But the graphs being discussed are cluster graphs. So are ...
1
vote
1answer
32 views

Interpreting probabilistic time turning machines

I was trying to understand better the definition of a strong PSRG and I came across this expression which I am trying to understand better: $$ Pr_{r \in \{0,1\}^l}[A(r) = \text{"yes"}]$$ Where r is ...
3
votes
0answers
31 views

Adversarial bin packing

An adversary gives you a set of items whose total size is $x$ (he gets to choose how $x$ is distributed. e.g. there may be $k-1$ items of size $\frac{x}{k}$ and 2 items of size $\frac{x}{2k}$). The ...
0
votes
1answer
81 views

Naive Bayes Intuition

I have some difficulties in understanding the intuition behind Naive Bayes Classification. In general, I do understand every argument of the definition, however I don't understand why it's correct ...
-2
votes
2answers
93 views

help with the probability of acceptance of a Nondeterministic Pushdown automata

I have this nondeterministic pda: $$\Sigma= \{a,b,c\}$$ and $$ L=\{\omega\ \epsilon\ \Sigma^*\ |\ \omega\ = \alpha\beta\beta^R\gamma\ and\ \alpha,\beta,\gamma\ \epsilon\ \Sigma^*\ and\ |\beta|\ ...
-2
votes
1answer
63 views

proof of convergence in arbitrary precision PRNGs

consider a program that generates a random walk using a PRNG, as in following pseudocode. it uses arbitrary precision arithmetic such that there is no limit on variable values (ie no overflow). ...
-3
votes
2answers
117 views

Measuring uniformity of CRC32 by using birthday problem

I would like to measure what is the probability that given some data and it's CRC32 checksum there is some other data with the same checksum. Running the simulation is not feasible because of the 2^32 ...
6
votes
1answer
136 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 ...
0
votes
1answer
58 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 ...
2
votes
0answers
63 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
163 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
81 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
2answers
77 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
195 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
207 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
127 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
423 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
101 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
63 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
276 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 ...
6
votes
3answers
195 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
97 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
28 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 ...