Probability of reaching a state in asymmetric random walk

Consider the following random walk:
enter image description here

Namely, if $S_i$ is the state at time $i$, then $Pr(S_{i+1}=1|S_i=0)=1$, and for every $s>0$ we have
$$S_{i+1}|S_i=s=
begin{cases}
s+1 & text{w.p. }1-p\
s-1 & text{w.p. }p
end{cases}.
$$

In my application, $p>frac{1}{2}$. I’m interested in two quantities, $Pr(S_T > H)$ and $mathbb E(S_T)$. My intuition is that $Pr(S_T > C ln T)leq frac{1}{T^2}$ for some global constant $C$, and that $mathbb E(S_T)=o(1)$. However, I couldn’t show it (yet).

Any ideas?


Here are some trivial claims. First, $Pr(S_T > H) leq exp(-frac{H^2}{T})$ due to Azuma’s inequality, but that doesn’t use the value $p$ nor the fact that $p> frac{1}{2}$. Second, $mathbb E(S_T) leq O(sqrt{T})$ since $S_t$ is stochastically dominated by a symmetric random walk, for which the expected place at time $T$ is $O(sqrt{T})$.

The stationary distribution is easy to find, being $pi_0=1-frac{1}{2p}$ and $pi_i = frac{pi_0}{p} left(frac{1-p}{p}right)^{i-1}$, but I’m not sure how to use it.

air travel – Do flight attendants prefer I press the button or walk to the back? (Long-haul flights)

Get Up if You Can, Call if You Can’t

I’d use your personal judgement on this one. What I do on long-haul flights is get up and go ask myself. For starters it makes me get up and move around a bit which is not at all bad. Secondly, I tell myself that flight attendants might be busy with something else and that my getting up might actually be helpful for them. From the way you worded your question I’m getting the idea that you think the same.

Now all this is all nice and dandy, if you are in a position to easily get up and move around. In other words, this works if you are seated on the aisle. However, if you are seated next to the window, with two other seats separating you from the aisle, you might want to press the button and wait. Calling the flight attendant might be much less disturbance than having to play musical chairs with two other passengers twice (to get out and back in) to go pick up a beer. Moreover, once you call the flight attendant, you can ask for two beers, so that you won’t have to repeat the process again soon thereafter.

Now, all of this is just my personal way of going about this. For completeness sake I managed to find some interesting posts here and there on the web offering similar and different point of views.

Get Up in Economy, Call in Business/First

This post on OneMileAtATime makes a somewhat valid point in distinguishing between economy class and business. In economy the attendant-to-passenger ratio is on the understaffed side of the scale (some 1:50 average). If many passengers push the button at the same time, the aircraft staff are likely to go crazy trying to manage all the requests. The same can also be said if many passengers get up concurrently to go towards the galley. However, on most long-haul flights you’ll find a nice self-serve tray with drinks and snacks set-up in the galley from which you can quench most of your cravings. If beer isn’t on the tray, you can go ask the staff directly.

In business/first class on the other hand the attendant-to-passenger ratio is much lower, and staff generally have a much easier time dealing with passenger requests. In that case you could opt for pressing the button over getting up yourself if you wish to do so.

Be Considerate to Staff Privacy

The post goes on to mention another interesting scenario. The author says that galleys are usually screened away from the cabin with curtains, aimed ad providing staff with some kind of privacy/relaxed environment. There’s a chance that airline policy or cultural norm might dictate that passengers aren’t supposed to see the staff in their relaxed mode. Hence, by walking up to the galley yourself you might be somewhat causing an awkward situation.

Quoting directly from the linked site:

On non-US airlines I think it’s always acceptable to push the call button for something service related. And I’ll take it a step further. Aside from airlines that have onboard bars, I find most crews actually prefer that you push the call button rather than coming to the galley, at least between meals.

What you might notice on most international carriers is that they have thick curtains between the galley and the rest of the cabin, so most of the time between meals the crews will draw the “curtains” around the galley. I’ve walked in on some really awkward situations while thinking I was doing them a favor by going to the galley to request something rather than pushing the call button.

Now if I’m going to the lavatory and see a crew member in sight then I might ask them for something, but I’ve found in the galley they’re often eating, applying makeup, or doing other less kosher things. So by pushing the call button you’re letting them present themselves to you as they’d like to be seen rather than basically opening their “curtain” uninvited.

Be Polite

As an added bonus, whatever you do keep a smile on your face and be polite. I’m prepared to bet that being arrogant and rude to the staff is much more of a problem than you pressing the button once when you’re not supposed to.

In the words of this flight attendant on FlyerTalk puts it:

As a philosophy, I am happy for you to use it at your discretion – as long as your discretion doesn’t mistake “flight attendant” for “personal servant” (that definitely happens!), and remember (if I may reiterate) that there are usually 200 hundred of you onboard. If you respect those facts and still see a need to ring, I support you. Most of my friends, I think, feel the same. Let’s be honest among friends though: In reality you just have to feel out your crew.

I will put out there that drink requests are a little bit special. I do prefer you come ask for it yourself (mostly I’m just afraid if passengers see me “running” for a drink, 1000 other dings will follow and it will get out of hand), but I wouldn’t be grumpy about it. Not unless you start dinging over and over.

As I like to say, all things in moderation. Trapped at the window? I can see that’s awkward! Need a hand? I’ll happily help. Feel the need for a cheeky drink that you’re occasionally too lazy to come to the galley for? I might tease you, but oh, go on then!

Still unsure? Here’s another measure: If you’re the kind of passenger to care if you should use it, you’re probably ok to do so. I promise to do it with pleasure, if you promise not to get carried away.

random walk – Expected number of stepds to reach 1 from n

Suppose a particle is moving in discrete steps. When it is at position $nge1$, it takes a step of size $X_n$, and moves to $n-X_n$, where $X_n$ is a random variable taking values in ${iinBbb{Z}mid ile n-1}$. Suppose there is a non-decreasing function $g:Bbb{R}^+toBbb{R}^+$ (where $Bbb{R}^+$ is the set of positive reals). All that we know about the distribution of $X_n$, is that $Bbb{E}(X_n)le g(n)$.

Let $T_n$ be the number of steps the particle takes to reach $1$ (for the first time). How can I calculate $Bbb{E}(T_n)$ in terms of $g(n)$?

I have solved the problem for a much simpler case, where $X_n$ could only take the values $1,2,cdots,n-1$. This simpler version can be easily solved via induction, and it turns out
$$Bbb{E}(T_n)leint_1^nfrac{dx}{g(x)}$$

How do I solve it for the more general case? Thanks in advance.

unity – Parameter ‘Walk’ doesn’t exist?

I’m trying to make walk animation. But when I try to change animation idle to walk, ıt doesn’t work.
It says ‘Parameter “Walk” doesn’t exist’but I added parameter and script works. I can manually change parameter and it works(walk animation is playing). But when I try to change via script, ıt doesn’t work.

enter image description here

Here are codes

public class Controller : MonoBehaviour

private Rigidbody rb;

private float xPos;

Vector3 playerMovement;

(SerializeField) Animator anim;

private void Awake() => rb = GetComponent<Rigidbody>();

private void Start()
{
    xPos = transform.position.x;
}

// Update is called once per frame
void Update()
{
    Move();
}

private void Move()
{
    float mH = Input.GetAxis("Horizontal");
    playerMovement = new Vector3(0, 0, mH);
    rb.AddForce(playerMovement * 2f);
    anim.SetFloat("Walk", 1);
    transform.position = new Vector3(xPos, transform.position.y, transform.position.z);
}

c – Random walk on a grid

// generate a random "walk" of letters from A to Z in a 2D grid, assuming a 
// character set with contiguous values of uppercase letters (e.g. ASCII); 
// stops if the "walker" gets stuck
// example of a successful walk:

//  A  .  .  .  I  J  K  .  .  . 
//  B  C  F  G  H  .  L  .  .  .
//  .  D  E  .  .  .  M  .  .  .
//  .  .  .  .  .  O  N  .  .  .
//  .  .  .  .  .  P  .  .  .  .
//  .  .  .  .  .  Q  .  .  .  .
//  .  .  .  .  .  R  S  .  .  .
//  .  .  .  .  .  .  T  U  .  . 
//  .  .  .  .  .  .  .  V  W  Z
//  .  .  .  .  .  .  .  .  X  Y

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>
#include <ctype.h>

#define GRID_SIZE 10

// movement directions
#define DIR_NUM 4

#define UP      0
#define LEFT    1
#define DOWN    2
#define RIGHT   3
#define ANY     (-1)

bool can_move(int dir, size_t rpos, size_t cpos, size_t rows, size_t cols,
              char grid(rows)(cols));
void generate_random_walk(size_t rows, size_t cols, char grid(rows)(cols));
void print_array(size_t rows, size_t cols, char grid(rows)(cols));

int main(void)
{
    char grid(GRID_SIZE)(GRID_SIZE) = { 0 };

    generate_random_walk(GRID_SIZE, GRID_SIZE, grid);
    print_array(GRID_SIZE, GRID_SIZE, grid);

    return 0;
}

void print_array(size_t rows, size_t cols, char grid(rows)(cols))
{
    for (size_t r = 0; r < rows; ++r) {
        for (size_t c = 0; c < cols; ++c) {
            char grid_c = grid(r)(c);
            printf(" %c ", isalpha(grid_c) ? grid_c : '.');
        }
        putchar('n');
    }
}

// checks all the directions by default (ANY)
bool can_move(int dir, size_t rpos, size_t cpos, size_t rows, size_t cols,
              char grid(rows)(cols))
{
    bool cangoup    = (rpos > 0) && grid(rpos - 1)(cpos) == 0;
    bool cangoleft  = (cpos > 0) && grid(rpos)(cpos - 1) == 0;
    bool cangodown  = (rpos < rows - 1) && grid(rpos + 1)(cpos)  == 0;
    bool cangoright = (cpos < cols - 1) && grid(rpos)(cpos + 1)  == 0;

    switch (dir) {
    case UP:    return cangoup;
    case LEFT:  return cangoleft;
    case DOWN:  return cangodown;
    case RIGHT: return cangoright;
    default:    return cangoup || cangoleft || cangodown || cangoright; // ANY
    }
}

void generate_random_walk(size_t rows, size_t cols, char grid(rows)(cols))
{
    size_t rpos, cpos;

    srand((unsigned int) time(NULL));

    rpos = cpos = 0;
    grid(0)(0) = 'A';
    for (char c = 'B'; c <= 'Z' && can_move(ANY, rpos, cpos, rows, cols, grid); c++) {
        // move in a random direction
        for (int dir;;) {
            dir = rand() % DIR_NUM;
            if (can_move(dir, rpos, cpos, rows, cols, grid)) {
                switch (dir) {
                case UP:    --rpos; break;
                case LEFT:  --cpos; break;
                case DOWN:  ++rpos; break;
                case RIGHT: ++cpos; break;
                default:
                    printf("Impossible movement direction.n");
                    exit(EXIT_FAILURE);
                }
                break; // break out of the loop
            }
        }

        // leave a trail
        grid(rpos)(cpos) = c;
    }
}

To summarize, this program prints a grid with a random walk of uppercase letters in order. If the “walker” cannot move in any direction due to lack of space around it (up, down, left, and right), the walking terminates.

What I’m interested in, aside from general tips regarding my code that you may be able to give me, are two things:

  1. I’ve read that functions shouldn’t normally take more than 2–3 parameters; do you think my functions really “suffer” from taking more than 3 parameters, and if so, how would I go about mitigating that?

  2. Should I be using a size_t when looping over an array or similar, or should I use an int instead? I’ve read here on Stack Exchange various opinions concerning this: some people say size_t should always be used since it’s essentially undefined behavior if the array’s size is greater than MAX_INT, etc., while others say unsigned and signed types ought not to be mixed (and I generally have to use them in expressions that undergo the usual arithmetic conversions), and this is a major source of bugs. Pragmatically, I believe I should therefore use a regular int. There’s another thing I’ve noticed, and that is if I have to actually use these counters to perform some calculation: in those cases I really have no recourse, and what I end up doing is simply casting and praying, hoping that the array is of a reasonable size (i.e. that my size_t counter, or the result of the expression isn’t out of the representable range for an int). I think this is even worse than using an int from the beginning, since the interface that the size_t type provides is not conformed to, so my code is “lying” to both itself and the reader.

Note that I would use an enum instead of the #define definitions for the directions, but my book hasn’t gotten to them yet, so I think we shouldn’t focus on this. Also, I’ve looked at other questions with this same exercise, but the code/approach presented there is somewhat different.

Given graph G and vertices v and w can you non-deterministically walk the “least Hamiltonian path” from v to w, if it exists?

My understanding of non-deterministic algorithms is that they’re “as lucky as you want”.

…you can think of the algorithm as being able to make a guess at any point it wants, and a space alien magically guarantees it will always make the right/lucky guess.

For example, if you choose two vertices v and w, if there’s a vw path, then you can non-deterministically walk a vw path, luckily correctly guessing the vertices to walk in a vw path. Given this is true of paths in general, I wonder if the same can be done for Hamiltonian paths. I would think so, but I’m not sure.

Therefore, my first question is: if you can non-deterministically walk a vw path, can you non-deterministically walk a Hamiltonian path from v to w, if a Hamiltonian path exists? If you can non-deterministically walk a Hamiltonian path, I wonder if the same can be done for an additional constraint, what I’m calling a “least Hamiltonian path.” I would think so, but I’m not sure.

Define the least Hamiltonian path from v to w to be the Hamiltonian path such that the second vertex is the smallest it can be, then the third vertex is the smallest it can be, the fourth is the smallest, etc. Assume vertices are integers. For example, if we consider K5 the graph with vertices {1,2,3,4,5} and all possible edges, then the least Hamiltonian path for (v,w) = (2,3) is 21453. If you were at vertex 2, the next least vertex would be 1. Then, the next least vertex would 4. etc.

Therefore, my actual question is: Given graph G and vertices v and w can you non-deterministically walk the least Hamiltonian path from v to w, if it exists?

Motivation: If so, then perhaps there’s a space-efficient algorithm for non-deterministically walking a Hamiltonian path: You can keep a counter for vertices v and w, and go through each pair of vertices such that v<w, checking for the existence of a least Hamiltonian path. To ensure all vertices in G are reached, keep a counter for the number of vertices walked (this should equal N if there are N vertices). Also, ensure that each vertex in the path is unique. The least Hamiltonian path from v to w will be unique, therefore it can be walked multiple times (each time you walk through it, starting at v, you’ll non-deterministically guess the next least vertex in the least Hamiltonian path). You could use two counters to ensure no vertices are repeated – one for the vertex you’re checking to see if it’s unique (loop through the vertices in the least Hamiltonian path), and another counter for a second pass through the least Hamiltonian path. Ensure the second counter encounters the value of the first counter exactly once (use a boolean flag to keep track of this).

Mean square displacement of self-avoiding walk in dimension 5 or more

What would be the best detailed written resource to study mean square displacement of self-avoiding walk in dimension 5 or more?

Is there a flexible calculator available that can walk you through complex SQL licensing?

The basic license guide for Microsoft SQL Server is 40 pages in length. This document references still more documents on various topics, options, and definitions used for licensing. The license that one selects determines the conditions that will trigger additional costs required to stay functional over time.

Is there an accurate application that can be used to determine pricing for the various licensing and project a timeline for potential additional costs as a function of time and growth?

This would be a useful tool for proposal writers, legal teams, and planners.

It is very clear that licensing has become it’s own “career track” that favors large business.

A tool or business that could provide an unambiguous set of costs and terms based on list price could be free small to medium sized businesses to move forward on projects with some measure of confidence.

Revenge or Walk Away? | Forum Promotion

Random walk generator – looking for optimizations (Python)

I just started learning Python and this is the first code I wrote. It’s a Random Walk generator. I think I got it to work pretty well but I’m also sure there are more effective and less clunky ways to do this. Could you give me some tips on what to change to make the code shorter/more optimized and just objectively more “pythonian” and better?

# Random Walk in two dimensions

import random

steps = "a"
maximal = "a"
minimal = "a"
Xstep = 0
Ystep = 0
StepSize = 0
PosNeg = 0


def new_line():
    print(" ")


def invalid_enter_number():
    print("Invalid input! Enter a number.")
    new_line()


def invalid_enter_positive():
    print("Invalid input! Enter a positive number.")
    new_line()


new_line()
print("Random Walk in two dimensions")
new_line()

while type(steps) != int:
    try:
        steps = int(input("How many steps should be done? "))
        while steps <= 0:
            invalid_enter_positive()
            steps = int(input("How many steps should be done? "))
    except:
        steps = ValueError
        invalid_enter_number()
        continue

while type(maximal) != int:
    try:
        maximal = int(input("How big is the biggest possible step? "))
        while maximal <= 0:
            invalid_enter_positive()
            maximal = int(input("How big is the biggest possible step? "))
    except:
        maximal = ValueError
        invalid_enter_number()
        continue

if maximal != 1:
    while type(minimal) != int:
        try:
            minimal = int(input("How big is the smallest possible step? "))
            while minimal <= 0 or minimal >= maximal:
                if minimal <= 0:
                    invalid_enter_positive()
                    minimal = int(input("How big is the smallest possible step? "))
                else:
                    print("Number must be smaller than the biggest possible step!")
                    new_line()
                    minimal = int(input("How big is the smallest possible step? "))
        except:
            minimal = ValueError
            invalid_enter_number()
            continue
else:
    minimal = 1

new_line()
print("Number of steps:", steps)

if maximal != 1:
    print("Step size range:", minimal, "-", maximal)
else:
    print("Step size: 1")

new_line()
print("Steps:")

while steps > 0:
    StepSize = random.randint(minimal, maximal)
    PosNeg = random.randint(0, 1)
    chance = random.randint(0, 1)
    if chance == 0 and PosNeg == 0:
        Xstep += StepSize
    elif chance == 0 and PosNeg == 1:
        Xstep -= StepSize
    elif chance == 1 and PosNeg == 0:
        Ystep += StepSize
    else:
        Ystep -= StepSize
    print("X:", Xstep, " Y:", Ystep)
    steps -= 1