0
votes
1answer
35 views

How do you find the probability of a certain state in Markov Chain?

This question appears without answer in an old exam I found (not a homework question) Suppose messages that enter a system need to be processed by two servers. They arrive at the system at a ...
1
vote
1answer
52 views

Calculate the probability that at least k of his favourite students are awarded?

Our hero - Maga is going to make a new contest for making the best teams. He is really excited about it. There will be S students in the contest. First N students in the final standings will be ...
0
votes
0answers
47 views

Calculate the Probability for Binary Matrix

Consider a binary matrix of dimension $m\times n$. Suppose the probability of occurrence of 1 is $p$ in any row of the matrix. Each row of the matrix is independent to each other. The all possible ...
0
votes
1answer
23 views

Strong one-way functions: a remark on the definition

Notation: $\Sigma^k$ is the set of $k$-strings on the alphabet $\Sigma$; $\Sigma^\ast$ is the set of all finite dimensional strings on the alphabet $\Sigma$. In the context of computer-science a ...
0
votes
1answer
61 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
23 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
77 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
55 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
137 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
193 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
97 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
101 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
104 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
48 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 ...
4
votes
1answer
596 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 ...
5
votes
3answers
5k 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
50 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
94 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
372 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
158 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
201 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
218 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
894 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
147 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 ...
5
votes
1answer
203 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 ...