Tagged Questions
1
vote
0answers
34 views
Fast way to estimate cardinal number of subset
I have a large set $S$ of items, but the set is not exactly known. All I know are the cardinal numbers of categories i.e. a number of disjoint subsets,
$ \vert{S_1}\vert \dots \vert S_n\vert$ with ...
-1
votes
1answer
27 views
How to compute conditional expectation of a log function
I've been studying the Expectation Maximization algorithm. According to the formula shown here, what I have to do in the M step is to compute a new $\theta$ that maximizes the conditional expectation ...
0
votes
1answer
36 views
PageRank algorithm. Iterative approach.
Given we have 4 nodes: A, B, C, D. A -> B and A <- B, B -> C, C -> D, C -> A and C <- A, D->A. We know only the starting probability of C which is 1. If we start from node C, what are the ...
1
vote
2answers
37 views
gradient descent optimal step size
Suppose a differentiable, convex function $F(x)$ exists. Then $b = a - \gamma\bigtriangledown F(a)$ imples that $F(b) <= F(a)$ given $\gamma$ is chosen properly. The goal is to find the optimal ...
0
votes
1answer
35 views
Using Chernoff bound to analysis the Lazyselect algorithm
It's my homework of the course of randomized algorithm. In the textbook (Randomized Altorithm by Rajeev Motwani et.al.), the author analyzed this algorithm using Chebyshev bound, but are there any ...
1
vote
1answer
109 views
Quicksort analysis problem
This is a problem from a probability textbook, not a CS one, if you are curious. Since I'm too lazy to retype the $\LaTeX$ I will post an ugly stitched screenshot:
This seems ridiculously hard to ...
0
votes
1answer
36 views
Probability of getting distinct numbers out of two differently distributed variables.
Assume you have $X$ and $Y$.
They both take the same values, but they have different distributions, for example:
$X$, $Y$ can be: $\{1,2,3\}$
$X$ has probabilities: $\{\frac{2}{7}$ ...
2
votes
1answer
36 views
Bounding the power of expected value of functions of a random variable.
I am interested in a problem and I do not know where to start looking for possible similar setting. If anyone has a direction to suggest, it would be greatly appreciated.
Consider a (finite) set ...
0
votes
1answer
50 views
How can I calculate the exact expected value of merge sort comparison (not O(n))?
First, the question stated that I have one unsorted list and then I have to split it out into two lists by fair coin flips. (Ex. Head goes A-list, tail goes B-list)
Second, I'm trying to solve the ...
2
votes
4answers
161 views
Can you simulate any probability with biased coin throws?
What you're given:
$p \in (0,1)$, but you don't know the value of $p$.
You have an algorithm $\mathcal{A}_p$ that returns $1$ with a probability of $p$ and $0$ with a probability of $(1-p)$. You ...
5
votes
2answers
106 views
Choosing between $n$ things using dice?
For which $n$ is there a finite algorithm to choose between $n$ things with the same probability using a die?
For example, we can choose between 2 things, 3 things, 4 things, 6 things, and 8 things, ...
0
votes
0answers
41 views
Maximum Independent Set by Distributed Algorithm
Maximum independent set on the ring could be found by distributed algorithm like following (unique UID's is required).
...
0
votes
1answer
39 views
Probability : Dividing a list into 2 classes
I have a list of integer numbers ($n$). I am dividing it into two parts $n_1$ (smaller) and $n_2$ (bigger) such that the length of $n_1 \ge a*n$; $a$ is positive and $a \lt 0.5$. What is the ...
1
vote
0answers
51 views
Maximum Independent Set on Path and Ring
I known this question is more appropriate to cs.stackexchange.com, nevertheless I want to ask it in Mathematics part because for solving the following problem strong understanding of probabilistic ...
1
vote
1answer
41 views
Median-of-k elements
Assume I am given a sequence of $n$ elements (by sequence I mean an ordered set). I want to randomly pick $k$ elements out of these $n$ elements, where $k$ is an odd number $\leq n$.
Then out of ...
4
votes
1answer
166 views
Puzzle : Birds on a circular wire
The problem is taken from my course on randomized algorithms :
There is a circle made of wire. n birds (assume n>2) occupy uniformly random position over it (visualize each bird occupying a point on ...
2
votes
1answer
104 views
Probability - Expected value of a $n$ random selection
Given an integer $n$, one does $n$ random selections with repetition one after the other. For each selection there are two possibilities a success $X$ and a failure $O$. For each selection $i\le n$ ...
1
vote
1answer
83 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 ...
0
votes
2answers
510 views
Intuition behind the concept of indicator random variables.
I am studying Randomized Algorithms chapter in the book "Introduction to Algorithms" by Cormen et al.
In this chapter the book introduces the concept of an indicator random variable and state that ...
4
votes
1answer
111 views
4
votes
1answer
675 views
Quick sort algorithm average case complexity analysis
This is for self-study. This question is from Kenneth Rosen's "Discrete Mathematics and Its Applications".
The quick sort is an efficient algorithm. To sort $a_1,a_2,\ldots,a_n$, this algorithm ...
3
votes
2answers
260 views
Monte Carlo algorithm that determines if a permutation of the integers 1 through $n$ has already been sorted.
This question is from "Discrete Mathematics and Its Applications", from Kenneth Rosen, 6th Edition.
Devise a Monte Carlo algorithm that determines whether
a permutation of the integers 1 through ...
0
votes
1answer
34 views
random Algorithm over Random input-help needed
A random Algorithm $A$ receives input in $[n]$ it's know that when the probability is taken over input that was chosen randomly over uni-formal distribution over the algorithm randomness the ...
1
vote
2answers
71 views
Is my algorithm probabilistically fair?
Let $S(n)$ be a sequence of length $n$. I want to give a label in $\{0,1,2,3\}$ to each term of $S(n)$ so that each term is given its label randomly. From some reasons, I want to use the following ...
1
vote
2answers
138 views
Algorithm to generate a fraction of winners based on a maximum number of players
I have some sort of a math issue : I have to implement an algorithm that randomly generates winners and losers based on :
a maximum number of players
a percentage of winners to reach
Of course, ...
0
votes
1answer
374 views
how to implement hash functions for Bloom filter [closed]
I read an article about the Bloom filter but I am not really familiar with hash function. Is there any document online where I can find information about how to implement those hash functions?
...
2
votes
1answer
774 views
Implementation of the Baum-Welch algorithm for HMM parameter estimation
In order to learn HMM thoroughly, I am implementing (in Matlab) the various algorithms for the basic questions of HMM. I've implemented the Viterbi, posterior-decoding, and the forward-backward ...
2
votes
1answer
642 views
how to distribute n red and m blue balls in some containers to maximize probability of random picking a red one from them?
This is an interview question.
Given n red balls and m blue balls and some containers, how would you distribute those balls among the containers such that the probability of picking a red ball is ...
7
votes
1answer
192 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
4answers
211 views
Figuring out probabilities with Hidden Markov Models
I'm really new to Math so sorry in advance if this question does not make sense. Also I cross posted this on stats.stackexchange.com also.
Background:
I'm trying to learn about hidden Markov models ...
1
vote
2answers
59 views
Is there a way to find $P(H_h)$, $P(E_\epsilon|H_\eta) (1 \leq \epsilon \leq e)$ and $P(E_\epsilon) (1 \leq \epsilon \leq e)$?
The problem:
If we have
$P(H_\eta|E_1,E_2,...,E_e)(1 \leq \eta \leq \mathbb{H})$
and
$P(E_1,E_2,...,E_e)$
for all True and False values of $E_\epsilon(1 \leq \epsilon \leq e)$ and ...
1
vote
1answer
104 views
Strategy to maximize no. of balls from N boxes
If you have N boxes each containing distinct number of balls and you are allowed to choose at most ...
4
votes
3answers
488 views
How to approach number guessing game(with a twist) algorithm?
I posted this on stackoverflow, but was advised to also post here. It's kind of a math/algo question so I think it's kind of stuck between both worlds of math and computer science. I believe this to ...
1
vote
0answers
80 views
optimize the expected value of a process
There are $a_i$ balls painted with number $i$. For example if we have balls painted with 1,1,1,3,2.
we have $a_1 = 3$, $a_2=1$, $a_3=1$. In total there are $m$ balls painted with number $1,\ldots,n$.
...
0
votes
0answers
92 views
Unbiased (random?) selection algorithm
Let say we have the following set $S = \{x_1, x_2, x_3, ..., x_n\}$
where $x_i$ is a real number between $0$ and $1$.
Now I want to find an algorithm that randomly generates a subset of $S$, free to ...
2
votes
0answers
90 views
Probabilistic analysis of two algorithms
Let $f$ be a binary function programmed at random; i.e. for any $x$ in its domain, $f(x)$ equals some $n$-bit value initially chosen at random. Such a function has the nice property that for any two ...
1
vote
0answers
69 views
First hitting time for generalized Pólya urn
I have looked around the literature but I've not found a clean answer to the following. Imagine that you have a generalized Pólya urn (GPU) in the sense of Pemantle's survey (Section 2.1 in ...
2
votes
3answers
783 views
Probability Calculations on Highway
I read this Google Interview Question.
Q:If the probability of observing a car in 30 minutes on a highway is 0.95, what is the probability of observing a car in 10 minutes (assuming constant default ...
2
votes
2answers
139 views
Formula to generate a score from 1 to 100 based on 2 percentages?
I am trying to come up with a formula that will result in a score of 1 to 100 (never anything lower or higher). I have two numbers that I can use to come up with this score, a specific percent and an ...
1
vote
1answer
106 views
Distribution of a random variable related to insertion sort
I am given a uniformly chosen permutation of the set $\{1,\ldots,n\}$ as an array $A[1,\ldots,n]$. For an integer $1 \leq j \leq n$ I am studing the distribution of the variable $X$ counting the ...
7
votes
2answers
399 views
Buckets of Balls, Will one fill if I add another Ball?
I was refereed here by stackoverflow.com. With some searching I found this: another balls and bins question, but its not quite what I am looking for. Rather the inverse. IE the expected number of ...
6
votes
2answers
252 views
Expected travel time for regularly departing trains
I'm going to ask a very simple practical question, but I believe it has some interesting mathematical properties.
The simple variant is: trains depart every $x$ minutes and take $y$ minutes to arrive ...
6
votes
2answers
437 views
How many steps does it take the computer to solve a Sudoku puzzle?
We all know what Sudoku is. Given a Sudoku puzzle, one can use a simple recursive procedure to solve it using a computer. Before describing the algorithm, we make some definitions.
A partial solution ...
5
votes
1answer
233 views
How is a Halton sequence related to a Latin hypercube?
I currently use a Halton sequence to choose parameter sets for a prognostic model (e.g. using metabolic rate and protein content parameters to predict growth rate).
From my understanding, both a ...
2
votes
1answer
137 views
How can I generate a random DFA with uniform distribution?
I need to generate a Deterministic Finite Automata (DFA), selected from all possible DFAs that satisfy the properties below. The DFA must be selected with uniform distribution.
The DFA must have ...
6
votes
0answers
204 views
Does this calculation have a name, or a generic formulation?
Background
I would appreciate help in identifying / explaining this operation:
To calculate each of the $n$ values of $f(\Phi)$:
sample from the distribution of each of $i$ parameters, $\phi_i$
...
2
votes
1answer
291 views
clarification on Chernoff's inequality
i'm studing probabilistic algorithms: the ones that - with a great gain in efficency - sometimes could return a false response.
They return the true response with a probability of $\frac{3}{4}$.
The ...
0
votes
1answer
376 views
Consequences of choice of a seed for random number generating algorithm?
Background
I am trying to do a reproducible scientific analysis. My conclusions are not dependent on the random number generator, but the RNG does change the results ~1% between runs. I would like to ...
2
votes
3answers
171 views
Expected time of tree search algorithm on random input
We have a perfect binary tree on 2^k-1 nodes. Every node in the tree is marked with probability 1/2, and a node is either marked or unmarked. We want to find a marked node and return it. Our algorithm ...
1
vote
1answer
578 views
Calculating probabilities for a 4-state Markov model
I need to write a piece of software that analyzes packet switched computer networks and calculates certain characteristics based on packet loss (the application is Voice over IP quality monitoring). ...
