Tagged Questions

28 views

On achieving the maximal correlation

I am reading the famous paper of Renyi, entitled "On measures of dependence" (see here1). He redefined the maximal correlation in a very general form for both discrete and continuous random ...
36 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 ...
53 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 ...
49 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 ...
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 ...
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 ...
24 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 ...
79 views

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 ...
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 ...
138 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 ...
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 ...
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 ...
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$ ...
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, ...
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 ...
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 ...
615 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 ...
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 ...
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 ...
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 ...
380 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 ...
162 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 ...
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 ...
218 views

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 ...
903 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 ...
57 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}$ ...