2
$\begingroup$

Let $S=\{0,1\}^n$ be a binary string of length $n$. Suppose you pick a number $r$ at random from any distribution on $\{1,\ldots,R\}$ of your choice and randomly generate $r$ boolean hash functions $h_0, h_1,\ldots, h_{r-1}: \{0,1\}\to\{0,1\}$. Using these hash functions, you take a one-directional random walk on $S$, starting at time $t=1$ and index $i=1$ so that if $h_{t \bmod{r}}(S[i])=1$, then you move from index $i$ to $i+1$. In other words, if the value of the hash function, indexed by your current time, of the character of your current position is $1$, then you move forwards in $S$. The random walk ends when you've processed the entire string $S$, i.e., when you've hit index $n+1$.

Conditioned on the random walk ending, do there exist $R=\text{polylog}(n)$ and constant $c>0$ for which we can upper bound the probability that the random walk ends at time $t\equiv 0 \bmod{r}$ by at most $O\left(\frac{1}{R^c}\right)$? Note that for $R=O(1)$, the probability is bounded by $\frac{1}{2}$ depending on the realization of $h_{r-1}$ and for $R=\Omega(n)$ with sufficiently large constant, the probability is bounded by $O\left(\frac{1}{\sqrt{n}}\right)$ from anti-concentration.

$\endgroup$
7
  • $\begingroup$ Should the hash domain be larger than $\{0,1\}$? $\endgroup$
    – kodlu
    Jun 8, 2020 at 0:30
  • $\begingroup$ No, the input to the hash functions is the symbol of the binary string $S$ at the current time/position, so I think $\{0,1\}$ is fine. $\endgroup$
    – learning
    Jun 8, 2020 at 2:15
  • $\begingroup$ ok, fine, the term "hash" is misleading though, it is usually associated with a length compressing string function. You may have said that you added a random noise bit $\pmod 2$ to the $S[i].$ $\endgroup$
    – kodlu
    Jun 8, 2020 at 8:21
  • $\begingroup$ I think you misstated something. What's to stop us from taking large $R$, but always taking $r=1$ (since we are allowed to have it be taken from any probability distribution on $\{1,\ldots,R\}$)? $\endgroup$ Jun 12, 2020 at 5:56
  • $\begingroup$ Yeah you're right, for $r=1$, it may be possible that $h_0(0)=h_1(0)=0$, so that the random walk never progresses (and in general), so I should have asked whether we can upper bound the probability, conditioned on the random walk terminating. Thanks for bringing it up, I've corrected the question. Note that for $h_0(0)=h_0(1)=1$, the random walk always terminates at some time congruent to $0\pmod{1}=0\pmod{r}$, so we cannot upper bound the probability by $\frac{1}{R^c}$. $\endgroup$
    – learning
    Jun 13, 2020 at 6:12

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.