0
votes
1answer
57 views

How to get 2 percentages to a 100%

First of im new to this site and I've never been the sharpest at math, im a web developer by trade. My question is math related but ill just give you a quick background about my website so that you ...
1
vote
1answer
21 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) = "yes"]$$ Where r is a truly ...
1
vote
0answers
46 views

what are the advantages and disadvantages of Belief propagation

Belief Propagation cannot solve the graphical model which has cycles. For undirected graphical model for example MRF and CRF in computer vision area, in which cases the model has no cycle ? As far as ...
0
votes
1answer
41 views

Help with probability formula in programming problem

I am trying to solve this dynamic programming problem using probabilities. I know how the recurrence for it should look but I have problems using a probability formula. I have the next case: In a ...
1
vote
2answers
133 views

Probability that $\frac{n}{2}$ bins are empty [close]

A Bloom filter of length $n$ was built. I have only the first $\frac{n}{2}$ bits of this filter. How will the false positive probability change? For the whole Bloom filter, the false positive ...
0
votes
0answers
190 views

Is it possible for the expectation of a random variable to be greater than it's range?

I am reading the following paper: http://www.cis.upenn.edu/~sanjeev/papers/focs11_sorting.pdf : and it states the following: Sample $N = 2(n+1)^2ln(n)$ points $\mathbf{x^1}, ..., \mathbf{x^N}$ from ...
1
vote
4answers
95 views

Is the mathematical concept of an “operation” necessarily deterministic?

Does the mathematical concept of an operation require that the process is deterministic? If not, what are some example cases for non-deterministic operations? Motivation: I am coming from a ...
3
votes
1answer
100 views

Balls on Stairs

Recently I realized that lost all computing skill in probability. Please take a look at the following problem. There are $b$ balls that are thrown one by one and bounce from top to bottom on the $n$ ...
2
votes
1answer
100 views

An interesting version of the problem “balls into bins”

Consider n people, each has k identical balls. Each people choose k different bins from m bins, constrained by the condition that there are no two people choose exactly the same k bins. For instance, ...
1
vote
0answers
20 views

Confusion related to Kulldorff's scan statistics

I was reading this paper related to Bayesian spatial scan statistics where I came across the Kulldorff's scan statistics. I have attached the screenshot of the paper. My objective is to find a ...
1
vote
0answers
47 views

Mean matching size

Suppose there is a simple bipartite graph $G(X,E,Y)$, where $|X|=n_1$, $|Y|=n_2$, $|E|=m$. The edges $E$ are chosen uniformly at random. The question is what is a mean value of the size of the ...
0
votes
0answers
109 views

Compute the probability $p$ of creating an edge in $G(n,p)$. (Erdős–Rényi random graph)

Consider $G(n,p)$, an Erdős–Rényi random graph with $n$ nodes, $m$ edges, and mean degree $c$: Compute the probability $p$ of creating an edge in $G(n,p)$. What exactly it means?
4
votes
1answer
494 views

Optimal Yahtzee (Dice roll) decisions: Probability and weighting choices

I'm a senior in computer science, and I have a hobby of taking on little projects that I find interesting. My current one is a Yahtzee optimal play solver. One would enter their current roll, and it ...
4
votes
3answers
4k views

Great Book on Probability and Statistics (for Computer Scientists)

I'm a Computer Science sophomore and we're studying Probability and Statistics (fundamentals and all). The teacher recommends a book which I don't like since it does not even try and explain ...
1
vote
2answers
47 views

Finding the probability of a client getting the same token in two consecutive interactions.

I am trying to find the probability in the following real-world inspired scenario. If I have a finite set of whole numbers from 0 to 4 billion which I call tokens and $n$ clients. Each time a client ...
1
vote
1answer
93 views

How to compare time complexities involving an exponential and a polynomial?

A sequence of events $A_n, n \in \mathbb{N}$ is said to have a high probability, if $\mathrm{P} (A_n^c) \leq \frac{c}{n^d}$ for some $c, d >0$. Chernoff bounds are often used to prove some (upper ...
8
votes
1answer
356 views

Throwing balls into $b$ buckets: when does some bucket overflow size $s$?

Suppose you throw balls one-by-one into $b$ buckets, uniformly at random. At what time does the size of some (any) bucket exceed size $s$? That is, consider the following random process. At each of ...
1
vote
1answer
146 views

Maximally entropy preserving irreversible functions. (CS related)

The topic/problem is related to hashing for data structures used in programming, but I seek formal treatment. I hope that by studying the problem I will be enlightened of the fundamental limitations ...
1
vote
1answer
189 views

lower bound for probability of no 2 balls per bin.

There are $n$ balls and $m$ bins and every ball is placed independently and uniformly at random into a bin. I'm trying to show that there exists a constant $c$ such that, if $m=c\sqrt{n}$ then with ...
7
votes
1answer
215 views

Tuning the birthday paradox

I have limited access to a collection $X_1,\ldots,X_m$ of sets of positive integers. Each $X_i$ is "moderately large" (a brief survey has found them to contain about $10^6$ elements in each set), but ...
1
vote
1answer
802 views

Probability of collision in binary exponential backoff

Four stations are trying to transmit frames through a single channel (only one frame per channel). After each frame is sent, they contend for the channel using Binary Exponential Backoff. After ...
0
votes
1answer
56 views

Probabilistic performance guarantees on information retrieval queries

The following is a question from lecture notes and although not assigned homework, I am trying to solve it. Assume that we have a collection $C$ of $N$ documents and a query $q$. There are $R_{q}$ ...
1
vote
2answers
145 views

How to select the optimum combination of numbers from a random list that add to up to a certain total (or as close to)

I'm developing a computer program, and need an algorithm to solve the following problem: How to select the optimum combination of numbers from a random list that add to up to a certain total (or as ...
4
votes
1answer
180 views

Complexity - why is RL=NL when omitting the demand for polynomial run-time?

The complexity class RL is described at the complexity zoo as: Has the same relation to L as RP does to P. The randomized machine must halt with probability 1 on any input. It must also run in ...